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 nodeaito nodebiin the graph.blueEdges[j] = [uj, vj]indicates that there is a directed blue edge from nodeujto nodevjin 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]Node 0 has distance 0, node 1 is reachable by one red edge, and node 2 cannot be reached with alternating edge colors.
Example 2
Input
n = 3, redEdges = [[0,1]], blueEdges = [[2,1]]Output
[0,1,-1]Node 1 is reachable from node 0 by one red edge, while node 2 is not reachable from node 0.
Constraints
- 1 <= n <= 100
- 0 <= redEdges.length, blueEdges.length <= 400
- redEdges[i].length == blueEdges[j].length == 2
- 0 <= ai, bi, uj, vj < n