#1928
Minimum Cost to Reach Destination in Time
master · 1665 · lc hard +32 · verified · 41.2% accepted · 962 likes · top 21%
Description
There is a country of n cities (0 to n - 1) with bidirectional roads edges[i] = [xi, yi, timei]. Passing through any city costs the fee given by passingFees[city].
Starting from city 0, reach city n - 1 within maxTime minutes, paying fees at every visited city (including start and end).
Return the minimum total fee, or -1 if you cannot reach within the time limit.
Example 1:
Input: maxTime = 30, edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees = [5,1,2,20,20,3]
Output: 11
Explanation: The path to take is 0 -> 1 -> 2 -> 5, which takes 30 minutes and has $11 worth of passing fees.
Example 2:
Input: maxTime = 29, edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees = [5,1,2,20,20,3]
Output: 48
Explanation: The path to take is 0 -> 3 -> 4 -> 5, which takes 26 minutes and has $48 worth of passing fees.
You cannot take path 0 -> 1 -> 2 -> 5 since it would take too long.
Example 3:
Input: maxTime = 25, edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees = [5,1,2,20,20,3]
Output: -1
Explanation: There is no way to reach city 5 from city 0 within 25 minutes.
Code
1
2
3