All problems

Exact Ride Pass

Medium · shortest path

A mountain resort sells a grand tour pass. It lets you ride cable cars, but the pass is only stamped as complete when you have taken exactly k rides, no more and no fewer.

The resort has n stations, numbered 0 to n - 1. Each entry of rides is [a, b, fee]: a one-way cable car from station a to station b that costs fee each time you board it. You may ride the same cable car as many times as you like, and visit a station more than once.

You start at station 0 (the valley) and your k-th ride must end at station n - 1 (the summit). Return the smallest total fee you can pay, or -1 if no tour of exactly k rides ends at the summit.

Several cable cars may run between the same two stations, with different fees.

Examples

Example 1

Input: n = 3, rides = [[0, 1, 4], [1, 2, 3], [0, 2, 10], [2, 0, 1]], k = 2

Output: 7

Two rides ending at station 2: through station 1 for 4 + 3 = 7. The direct car would need a second ride out of station 2 and would not end there.

Example 2

Input: n = 3, rides = [[0, 1, 4], [1, 2, 3], [0, 2, 10], [2, 0, 1]], k = 3

Output: 21

Exactly three rides ending at station 2: 0 to 2 (10), back to 0 (1), then 0 to 2 again (10), for 21.

Example 3

Input: n = 2, rides = [[0, 1, 5]], k = 2

Output: -1

After reaching station 1 there is no cable car to ride, so a second ride is impossible.

Constraints