The Runner-Up Route — Solution & Editorial

Back to the Problem

Dijkstra with two distance slots per node (best and second-best distinct); relax both. Because walks may backtrack, the second value always propagates correctly.

Complexity: O(M log N)

Watch out: Strictly second: equal-length alternative paths do NOT count — the two slots must hold distinct values.