1659. Changing Between Road and Rail

A network has n towns and m two-way legs. Each leg is either ROAD (type 0) or RAIL (type 1) and takes w minutes. Changing between road and rail at a town costs an extra s minutes. The very first leg of a journey costs no change, whichever type it is.

Print the least total minutes from town 1 to town n, or -1 if it cannot be reached.

4 towns, change costs 5 1 - 2 road (1) 2 - 3 rail (1) 3 - 4 road (1) 1 - 4 road (9) -> 9

The three-leg route takes 3 minutes of travel and two changes of 5, for 13. The single road leg takes 9 and changes nothing, so 9 wins.

## The four things that have to be said

directed? no. Every leg may be travelled either way, keeping its type. self-loops? allowed, and only ever a way to waste a change. parallel legs? allowed, including the same pair joined by road and by rail at different times, which is exactly the interesting case. unreachable? yes. If town n sits in another piece, print -1. When n is 1 the answer is 0 and no leg is taken.

## What most people try first

Dijkstra over the towns, with the change fee folded into the leg weight. There is nowhere to fold it: the fee depends on what you arrived by, which the town does not record. A cheap arrival by rail and a dearer arrival by road are not interchangeable when the next leg is a road.

The second instinct is to run two separate searches, one over road legs only and one over rail legs only, and combine them. That answers a different question, because a journey may change type several times.

## The node of the search is a pair

Search the PRODUCT graph whose vertices are pairs (town, type of the last leg) with the second coordinate taking three values: 0 for road, 1 for rail, and 2 for "nothing travelled yet". Its size is 3 * n, which is 60000 states at the limits.

for each leg (u, v, t, w) and each last value L: extra = s when L is 0 or 1 and L != t extra = 0 when L is 2, because the first leg is never charged arc (u, L) -> (v, t) of cost w + extra arc (v, L) -> (u, t) of cost w + extra start (1, 2) answer the smallest distance over the three states (n, 0), (n, 1), (n, 2)

The third value exists only to make the first leg free, and is left behind the moment any leg is taken, so no arc ever leads back into it.

## Why the fee belongs on the arc and not on the vertex

A change does not happen at a town; it happens between two legs. Charging it on arrival would charge a journey that ends there, and charging it on departure without knowing what you arrived by is the error the pair state removes. Putting it on the arc, decided by the pair (last type, this type), is the only place where both pieces of information are present at once.

Every arc cost is non-negative, since w and s are, so Dijkstra is correct on the product graph unchanged.

## Overflow, computed rather than assumed

The product graph has 3n = 60000 states, so a cheapest journey takes at most 59999 legs. A single arc costs w + s, at most 2000000000, and that still fits in a signed 32 bit integer, whose limit is 2147483647. It is the ACCUMULATION that does not: 59999 arcs of two billion reach about 1.2 * 10^14, so the distance array needs 64 bits while the arc weights would not.

## Cost

O(m log n) with a constant factor of three for the layers, and O(n) memory.

Constraints - `1 ≤ n ≤ 20000` - `0 ≤ m ≤ 50000` - `0 ≤ s ≤ 1000000000` - `t` is 0 or 1 - `0 ≤ w ≤ 1000000000`