Cheapest Trip Under Deadline
HardAdvanced Graphs
Problem
A traveller crosses n cities joined by two-way roads roads[i] = [u, v, minutes]. Every time they enter a city (including the start city 0 and the destination n - 1) they pay that city's entry fee fees[city].
Return the minimum total fee to travel from city 0 to city n - 1 within at most maxTime minutes, or -1 if that is impossible. Cities may be revisited (paying again).
Example 1
- Input:
- n = 4, roads = [[0,1,10],[1,3,10],[0,2,1],[2,3,1]], fees = [1,1,10,1], maxTime = 25
- Output:
- 3
0 → 1 → 3 takes 20 minutes and costs 1 + 1 + 1 = 3.
Example 2
- Input:
- same roads and fees, maxTime = 15
- Output:
- 12
Only 0 → 2 → 3 (2 minutes, fee 12) fits.
Example 3
- Input:
- same roads and fees, maxTime = 1
- Output:
- -1
Constraints
- 2 ≤ n ≤ 1000
- 1 ≤ roads.length ≤ 2000
- 1 ≤ minutes ≤ 1000
- 1 ≤ maxTime ≤ 1000
- 1 ≤ fees[i] ≤ 1000
Hint
Show the first hint
There are two quantities: fee (to minimise) and time (to keep under a limit). A single distance per city is not enough.
Walkthrough
How to approach it
01Clarify before coding
- Is the start city's fee paid? Yes, and the destination's too.
- Can cities be revisited? Yes, paying again, which never helps but must not break the algorithm.
- Is time a hard limit? Yes, total minutes ≤ maxTime.
02Brute force
DP over time: best[t][v] = minimum fee to be at v at exactly time t, filled for t = 0..maxTime.
Cost: O(maxTime · E) ≈ 10^3 · 2·10^3 = 2·10^6: actually fine here, and a good fallback; the Dijkstra version below skips most dominated states.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.