1655. Cheapest Tank of Fuel Across the Country
A country has n cities joined by m two-way roads. Road (u, v, L) burns
L units of fuel. City i sells fuel at price[i] per unit and will sell any
whole number of units.
A car starts at city 1 with an EMPTY tank, which holds at most cap units.
Print the least money needed to reach city n, or -1 if it cannot be reached.
3 cities, tank 5, prices 1 10 1
road 1 - 2 burns 3, road 2 - 3 burns 2 -> 5
Buy five units at city 1 for 5, drive to city 2 using three, drive to city 3 using the last two, and never pay city 2's price of 10.
## The four things that have to be said
directed? no. Every road may be driven either way.
self-loops? allowed. Driving one burns fuel and gains nothing.
parallel roads? allowed, at different lengths, and the shorter copy is the
one worth taking.
unreachable? yes, in two ways. City n may sit in another piece, or every
route to it may cross a road longer than the whole tank.
Print -1 for both. When n is 1 the answer is 0, with no fuel
bought at all.
## What most people try first
Dijkstra on the cities, using the price of the cheaper endpoint for each road. It is the natural move and it is wrong, because the state of the car is not its city. Two arrivals at the same city with different amounts of fuel left are not interchangeable: a car arriving nearly empty must buy here at whatever this city charges, and a car arriving full may drive straight past.
The second instinct, buying greedily at every cheap city, fails for the same reason in reverse: it cannot know how much to buy without knowing the road ahead, and the tank may not hold enough.
## The node of the search is a PAIR
Search the PRODUCT graph whose vertices are pairs (city, fuel), with fuel
running from 0 to cap. Its size is n * (cap + 1), which at the limits is
1000 * 101 = 101000 states, and it has two kinds of arc:
buy one unit (v, f) -> (v, f + 1) cost price[v], for f < cap
drive a road (u, f) -> (v, f - L) cost 0, for f >= L
Buying is where the money goes, and driving is free because the fuel was paid
for when it was bought. The question becomes an ordinary cheapest-route question
on this larger graph, from (1, 0) to any (n, f), and every arc cost is
non-negative, so Dijkstra is correct on it.
## Why buying one unit at a time is enough, and not a loss
It looks wasteful to model a purchase of forty units as forty arcs. It is not: any purchase is a run of single-unit arcs, their costs add to the same total, and Dijkstra never explores a state twice. Modelling "buy exactly the amount you will need" instead forces you to guess the road ahead, which is the mistake the pair state exists to remove.
## Cost
O((n * cap + m * cap) log(n * cap)), about 10^6 heap operations at the
limits. The money is bounded by the number of buy arcs on a route, at most
n * (cap + 1), times the highest price 1000, so about 10^8. That is inside
the 2147483647 a signed 32 bit integer holds, with room, though there is no cost
to using 64 bits.
Constraints - `1 ≤ n ≤ 1000` - `0 ≤ m ≤ 5000` - `1 ≤ cap ≤ 100` - `1 ≤ price[i] ≤ 1000` - `1 ≤ L ≤ 100`
Input
The first line contains three integers n, m and cap.
The second line contains n integers, the fuel price at each city.
Each of the next m lines contains three integers u, v and L: a two-way road between u and v burning L units of fuel.
Output
Print one integer, the least money needed to drive from city 1 to city n starting with an empty tank, or -1 if city n cannot be reached.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.