Roads with Switches
A city map is a directed graph. Every one-way road (u, v) has a switch and is currently OPEN (drivable) or CLOSED. You may flip closed roads open, each flip spending one of your allowed flips; open roads cost nothing.
minFlips(roads, src, dst) -> minimum flips to drive src -> dst,
or -1 if unreachable even with unlimited flips
canReach(roads, src, dst, k) -> minFlips is in [0, k]roads = [["A","B",true], ["B","C",false], ["A","D",false], ["D","C",false]] minFlips(roads, "A", "C") => 1 (A->B open, flip B->C) canReach(roads, "A", "C", 0) => false canReach(roads, "A", "C", 1) => true minFlips(roads, "C", "A") => -1 (roads are one-way) minFlips(roads, "A", "A") => 0
Up to 10^5 nodes and 10^6 roads; node ids are arbitrary; src or dst may appear on no road at all (then only src == dst is reachable). Expected O(V + E).
Hints
Hint 1
Weights are only 0 (open) and 1 (closed) — that is 0-1 BFS: a deque where 0-cost edges push front and 1-cost edges push back. Dijkstra with a heap also works, one log factor slower.
Hint 2
The deque invariant: distances popped are non-decreasing, so the first time dst pops, its flip count is final.
Hint 3
src == dst is 0 before any graph work — and ids missing from every road only reach themselves.