All problems

Electric Van Charging

Hard · shortest path

A delivery van drives between n towns, numbered 0 to n - 1. Each road is given as [a, b, km]: it joins towns a and b in both directions and is km kilometres long. There may be several roads between the same two towns.

The van is electric. Its battery holds at most capacity units of charge, and every kilometre driven uses one unit. The van can only start a road if it has at least km units in the battery.

Every town has a charging point. In town i you can buy as many whole units as you like for prices[i] each, as long as the battery never holds more than capacity units. Charge that is left over at the end is worth nothing.

The van starts in town 0 with an empty battery and has to reach town n - 1. It may pass through a town, or use a road, as many times as it likes.

Return the smallest total amount of money that has to be spent on charging, or -1 if the van cannot get there.

Examples

Example 1

Input: n = 3, roads = [[0, 1, 2], [1, 2, 2]], prices = [3, 1, 5], capacity = 4

Output: 8

Buy 2 units in town 0 for 6, drive to town 1, buy 2 more there for 2, and drive on to town 2.

Example 2

Input: n = 4, roads = [[0, 1, 3], [1, 2, 3], [2, 3, 3]], prices = [4, 2, 6, 1], capacity = 5

Output: 28

Example 3

Input: n = 3, roads = [[0, 1, 4], [1, 2, 1]], prices = [1, 1, 1], capacity = 3

Output: -1

The first road is 4 km long, but the battery only holds 3 units, so the van can never drive it.

Constraints