Weighted route state
A cheap route may use more legs than an expensive one. Breadth-first distance alone can't compare different edge costs. Keep tentative route costs and repeatedly finalize the smallest unsettled cost. Relaxation checks whether a new route improves a neighbor; first discovery is only tentative. Zero-cost edges are valid when the task permits them.
Some routes also spend a resource. A station reached with a spare waiver differs from the same station reached after spending it. A transfer cap requires separate cost layers so one update can't accidentally use several new legs. When counting cheapest routes, retain both distance and count, replacing counts on improvements and adding them on ties. State what your distance means before coding. The exercises use bounded networks so both dense scans and heap-based implementations are practical.
legs = [[0,1,9], [0,2,2], [2,1,1], [1,3,3]]
cheapest route: 0 -> 2 -> 1 -> 3
cost = 2 + 1 + 3 = 6
fewest-leg route: 0 -> 1 -> 3, cost 12
The route with the fewest legs is more expensive.