774. Cheapest Trip in Time
A courier starts in depot 0 and must arrive at depot n - 1, where n = fees.length, no later than minute maxTime. Each entry edges[i] = [x, y, minutes] is a two-way road between depots x and y that takes minutes to drive. Every time the courier arrives at a depot, including the starting depot at minute 0 and the final one, they pay that depot's parking fee fees[depot]; coming back to a depot means paying again.
Return the minimum total fee over all trips that finish within maxTime minutes (arriving at exactly maxTime is allowed), or -1 if no such trip exists. If n = 1 the answer is fees[0]. Parallel roads may exist.
Example 1
- Input:
- maxTime = 12edges = [[0,1,4],[1,2,5],[0,2,12],[2,3,3]]fees = [5,2,9,4]
- Output:
- 20
- Explanation:
Only the route 0-1-2-3 (4 + 5 + 3 = 12 minutes) fits, and it pays 5 + 2 + 9 + 4 = 20.
Example 2
- Input:
- maxTime = 15edges = [[0,1,4],[1,2,5],[0,2,12],[2,3,3]]fees = [5,2,9,4]
- Output:
- 18
- Explanation:
With 15 minutes the road 0-2 also fits (12 + 3 = 15) and skips depot 1's fee, so 5 + 9 + 4 = 18 beats 20.
Example 3
- Input:
- maxTime = 10edges = [[0,1,4],[1,2,5],[0,2,12],[2,3,3]]fees = [5,2,9,4]
- Output:
- -1
- Explanation:
The fastest way to depot 3 takes 12 minutes, which is more than 10, so no trip qualifies and the answer is -1.
Constraints
- 1 ≤ maxTime ≤ 1000
- 1 ≤ n = fees.length ≤ 1000
- 0 ≤ edges.length ≤ 1000
- 0 ≤ x, y < n, x ≠ y, and 1 ≤ minutes ≤ 1000
- 1 ≤ fees[i] ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,000 msC++ 250 msJava 500 msJavaScript 500 msTypeScript 500 ms
Expected complexity
- Time
- O(maxTime * E)
- Space
- O(maxTime * n)