#1129

Shortest Path with Alternating Colors

specialist · 900 · lc medium +31 · verified · 47.8% accepted · 3,702 likes · top 33%

Description

You are given n nodes (labeled 0 to n - 1) in a directed graph. Edges are colored red or blue; self-edges and parallel edges are possible.

You are given redEdges[i] = [ai, bi] and blueEdges[j] = [uj, vj].

Return an array answer of length n where answer[x] is the length of the shortest alternating-color path from node 0 to node x, or -1 if no such path exists.

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]

Code

1

2

3

class Solution:
    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:

class Solution:
    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]: