114. Cheapest Flights Within K Stops
Find the cheapest route whose number of intermediate stops does not exceed k. A route with one flight has no intermediate stop, and a route with two flights has one.
A cheap route using too many flights is invalid. Track the stop restriction independently of total price, including the source-equals-destination case.
Example 1
Input
n=3, edges=[[0,1,1],[1,2,1],[0,2,8]], source=0, target=2, k=0
Output
8
Explanation: One allowed flight excludes the cheaper two-flight route.
Example 2
Input
Same flights, k=1
Output
2
Explanation: One intermediate stop admits 0→1→2.
Example 3
Input
source=target, any nonnegative k
Output
0
Explanation: The empty route wins or ties because all prices are nonnegative.
Constraints
1 <= n <= 10000 <= edges.length <= 104edges[i].length == 30 <= source, target, edge endpoint < n0 <= price, k <= 231 - 1
Hints
Hint 1
Count flights rather than stops and define a budget-indexed distance.
Hint 2
How can a whole round guarantee it adds at most one edge?
Hint 3
Clone the old layer, read only that layer for every relaxation, and cap the nonnegative budget at n−1.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
One stop limit separates frozen reads from tentative writes
3
[[0,1,1],[1,2,1],[0,2,8]]
0
2
0
8