683. Minimum Cost to Reach Destination in Time

There are n cities (0 to n-1) connected by undirected roads edges = [u, v, time], and passingFees[i] is charged each time you are at city i (including the start and end). Starting at city 0, reach city n-1 with total travel time at most maxTime, minimizing the total fees. Return the minimum cost, or -1 if impossible. The input is JSON {maxTime, edges, passingFees}.

Input: JSON {maxTime, edges, passingFees}.

Output: Integer — the minimum cost, or -1.

Examples

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 cheaper path fits within the time limit.

Input: {"maxTime":9,"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: No path fits in time 9.

Input: {"maxTime":5,"edges":[[0,1,5]],"passingFees":[3,4]}
Output: 7
Explanation: 3 + 4 within time 5.

Constraints

• 2<=n<=1000
• 1<=maxTime<=1000

Asked by