Free and Paid Roads — Solution & Editorial

Back to the Problem

0-1 BFS: a deque where 0-edges push front and 1-edges push back gives Dijkstra's guarantees in O(V + E) — no heap.

Complexity: O(N + M)

Watch out: A plain queue breaks optimality; the front/back discipline is the whole trick.