All problems

Minimum Cost to Reach Destination in Time

Hard · shortest path

A road map has n towns, numbered 0 to n - 1, where n is the length of the list tolls. The two-way roads are given as a list roads of triples [a, b, minutes]: a road between towns a and b that takes minutes minutes to drive.

You start in town 0 at minute 0 and want to reach town n - 1 no later than minute deadline. Every time you are in a town, including the first and the last one, you pay that town's toll, tolls[i] for town i. If you drive through the same town twice, you pay its toll twice.

Return the smallest total toll you can pay on a trip that arrives at town n - 1 within deadline minutes. If no trip arrives in time, return -1.

Several roads may join the same pair of towns, with different times. No road joins a town to itself.

Examples

Example 1

Input: deadline = 12, roads = [[0, 1, 5], [1, 2, 5], [0, 2, 11]], tolls = [2, 3, 4]

Output: 6

The direct road takes 11 minutes and pays towns 0 and 2: 2 + 4 = 6. Going through town 1 takes 10 minutes but pays 2 + 3 + 4 = 9.

Example 2

Input: deadline = 10, roads = [[0, 1, 5], [1, 2, 5], [0, 2, 11]], tolls = [2, 3, 4]

Output: 9

The direct road is now too slow (11 minutes), so the only trip in time goes through town 1.

Example 3

Input: deadline = 9, roads = [[0, 1, 5], [1, 2, 5], [0, 2, 11]], tolls = [2, 3, 4]

Output: -1

Every trip takes at least 10 minutes.

Constraints