Asked at
Cheapest Flights Within K Stops
MediumVerifiedDijkstraBFSDynamic Programming~25 min
You have n cities connected by directed flights, each flights[i] = [from, to, price]. Find the cheapest price from src to dst using at most k stops (so at most k + 1 flights).
Return the cheapest price, or -1 if no such route exists.
The input arrives as a single object { n, flights, src, dst, k }.
Examples
in{ n: 3, flights: [[0,1,100],[1,2,100],[0,2,500]], src: 0, dst: 2, k: 1 }
out200
Two hops 0→1→2 cost 200, within one stop.
in{ n: 3, flights: [[0,1,100],[1,2,100],[0,2,500]], src: 0, dst: 2, k: 0 }
out500
With zero stops only the direct flight 0→2 qualifies.
Constraints
- 1 ≤ n ≤ 100
- Edges are directed: flights[i] = [from, to, price]
- 0 ≤ k < n
- 1 ≤ price ≤ 10⁴
Get help
🔑
Sign in to solve
Sign in to write, run, and submit your solution — and to pick up where your iOS flow left off.