1129. Shortest Path with Alternating Colors

Problem Link

Description

---

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

Solution

---

Python3

class Solution:
    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:
        red, blue = defaultdict(list), defaultdict(list)
        queue = collections.deque()
        visited = set()
        res = [-1] * n
        res[0] = 0
        
        for x, y in redEdges:
            red[x].append(y)
            if x == 0:
                queue.append((y, 1, True))
        
        for x, y in blueEdges:
            blue[x].append(y)
            if x == 0:
                queue.append((y, 1, False))
        
        while queue:
            node, distance, isRed = queue.popleft()
            
            if res[node] == -1 or distance < res[node]:
                res[node] = distance
            
            if isRed:
                for nei in blue[node]:
                    p = (nei, True)
                    if p not in visited:
                        visited.add(p)
                        queue.append((nei, distance + 1, False))
            else:
                for nei in red[node]:
                    p = (nei, False)
                    if p not in visited:
                        visited.add(p)
                        queue.append((nei, distance + 1, True))
        
        return res