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 nodeaito nodebiin the graph, andblueEdges[j] = [uj, vj]indicates that there is a directed blue edge from nodeujto nodevjin 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 <= 1000 <= redEdges.length, blueEdges.length <= 400redEdges[i].length == blueEdges[j].length == 20 <= 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 < Integer, List();
for (int[] edge : red_edges) {
map.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(new Connection(edge[1], RED));
}
for (int[] edge : blue_edges) {
map.computeIfAbsent(edge[0], k -> new ArrayList < >()).add(new Connection(edge[1], 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 < Integer, List queue = new LinkedList<>();
boolean[][] visited = new boolean[2][n];
queue.add(new int[]{0, -1});
while (!queue.isEmpty()) {
int size = queue.size();
while (size-- > 0) {
int[] removed = queue.remove();
if (removed[0] == target) {
found = true;
break;
}
int color = removed[1];
for (Connection connection : map.getOrDefault(removed[0], new ArrayList < >())) {
if (color == -1 && !visited[connection.color - 1][connection.val]) {
visited[connection.color - 1][connection.val] = true;
queue.add(connection.getArray());
}
else if (color == 1 && connection.color != 1 && !visited[connection.color - 1][connection.val]) {
visited[connection.color - 1][connection.val] = true;
queue.add(connection.getArray());
}
else if (color == 2 && connection.color != 2 && !visited[connection.color - 1][connection.val]) {
visited[connection.color - 1][connection.val] = true;
queue.add(connection.getArray());
}
}
}
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};
}
}
Input
n = 3, redEdges = [[0,1],[1,2]], blueEdges = []
Output
[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[0] = 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[0] == cur && d[r[1] + n] > d[cur] + 1) {
d[r[1] + n] = d[cur] + 1
queue.push(r[1] + n)
}
}
} else {
for (let b of blue_edges) {
if (b[0] == cur - n && d[b[1]] > d[cur] + 1) {
d[b[1]] = d[cur] + 1
queue.push(b[1])
}
}
}
}
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
}
Input
n = 3, redEdges = [[0,1],[1,2]], blueEdges = []
Output
[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][0].append(v)
for u, v in blue_edges:
edge[u][1].append(v)
dfs(0, 0, 0)
dfs(0, 1, 0)
return [x if x != float('inf') else -1 for x in map(min, res)]
Input
n = 3, redEdges = [[0,1]], blueEdges = [[2,1]]
Output
[0,1,-1]