1129 Shortest Path with Alternating Colors

You are given an integer n, the number of nodes in a directed graph where the nodes are labeled from 0 to n - 1. Each edge is red or blue in this graph, and there could be self-edges and parallel edges.

You are given two arrays redEdges and blueEdges where:

  • redEdges[i] = [ai, bi] indicates that there is a directed red edge from node ai to node bi in the graph, and
  • blueEdges[j] = [uj, vj] indicates that there is a directed blue edge from node uj to node vj in the graph.

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 does not exist.

Example 1:

Input: n = 3, redEdges = [[0,1],[1,2]], blueEdges = []
Output: [0,1,-1]

Example 2:

Input: n = 3, redEdges = [[0,1]], blueEdges = [[2,1]]
Output: [0,1,-1]

Constraints:

  • 1 <= n <= 100
  • 0 <= redEdges.length, blueEdges.length <= 400
  • redEdges[i].length == blueEdges[j].length == 2
  • 0 <= ai, bi, uj, vj < n
 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
class Solution:
    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:
        graph = {
            1: defaultdict(set),    # red
            -1: defaultdict(set),   # blue
        }
        for se, ee in redEdges:
            graph[1][se].add(ee)
        for se, ee in blueEdges:
            graph[-1][se].add(ee)
    
        res = [-1] * n
        res[0] = 0
        queue = [(0, 1), (0, -1)]
        seen = set()
        path_len = 1
        while queue:
            temp_queue = []
            for node, color in queue:
                for child in graph[-color][node]:
                    if (node, child, -color) not in seen:
                        seen.add((node, child, -color))
                        if res[child] == -1 or path_len < res[child]:
                            res[child] = path_len
                        temp_queue.append((child, -color))
            queue = temp_queue
            path_len += 1
        return res