Cheapest Route Within a Time Budget
A delivery network has cities connected by roads, each road taking some minutes to traverse. Passing through a city costs a per-city toll. Starting at city 0, reach city n-1 within maxTime minutes at the lowest total toll.
Problem
Given n cities (0..n-1), passingFees[i] (the toll charged each time you are at city i, including start and end), and bidirectional edges[j] = [u, v, time], find the minimum total toll to travel from city 0 to city n-1 such that the total travel time does not exceed maxTime. Return -1 if impossible.
Input
Integer maxTime, array edges of [u, v, time], and array passingFees of length n.
Output
An integer: minimum total passing fee, or -1 if unreachable in time.
Constraints
- 1 <= n <= 1000
- n - 1 <= edges.length <= 1000
- 1 <= maxTime <= 1000, 1 <= time <= 1000
- 1 <= passingFees[i] <= 1000
Examples
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
Route 0→1→2→5 takes 30 min and tolls 5+1+2+3 = 11.
Example 2
Input
maxTime = 29, edges = same as above, passingFees = same
Output
48
The 30-min route is now too slow; a costlier faster route is forced.