1647. Roads That Are Free or Cost One Coin
Every road in a town is either free or costs one coin, and nothing else. Print
the smallest number of coins needed to travel from junction 1 to junction n,
or -1 if there is no route at all.
6 junctions
1 - 2 (1) 2 - 3 (0) 3 - 6 (1)
1 - 4 (0) 4 - 5 (0) 5 - 6 (1) 2 - 4 (1) -> 1
Walking 1 - 4 - 5 - 6 pays nothing for the first two roads and one coin for the last. The shorter-looking 1 - 2 - 3 - 6 pays two.
## The four things that have to be said
directed? no. Every road may be walked either way.
self-loops? allowed. A road from a junction to itself is never useful.
parallel roads? allowed, at different prices, and the cheaper copy wins.
disconnected? allowed. If junction n is in another piece, print -1.
When n is 1 you are already there, so the answer is 0.
## What most people try first
Dijkstra with a binary heap. That is correct, and it is the right instinct, and
it is also paying for something this problem does not need. A heap costs
O(log n) per operation to keep an arbitrary set of keys in order, while the
keys here only ever take two values and those two differ by one.
Plain breadth-first search is the other instinct, and it is wrong rather than slow. A queue finishes vertices in order of EDGE COUNT, and here a route of nine free roads beats a route of one paid road.
## A deque instead of a heap
Relax exactly as Dijkstra does, but hold the frontier in a double-ended queue:
dist[1] = 0, everything else infinite
push 1
while the deque is not empty:
u = pop from the FRONT
for each road (u, v, w):
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
if w == 0: push v on the FRONT
else: push v on the BACK
## Why that keeps the deque sorted, so no heap is needed
The invariant is that the distances inside the deque never decrease from front to
back, and that they span at most two consecutive values, d and d + 1.
Pop a vertex at distance d from the front. A free road from it writes d,
which belongs at the front because d is already the smallest value present. A
paid road writes d + 1, which belongs at the back because d + 1 is already
the largest value present. Neither push can break the ordering, so the front is
always a true minimum and no comparison is ever needed.
## Cost
O(n + m), against O(m log n) for the heap. The answer cannot exceed
n - 1 coins, which is below 50000 here, so every total fits in a 32 bit
integer with room to spare.
Constraints - `1 ≤ n ≤ 50000` - `0 ≤ m ≤ 100000` - `1 ≤ u, v ≤ n` - `w` is 0 or 1
Input
The first line contains two integers n and m.
Each of the next m lines contains three integers u, v and w: a two-way road between u and v costing w, where w is 0 or 1.
Output
Print one integer, the smallest number of coins on a route from junction 1 to junction n, or -1 if no route exists.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.