## Algorithm

Problem Name: 1129. Shortest Path with Alternating Colors

You are given an integer `n`, the number of nodes in a directed graph where the nodes are labeled from `0` to `n - 1`. Each edge is red or blue in this graph, and there could be self-edges and parallel edges.

You are given two arrays `redEdges` and `blueEdges` where:

• `redEdges[i] = [ai, bi]` indicates that there is a directed red edge from node `ai` to node `bi` in the graph, and
• `blueEdges[j] = [uj, vj]` indicates that there is a directed blue edge from node `uj` to node `vj` in the graph.

Return an array `answer` of length `n`, where each `answer[x]` is the length of the shortest path from node `0` to node `x` such that the edge colors alternate along the path, or `-1` if such a path does not exist.

Example 1:

```Input: n = 3, redEdges = [[0,1],[1,2]], blueEdges = []
Output: [0,1,-1]
```

Example 2:

```Input: n = 3, redEdges = [[0,1]], blueEdges = [[2,1]]
Output: [0,1,-1]
```

Constraints:

• `1 <= n <= 100`
• `0 <= redEdges.length, blueEdges.length <= 400`
• `redEdges[i].length == blueEdges[j].length == 2`
• `0 <= ai, bi, uj, vj < n`

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
private final Integer RED = 1;
private final Integer BLUE = 2;
public int[] shortestAlternatingPaths(int n, int[][] red_edges, int[][] blue_edges) {
Map> map = new HashMap<>();
for (int[] edge : red_edges) {
map.computeIfAbsent(edge, k -> new ArrayList<>()).add(new Connection(edge, RED));
}
for (int[] edge : blue_edges) {
map.computeIfAbsent(edge, k -> new ArrayList<>()).add(new Connection(edge, BLUE));
}
int[] distances = new int[n];
for (int i = 1; i < n; i++) {
distances[i] = getDistance(map, i, n);
}
return distances;
}

private int getDistance(Map> map, int target, int n) {
int curr = 0;
int steps = 0;
boolean found = false;
boolean[][] visited = new boolean[n];
while (!queue.isEmpty()) {
int size = queue.size();
while (size-- > 0) {
int[] removed = queue.remove();
if (removed == target) {
found = true;
break;
}
int color = removed;
for (Connection connection : map.getOrDefault(removed, new ArrayList<>())) {
if (color == -1 && !visited[connection.color - 1][connection.val]) {
visited[connection.color - 1][connection.val] = true;
}
else if (color == 1 && connection.color != 1 && !visited[connection.color - 1][connection.val]) {
visited[connection.color - 1][connection.val] = true;
}
else if (color == 2 && connection.color != 2 && !visited[connection.color - 1][connection.val]) {
visited[connection.color - 1][connection.val] = true;
}
}
}
if (found) {
break;
}
steps++;
}
return found ? steps : -1;
}
}

class Connection {
int val;
int color;

public Connection(int val, int color) {
this.val = val;
this.color = color;
}

public int[] getArray() {
return new int[]{this.val, this.color};
}
}
``````
Copy The Code &

Input

cmd
n = 3, redEdges = [[0,1],[1,2]], blueEdges = []

Output

cmd
[0,1,-1]

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const shortestAlternatingPaths = function(n, red_edges, blue_edges) {
let d = new Array(n * 2).fill(Number.MAX_SAFE_INTEGER)
let queue = []
d = d[n] = 0
queue.push(0)
queue.push(n)
while (queue.length) {
let cur = queue.shift()
if (cur < n) {
for (let r of red_edges) {
if (r == cur && d[r + n] > d[cur] + 1) {
d[r + n] = d[cur] + 1
queue.push(r + n)
}
}
} else {
for (let b of blue_edges) {
if (b == cur - n && d[b] > d[cur] + 1) {
d[b] = d[cur] + 1
queue.push(b)
}
}
}
}
let res = new Array(n).fill(-1)
for (let i = 0; i < n; i++) {
res[i] =
Math.min(d[i], d[i + n]) == Number.MAX_SAFE_INTEGER
? -1
: Math.min(d[i], d[i + n])
}
return res
}
``````
Copy The Code &

Input

cmd
n = 3, redEdges = [[0,1],[1,2]], blueEdges = []

Output

cmd
[0,1,-1]

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:

def dfs(i, mod, cnt):
res[i][mod] = cnt
for v in edge[i][mod]:
if cnt < res[v][1 - mod]:
dfs(v, 1 - mod, cnt + 1)

res = [[float('inf'), float('inf')] for _ in range(n)]
edge = [[[], []] for _ in range(n)]
for u, v in red_edges:
edge[u].append(v)
for u, v in blue_edges:
edge[u].append(v)
dfs(0, 0, 0)
dfs(0, 1, 0)
return [x if x != float('inf') else -1 for x in map(min, res)]
``````
Copy The Code &

Input

cmd
n = 3, redEdges = [[0,1]], blueEdges = [[2,1]]

Output

cmd
[0,1,-1]