#227MediumGraphs· Dijkstra over Expanded States

Discounted Tolls

A freight company plans a trip between depots numbered `0` to `n - 1`. Every road `[u, v, toll]` connects two depots in both directions and has a toll. The company owns `coupons` half-price coupons. A coupon can be used on **one road crossing**, and then that crossing costs `floor(toll / 2)`. At most one coupon is used per crossing, and unused coupons are simply wasted. Return the lowest total toll to drive from depot `0` to depot `n - 1`, or `-1` if no route exists. If `n` is 1 the trip is already over and costs 0.

Input format

`n`: number of depots; `roads`: array of `[u, v, toll]`; `coupons`: number of coupons.

Output format

An integer: the cheapest total toll, or -1.

Examples

Input: n = 4, roads = [[0, 1, 10], [1, 3, 10], [0, 2, 8], [2, 3, 30]], coupons = 1

Output: 15

Route 0-1-3 costs 20. Using the coupon on one of its tolls gives 10 + 5 = 15. Route 0-2-3 with the coupon on the 30 toll costs 8 + 15 = 23, so 15 wins.

Input: n = 3, roads = [[0, 1, 4], [1, 2, 6]], coupons = 0

Output: 10

With no coupons the only route costs 4 + 6 = 10.

Input: n = 3, roads = [[0, 1, 5]], coupons = 2

Output: -1

Depot 2 cannot be reached at all.

Constraints

1 <= n <= 10^4
0 <= roads.length <= 5 * 10^4
0 <= u, v < n, u != v
0 <= toll <= 10^4
0 <= coupons <= 10

#dijkstra
#graph
#heap
#state-expansion
#shortest-path