Shortest Path in Color-Flipping Directed Graph
You are given a directed graph with n vertices labeled from 0 to n - 1, and a list of directed edges.
Each edge is represented as [u, v, c], indicating an initial directed edge from vertex u to vertex v with color c (where 0 <= c < C).
Initially, all edges point in their default directions.
Whenever you traverse an edge of color c:
- You move to the destination vertex.
- Every edge in the graph with color
creverses its direction (an edge currently directed $x \to y$ becomes directed $y \to x$, and vice versa).
Find the minimum number of edge traversals required to travel from vertex start to vertex target. If target is unreachable from start, return -1.
[ "4", "[[0, 1, 0], [1, 0, 1], [0, 2, 1], [2, 3, 0]]", "0", "3" ]
Explanation. From node 0, traverse edge [0, 2, 1] to reach node 2. Color 1 flips. At node 2, color 0 is still in its initial direction, so edge [2, 3, 0] is active. Traverse it to reach node 3 in 2 steps.
[ "4", "[[0, 1, 0], [1, 2, 1], [2, 3, 0]]", "0", "3" ]
Explanation. Traversing [0, 1, 0] flips color 0. Consequently, edge [2, 3, 0] becomes directed from 3 to 2, making node 3 unreachable.
[ "3", "[[0, 1, 0], [1, 2, 0]]", "1", "1" ]
Explanation. The start node is already the target node, so 0 steps are needed.
[ "4", "[[0, 1, 0], [1, 2, 1], [1, 2, 0], [1, 3, 0]]", "0", "3" ]
Explanation. Node 3 requires color 0 to be unflipped when leaving node 1. The shortest path is 0 -> 1 (flips c0), 1 -> 2 (flips c1), 2 -> 1 (flips c0 back), and 1 -> 3 (flips c0 again), taking 4 steps in total.
[ "5", "[[0, 1, 0], [1, 2, 1], [2, 3, 2], [2, 3, 0], [2, 4, 0]]", "0", "4" ]
Explanation. Path 0 -> 1 -> 2 -> 3 -> 2 -> 4 toggles color states across steps, allowing edge [2, 4, 0] to be traversed when color 0 is unflipped at step 4.
Follow-up: If each edge also had a positive integer weight w and we sought the minimum total weight path instead of minimum steps, how would the solution change? (Hint: Replace BFS with Dijkstra's algorithm over the implicit state space).
1 <= n <= 1000 0 <= edges.length <= 2000 Each edge is represented as [u, v, c] with 0 <= u, v < n and 0 <= c <= 7. 0 <= start, target < n