1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| class Solution {
public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
Map<Integer, List<int[]>> nodeNeighbors = new HashMap<>();
for (int[] redEdge : redEdges) {
int startNode = redEdge[0], endNode = redEdge[1];
nodeNeighbors.computeIfAbsent(startNode, (key) -> new ArrayList<>()).add(new int[] { endNode, 0 });
}
for (int[] blueEdge : blueEdges) {
int startNode = blueEdge[0], endNode = blueEdge[1];
nodeNeighbors.computeIfAbsent(startNode, (key) -> new ArrayList<>()).add(new int[] { endNode, 1 });
}
Deque<int[]> queue = new ArrayDeque<>();
boolean[][] visited = new boolean[n][2];
visited[0][0] = true;
visited[0][1] = true;
queue.offer(new int[] { 0, -1 });
int distance = 0;
int[] ans = new int[n];
Arrays.fill(ans, -1);
ans[0] = 0;
while (!queue.isEmpty()) {
for (int i = queue.size(); i > 0; i--) {
int[] currNodeInfo = queue.poll();
int currNode = currNodeInfo[0], lastEdgeColor = currNodeInfo[1];
ans[currNode] = ans[currNode] == -1 ? distance : Math.min(ans[currNode], distance);
if (nodeNeighbors.containsKey(currNode)) {
for (int[] neighborInfo : nodeNeighbors.get(currNode)) {
int neighbor = neighborInfo[0], pathColor = neighborInfo[1];
if (pathColor != lastEdgeColor && !visited[neighbor][pathColor]) {
visited[neighbor][pathColor] = true;
queue.offer(new int[] { neighbor, pathColor });
}
}
}
}
distance += 1;
}
return ans;
}
}
|
