Shortest Path With K Free Edges

You are given an undirected weighted graph with n nodes labeled from 1 to n. The normal weighted edges are given in edges, where each edge is [u, v, w].
You are also given a list of special edges called magical bridges. Each bridge is given as [u, v] and can be traversed with cost 0. You may use at most k magical bridge traversals in total.
Return the minimum cost required to travel from node 1 to node n. If it is not possible, return -1.

Function
shortestPathWithKFreeEdges(n: int, edges: int[][], bridges: int[][], k: int) → long

Examples
Example 1
n = 4
edges = [[1, 2, 10], [2, 4, 10], [1, 3, 5], [3, 4, 20]]
bridges = [[1, 4]]
k = 1
return = 0
Use the magical bridge directly from node 1 to node 4 with cost 0.
Example 2
n = 3
edges = [[1, 2, 5]]
bridges = []
k = 1
return = -1
Node 3 cannot be reached.

Constraints
The graph is undirected.
edges[i] = [u, v, w] describes a weighted edge.
bridges[i] = [u, v] describes a zero-cost magical bridge.
0 <= k

The trick is a layered state: (node, bridgesUsed). Run Dijkstra on that pair with a min-heap. From (u, j), a normal edge goes to (v, j) with cost w. A bridge goes to (v, j+1) with cost 0, only if j < k. Bridges are undirected like the rest of the graph, so add them both ways. Your distance table is n by (k+1). The answer is the minimum over all j of dist[n][j], or -1 if every entry is infinite. The common pitfall is keeping a single dist per node and pruning states that are worse in cost but better in bridges left. That prunes valid paths. Another miss is using int when the return type is long. Also handle k = 0, where bridges simply never get used. If the live OA freezes you on the state design, StealthCoder can supply the layered Dijkstra while you stay calm.

If you see this problem in your OA tomorrow, the play is to recognize the pattern in 30 seconds. StealthCoder buys you that recognition.