1129. 顔色交替的最短路徑（BFS）

class Solution {
    public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        List<Integer>[][] edge = new List[2][n]; // edge[0][0] 表示與節點0相連的所有紅邊
                                             // edge[0][1] 表示與節點1相連的所有藍邊
        for(int i=0;i<2;i++) {
            for(int j=0;j<n;j++) {
                edge[i][j] = new ArrayList<>();
            }
        }
        for(int[] red:redEdges) {
            edge[0][red[0]].add(red[1]);
        }
        for(int[] blue:blueEdges) {
            edge[1][blue[0]].add(blue[1]);
        }
        int[][] dist = new int[2][n]; // dist[0][1] 表示0-1且邊最終顔色為紅色的最短路徑
                                      // dist[1][1] 表示0-1且邊最終顔色為藍色的最短路徑
        for(int i=0;i<2;i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }
        Queue<int[]> queue = new ArrayDeque<>(); // 隊列的每一項代表{邊顔色，節點}
        dist[0][0] = 0;
        dist[1][0] = 0;
        queue.offer(new int[]{0,0});
        queue.offer(new int[]{1,0});
        while(!queue.isEmpty()){
            int[] front = queue.poll();
            int x = front[0]; // 邊顔色
            int y = front[1]; // 節點
            for(int t:edge[1-x][y]) { // 周遊節點y相連的，與上一條邊顔色不同的所有點
                if(dist[1-x][t] != Integer.MAX_VALUE) // 已經到達過此點
                    continue;
                dist[1-x][t] = dist[x][y] + 1;
                queue.offer(new int[]{1-x, t});    
            }
        }
        int[] ans = new int[n];
        for(int i=0;i<n;i++) {
            ans[i] = Math.min(dist[0][i],dist[1][i]);
            if(ans[i]==Integer.MAX_VALUE)
                ans[i]=-1;
        }
        return ans;
    }
}