Cheapest Flights Within K Stops

Medium · Advanced Graphs

You are given the number of cities labeled 0 to n-1 and a list of flights, where each flight is [from, to, price] meaning a one-way route with that ticket price. Given a starting city, a destination city, and a maximum number of stops (layovers) allowed along the way, return the cheapest total price to travel from the start to the destination using at most that many stops. If there is no route within the stop limit, return -1.

Examples

Input:  n=4, flights=[[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src=0, dst=3, k=1
Output: 700
Why:    With at most 1 stop, the path 0->1->3 costs 100+600=700, which is cheaper than routes needing more stops.

Input:  n=3, flights=[[0,1,100],[1,2,100],[0,2,500]], src=0, dst=2, k=1
Output: 200
Why:    The direct-ish path 0->1->2 uses exactly 1 stop and costs 100+100=200, beating the direct flight priced at 500.

Input:  n=3, flights=[[0,1,100],[1,2,100],[0,2,500]], src=0, dst=2, k=0
Output: 500
Why:    With 0 stops allowed only the direct flight 0->2 is usable, costing 500.

Constraints

1 <= n <= 100, 0 <= flights.length <= n*(n-1)/2, 0 <= src, dst < n, src != dst, 0 <= k <= n-1, 1 <= price <= 10^4

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Cheapest Flights Within K Stops

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Cheapest Flights Within K Stops. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.