Shortest Path with Alternating Colors
Consider a directed graph, with nodes labelled 0, 1, ..., n-1
. In this graph, each edge is either red or blue, and there could be self-edges or parallel edges.
Each [i, j]
in red_edges
denotes a red directed edge from node i
to node j
. Similarly, each [i, j]
in blue_edges
denotes a blue directed edge from node i
to node j
.
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 doesn't exist).
Example 1:
Input: n = 3, red_edges = [[0,1],[1,2]], blue_edges = []
Output: [0,1,-1]
Example 2:
Input: n = 3, red_edges = [[0,1]], blue_edges = [[2,1]]
Output: [0,1,-1]
Example 3:
Input: n = 3, red_edges = [[1,0]], blue_edges = [[2,1]]
Output: [0,-1,-1]
Example 4:
Input: n = 3, red_edges = [[0,1]], blue_edges = [[1,2]]
Output: [0,1,2]
Example 5:
Input: n = 3, red_edges = [[0,1],[0,2]], blue_edges = [[1,0]]
Output: [0,1,1]
Constraints:
1 <= n <= 100
red_edges.length <= 400
blue_edges.length <= 400
red_edges[i].length == blue_edges[i].length == 2
0 <= red_edges[i][j], blue_edges[i][j] < n
class Solution {
static class Pair {
int val, color;
Pair(int val, int color) {
this.val = val;
this.color = color;
}
}
// there could be self-edges or parallel edges.
public int[] shortestAlternatingPaths(int n, int[][] red_edges, int[][] blue_edges) {
List<Pair>[] graph = new ArrayList[n];
for (int i = 0; i < n; i++)
graph[i] = new ArrayList<>();
// 0-> red, 1-> blue
for (int[] edge : red_edges)
graph[edge[0]].add(new Pair(edge[1], 0));
for (int[] edge : blue_edges)
graph[edge[0]].add(new Pair(edge[1], 1));
int[] ans = new int[n];
Arrays.fill(ans, -1);
// BFS
boolean visited[][] = new boolean[n][2];
Queue<Pair> q = new LinkedList<>();
q.add(new Pair(0, -1));
// package ->(node, color from which we reach this node)
int counter = 0;
while (q.size() != 0) {
int size = q.size();
while (size-- > 0) {
Pair node = q.poll();
int color = node.color;
int val = node.val;
if (color != -1 && visited[val][color])
continue;
if (color == -1) {
visited[val][0] = true;
visited[val][1] = true;
} else
visited[val][color] = true;
ans[val] = Math.min(ans[val] == -1 ? Integer.MAX_VALUE : ans[val], counter);
for (Pair adj : graph[val])
if (color == -1 || adj.color != node.color)
q.add(adj);
}
counter++;
}
return ans;
}
}
Last updated