Shortest Paths Alternating Between Two Link Types
A network has two link types (say primary and backup), modeled as red and blue edges. A valid route must alternate link types at every hop. Find the shortest alternating route length from node 0 to every node.
Problem
You are given an integer n and two directed edge lists redEdges and blueEdges over nodes 0..n-1. Return an array answer where answer[i] is the length of the shortest path from node 0 to node i whose edge colors strictly alternate (red, blue, red, ...), or -1 if no such path exists.
Input
An integer n, a redEdges list, and a blueEdges list of [from, to] pairs.
Output
An array of n shortest alternating-path lengths.
Constraints
- 1 <= n <= 100
- 0 <= redEdges.length, blueEdges.length <= 400
- Parallel edges and self-loops are allowed.
Examples
Example 1
Input
n = 3, redEdges = [[0,1],[1,2]], blueEdges = []
Output
[0,1,-1]
0->1 is red; reaching 2 would need a blue edge after red, but none exists.
Example 2
Input
n = 3, redEdges = [[0,1]], blueEdges = [[2,1]]
Output
[0,1,-1]
Only node 1 is reachable with an alternating path.