[Leetcode] Problem 1129 - Shortest Path with Alternating Colors

Posted on | In ,

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

No.1

Input: n = 3, red_edges = [[0,1],[1,2]], blue_edges = []

Output: [0,1,-1]

No.2

Input: n = 3, red_edges = [[0,1]], blue_edges = [[2,1]]

Output: [0,1,-1]

No.3

Input: n = 3, red_edges = [[1,0]], blue_edges = [[2,1]]

Output: [0,-1,-1]

No.4

Input: n = 3, red_edges = [[0,1]], blue_edges = [[1,2]]

Output: [0,1,2]

No.5

Input: n = 3, red_edges = [[0,1],[0,2]], blue_edges = [[1,0]]

Output: [0,1,1]

Note

  • 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

Code

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
42
43
44
45
public int[] shortestAlternatingPaths(int n, int[][] red_edges, int[][] blue_edges) {
    int[] result = new int[n];
    List<Integer>[][] graph = new ArrayList[2][n];
    boolean[][] visit = new boolean[2][n];
    Queue<int[]> queue = new LinkedList<>();
    // 0 = red, 1 = blue
    queue.offer(new int[] {0, 0});
    queue.offer(new int[] {0, 1});
    visit[0][0] = true;
    visit[1][0] = true;
    int path = 0;
    Arrays.fill(result, -1);

    for (int i = 0; i < n; i++) {
        graph[0][i] = new ArrayList<>();
        graph[1][i] = new ArrayList<>();
    }
    for (int[] red : red_edges)   
        graph[0][red[0]].add(red[1]);

    for (int[] blue : blue_edges)
        graph[1][blue[0]].add(blue[1]);

    while (!queue.isEmpty()) {
        int size = queue.size();

        for (int i = 0; i < size; i++) {
            int[] node = queue.poll();
            int idx = node[0];
            int color = node[1];
            result[idx] = result[idx] < 0 ? path : Math.min(path, result[idx]);
            
            for (int neighbor : graph[1 - color][node[0]]) {
                if (!visit[1 - color][neighbor]) {
                    visit[1 - color][neighbor] = true;
                    queue.offer(new int[] {neighbor, 1 - color});
                }
            }
        }

        path++;
    }

    return result;
}