Cheapest Flights Within K Stops
Medium · Advanced Graphs · Graph · Shortest Path · Dynamic Programming · Breadth-First Search
Problem
There are n cities numbered 0 to n - 1, connected by one-way flights. flights[i] = [from_i, to_i, price_i] is a flight from from_i to to_i costing price_i.
Given src, dst and k, return the cheapest total price to travel from src to dst using at most k intermediate stops, that is, at most k + 1 flights. If no such route exists, return -1.
Examples
Input: n = 4, flights = [[0,1,50],[1,2,50],[2,3,50],[0,3,200],[0,2,120]], src = 0, dst = 3, k = 1 Output: 170
0 → 2 → 3 costs 170 with one stop. The cheaper route 0 → 1 → 2 → 3 costs 150 but needs two stops.
Input: n = 4, flights = [[0,1,50],[1,2,50],[2,3,50],[0,3,200],[0,2,120]], src = 0, dst = 3, k = 2 Output: 150
With two stops the 150 route is allowed.
Input: n = 3, flights = [[0,1,10]], src = 0, dst = 2, k = 1 Output: -1
City 2 has no incoming flight.
Constraints
- 1 <= n <= 100
- 0 <= len(flights) <= n · (n - 1) / 2
- len(flights[i]) == 3
- 0 <= from_i, to_i < n, from_i != to_i
- 1 <= price_i <= 10^4
- There are no duplicate flights.
- 0 <= src, dst, k < n, src != dst
Approaches
- Baseline: try every route — time O(d^(k+1)) for out-degree d, space O(k) recursion
Follow-up
Dijkstra also works if the state is (city, flights used): pop the cheapest state, and do not expand it past k + 1 flights. It can be faster on sparse graphs, but a city may be settled once per flight count, so the bound is O(k · E log(k · E)). The rounds of Bellman-Ford give O(k · E) with no heap.
Related problems
Start free on Cariara · Coding problems · System design studio
