Cheapest Route — Solution & Editorial

Back to the Problem

Dijkstra with a binary heap; skip popped entries that are stale (distance already improved). Positive weights make it valid.

Complexity: O(M log N)

Watch out: Distances reach 2×10¹⁰ — use 64-bit distance values.