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).

Follow-up (the grid variant, LC 1293)

An m × n grid of 0s and 1s; you may walk through at most k obstacles. Minimum steps corner to corner — every step costs 1, so plain BFS over (r, c, obstaclesUsed) states; and when k >= m + n − 3 the answer is just the Manhattan distance.