Editorial for Just One More Tunnel (Easy)

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Every corridor and tunnel has nonnegative cost. Removing a cycle from a walk therefore cannot increase its cost, even when the cycle costs zero. Consequently, a shortest walk always has a simple path of the same or lower cost. We can use Dijkstra's algorithm without tracking which rooms have been visited along each candidate route.

Representing the Tunnels

Adding a tunnel between every pair of shortcut rooms would create up to $O(n^2)$ ~O(n^2)~ edges. Instead, introduce one auxiliary vertex $h$ ~h~. For each shortcut room $v$ ~v~, add two directed edges:

$v \to h$ ~v \to h~ with cost $t$ ~t~;
$h \to v$ ~h \to v~ with cost $0$ ~0~.

Keep each ordinary corridor as two directed edges of its original cost. Moving from one shortcut room to another through $h$ ~h~ costs exactly $t$ ~t~ in either direction. In particular, the tunnel cost must be charged only once, not on both edges.

Run Dijkstra from room $1$ ~1~. Print the distance to room $n$ ~n~, or Impossible if it is unreachable.

Correctness

Every valid route in the original graph gives a walk of the same cost in the auxiliary graph: replace each tunnel by its two edges through $h$ ~h~. Thus the shortest auxiliary distance cannot exceed the optimal route cost.

Conversely, take a shortest auxiliary walk. Every passage through $h$ ~h~ has the form $u \to h \to v$ ~u \to h \to v~ for shortcut rooms $u$ ~u~ and $v$ ~v~. When $u \neq v$ ~u \neq v~, replace it by the corresponding tunnel. When $u=v$ ~u=v~, discard the excursion; its cost is nonnegative. This gives a walk in the original graph of no greater cost. Remove repeated-vertex cycles to obtain a simple route, again without increasing the cost.

The two inequalities show that the shortest auxiliary distance is exactly the required answer. The same construction preserves reachability, so an unreachable finish is correctly reported as Impossible.

Complexity

The auxiliary graph has $n+1$ ~n+1~ vertices and at most $2m+2n$ ~2m+2n~ directed edges. Dijkstra with a binary heap takes $O((n+m)\log n)$ ~O((n+m)\log n)~ time and $O(n+m)$ ~O(n+m)~ memory. A 64-bit distance type and a sufficiently large infinity value are convenient.

The included sol.cpp also handles negative tunnel times using min-cost flow. It remains correct for this version, but the simpler Dijkstra solution above is sufficient.

Comments

There are no comments at the moment.