1658. A Handful of Free Rides
A rail network has n stations and m two-way lines, each with a fare. You
hold k free-ride vouchers, and each voucher pays the whole fare of one line,
whatever it costs. Print the least money needed to travel from station 1 to
station n, or -1 if it cannot be reached.
Vouchers may be left unused.
4 stations, 1 voucher
1 - 2 (10) 2 - 4 (10) 1 - 3 (1) 3 - 4 (1) -> 1
Take 1 - 2 - 4 and spend the voucher on one of its two fares of 10, paying
10; or take 1 - 3 - 4 and spend it on one of the fares of 1, paying 1. The
second is better, which is the point: the voucher does not make the expensive
route cheap enough to win.
## The four things that have to be said
directed? no. Every line may be ridden either way.
self-loops? allowed, and never worth a voucher.
parallel lines? allowed, at different fares.
unreachable? yes. If station n sits in another piece, no number of
vouchers helps, so print -1. When n is 1 the answer is 0 and
no voucher is spent.
## What most people try first
Run Dijkstra, then subtract the k largest fares on the route it found. That is
wrong because it optimises the wrong thing: the route the plain search picks is
the cheapest at FULL fare, and the best route with vouchers may be a different
one entirely. On the example it finds 1 - 3 - 4 at 2 and gets 1, which happens
to be right; change the cheap fares to 6 each and the plain search still finds
1 - 3 - 4 at 12, waives a 6 to get 6, while 1 - 2 - 4 with a voucher costs
10. Picking the route first and the vouchers second cannot see that.
The second instinct is to try every choice of which lines to waive. With m at
50000 and k at 20 that is not a method.
## The node of the search is a pair
Search the PRODUCT graph whose vertices are pairs (station, vouchers left),
with the second coordinate running from k down to 0. Its size is
n * (k + 1), which at the limits is 20000 * 21 = 420000 states.
for each line (u, v, w) and each level j:
pay the fare (u, j) -> (v, j) cost w
spend a voucher (u, j) -> (v, j - 1) cost 0, when j > 0
start (1, k)
answer the smallest distance over all states (n, j)
Every arc is non-negative, so Dijkstra is correct on the product graph as it
stands. The answer takes the minimum over every j because leaving vouchers
unspent is allowed and costs nothing.
## Why the levels only ever go down, and why that matters
A voucher is never regained, so the second coordinate is non-increasing along
any route. The product graph is therefore k + 1 stacked copies of the network
with free arcs pointing from each copy to the one below, and none pointing back
up. That is what makes the state small: there is no need to remember WHICH lines
were waived, only how many vouchers remain.
## Overflow, computed rather than assumed
The product graph has n * (k + 1) = 420000 states, so a cheapest route uses at
most 419999 paid lines, each up to 10^9. The total can reach roughly
4 * 10^14, far past the 2147483647 a signed 32 bit integer holds, so the
distances need 64 bits. A single fare of 10^9 fits in 32 bits without
difficulty.
## Cost
O(m * k * log(n * k)) time and O(n * k) memory, about 2 * 10^7 heap
operations at the limits.
Constraints - `1 ≤ n ≤ 20000` - `0 ≤ m ≤ 50000` - `0 ≤ k ≤ 20` - `1 ≤ u, v ≤ n` - `0 ≤ w ≤ 1000000000`
Input
The first line contains three integers n, m and k.
Each of the next m lines contains three integers u, v and w: a two-way line between u and v with fare w.
Output
Print one integer, the least money needed to travel from station 1 to station n using at most k free-ride vouchers, or -1 if station n cannot be reached.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.