---
# System prepended metadata

title: 1129. Shortest Path with Alternating Colors
tags: [Leetcode, BFS, Medium]

---

# 1129. Shortest Path with Alternating Colors
###### tags: `Leetcode` `Medium` `BFS`
Link: https://leetcode.com/problems/shortest-path-with-alternating-colors/description/
## Code
```java=
class Solution {
    public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        Set<Integer>[][] graph = new HashSet[n][2];
        int[][] res = new int[n][2];
        for(int i=1; i<n; i++){
            res[i][0] = Integer.MAX_VALUE;
            res[i][1] = Integer.MAX_VALUE;
        }
        for(int i=0; i<n; i++){
            graph[i][0] = new HashSet<>();
            graph[i][1] = new HashSet<>();
        }
        for(int[] edge:redEdges){ // add red edges
            graph[edge[0]][0].add(edge[1]);
        }
        for(int[] edge:blueEdges){ // add blue edges
            graph[edge[0]][1].add(edge[1]);
        }
        Queue<int[]> q = new LinkedList<>(); //index color
        q.add(new int[]{0,0});
        q.add(new int[]{0,1});
        while(!q.isEmpty()){
            int[] cur = q.poll();
            for(int next:graph[cur[0]][1-cur[1]]){
                if(res[next][1-cur[1]]==Integer.MAX_VALUE){
                    res[next][1-cur[1]] = 1+res[cur[0]][cur[1]];
                    q.add(new int[]{next, 1-cur[1]});
                }
            }
        }
        int[] ans = new int[n];
        for(int i=0; i<n; i++){
            int min = Math.min(res[i][0], res[i][1]);
            ans[i] = min==Integer.MAX_VALUE?-1:min;
        }
        return ans;
    }
}
```