1651. Every Distance in a Free-or-Paid Network
A network of n nodes is joined by two-way links, each either free or costing
1. Print the cheapest total cost from node 1 to EVERY node, in order, on one
line. Print -1 for a node that cannot be reached, and 0 for node 1 itself.
6 nodes
1 - 2 (0) 1 - 3 (1) 2 - 3 (0)
3 - 4 (1) 4 - 5 (0) 5 - 6 (1) -> 0 0 0 1 1 2
Node 3 costs nothing because 1 - 2 - 3 is free, even though the direct link
costs 1. Problem 1647 asked the same network for one number; this asks for the
whole array, which is what the search produces anyway.
## The four things that have to be said
directed? no. Every link works both ways.
self-loops? allowed, and always useless.
parallel links? allowed, at different prices, and the cheaper copy wins.
disconnected? allowed, and this is where the output shape earns its keep:
an unreachable node prints -1 while its neighbours print real
numbers, so -1 cannot be a sentinel inside the search.
When n is 1 the whole answer is the single number 0.
## What most people try first
Breadth-first search, because the weights look small. A queue orders vertices by EDGE COUNT, so it settles a node two free links away after a node one paid link away, and gets the array wrong in both directions. On the example it reports node 4 at 2 rather than 1.
The next instinct is Dijkstra with a heap, which is correct. The heap exists to answer "which queued node is nearest" over an arbitrary set of keys, and that is more than this problem ever asks: the frontier only ever holds two distinct distances.
## Why a deque suffices, and why no heap is needed
Hold the frontier in a double-ended queue and keep this invariant: the distances
inside it do not decrease from front to back, and they span at most two
consecutive values, d and d + 1.
dist[1] = 0, everything else infinite
deque holding node 1
while the deque is not empty:
u = pop from the FRONT
for each link (u, v, w):
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
push v on the FRONT if w == 0, else on the BACK
Pop u at distance d. A free link writes d, which is already the smallest
value in the deque, so it belongs at the front. A paid link writes d + 1,
already the largest, so it belongs at the back. Neither push can break the
ordering, so the front is always a true minimum and nothing is ever compared.
## The trap in the output
An unreachable node must print -1 while a node at genuine distance 0 prints
0, so the two must be distinguishable inside the search. Keep unreachable as a
separate infinite marker and turn it into -1 only when printing. Using -1
as the internal marker makes it look smaller than every real distance, and the
relaxation then treats unreachable nodes as the nearest ones.
## Cost
O(n + m) time, O(n) memory beyond the graph, against O(m log n) for the
heap. A distance is at most n - 1, below 50000 here, so a 32 bit integer
holds every value.
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 link between u and v costing w, where w is 0 or 1.
Output
Print n integers on one line separated by single spaces: the cheapest cost from node 1 to node 1, then to node 2, and so on, with -1 for any node that cannot be reached.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.