Cheapest Route With Layovers
MediumAdvanced Graphs
Problem
An airline network has n airports. Each flights[i] = [from, to, price] is a one-way flight. A traveller wants to go from src to dst but refuses to make more than k layovers (intermediate airports).
Return the cheapest total price of such a trip, or -1 if no trip with at most k layovers exists.
Example 1
- Input:
- n = 4, flights = [[0,1,100],[1,2,100],[2,3,100],[0,2,500],[1,3,600]], src = 0, dst = 3, k = 1
- Output:
- 600
With one layover the options are 0→1→3 (700) and 0→2→3 (600). The 300 route needs two layovers.
Example 2
- Input:
- same flights, k = 2
- Output:
- 300
0 → 1 → 2 → 3 is now allowed.
Example 3
- Input:
- n = 3, flights = [[0,1,10]], src = 0, dst = 2, k = 5
- Output:
- -1
Constraints
- 2 ≤ n ≤ 100
- 0 ≤ flights.length ≤ n·(n - 1)
- 1 ≤ price ≤ 10^4
- 0 ≤ k < n
- src ≠ dst
Hint
Show the first hint
k layovers means at most k + 1 flights. Which shortest-path algorithm grows paths one edge at a time?
Walkthrough
How to approach it
01Clarify before coding
- Is k the number of flights or of intermediate stops? Intermediate stops, so at most k + 1 flights.
- Are prices positive? Yes, at least 1.
- Can flights repeat airports? Yes, but with positive prices that never helps.
02Brute force
DFS from src exploring every route up to k + 1 flights, keeping the cheapest that ends at dst.
Cost: O(d^(k+1)) for out-degree d: exponential in k.
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.