You drive between n cities 0 .. n-1 along undirected roads roads[i] = [u, v, litres]:
driving the road uses exactly litres of fuel. Fuel costs price[c] per litre in city c, and
you may buy any whole number of litres there as long as the tank never holds more than cap
litres. You start in src with an empty tank.
Return the minimum amount of money needed to reach dst, or -1 if it is impossible.
Examples
Input: price = [3, 1, 5, 2], roads = [[0,1,2],[1,2,3],[2,3,1],[1,3,4],[0,2,4]],
cap = 5, src = 0, dst = 3
Output: 10
Explanation: buy 2 litres in city 0 (6), drive to 1, buy 4 litres (4), drive 1 -> 3.
Input: price = [1, 1], roads = [[0,1,5]], cap = 4, src = 0, dst = 1
Output: -1
Explanation: the road needs more fuel than the tank can hold.
Constraints
1 <= n <= 100,0 <= len(roads) <= 1000,1 <= cap <= 1000 <= litres <= 100,1 <= price[c] <= 100- Target
O(cap * (V + E) * log(cap * V))time.
Goals
- Model (city, fuel in tank) as a search state
- Split refuelling into 'buy one more litre' steps to keep transitions small
- Stop at the first time the destination is settled