All problems

Driver Hours Haulage

Hard · shortest path

A lorry driver has to deliver a load across a region with n towns, numbered 0 to n - 1. Each entry of roads is [a, b, minutes]: a two-way road between towns a and b that takes minutes to drive.

Driving rules say the driver may never have more than limit minutes of driving in a row. The clock starts at 0 when the lorry leaves town 0, and a road can only be started if the clock plus its minutes stays at most limit (the road is driven in one go, with no stopping half-way).

A break resets the clock to 0 and takes pause minutes. A break can only be taken in a town where rest_area[i] is 1. You can take a break each time you are in such a town, as often as you like, and the time counts towards the total.

The lorry starts in town 0 with the clock at 0 and must reach town n - 1. Return the fewest total minutes (driving plus breaks) needed, or -1 if the driver cannot get there without breaking the rules. If n is 1, the lorry is already there, so return 0.

Roads may be driven more than once, and several roads may join the same two towns.

Examples

Example 1

Input: n = 3, roads = [[0, 1, 6], [1, 2, 6]], rest_area = [0, 1, 0], limit = 10, pause = 3

Output: 15

Driving both roads in a row needs 12 minutes, over the limit. Drive 6, take a break in town 1 for 3, then drive 6 more: 15.

Example 2

Input: n = 3, roads = [[0, 1, 6], [1, 2, 6]], rest_area = [0, 0, 0], limit = 10, pause = 3

Output: -1

There is nowhere to take a break, so the second road can never be started.

Example 3

Input: n = 4, roads = [[0, 1, 5], [1, 2, 5], [2, 3, 5], [0, 3, 14]], rest_area = [0, 1, 0, 0], limit = 12, pause = 2

Output: 17

The direct road takes 14, more than the limit. Via the towns: drive 5, break for 2 in town 1, then drive 5 + 5, for 17.

Constraints