Cheapest fare with at most k stops
There are n cities numbered 0 to n − 1. Each triple
[from, to, price] in flights is a one-way flight. Return the cheapest total price from
src to dst using at most k stops (so at most k + 1 flights), or
−1 if no such route exists.
Examples
| Input | Output | Why |
|---|---|---|
n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1 | 700 | 0 → 1 → 3 costs 700. 0 → 1 → 2 → 3 costs 400 but needs two stops. |
n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1 | 200 | One stop is allowed. |
same flights, k = 0 | 500 | Only the direct flight. |
Constraints
- 1 ≤ n ≤ 100
- 0 ≤ flights.length ≤ n(n − 1)/2
- 1 ≤ price ≤ 10⁴
- 0 ≤ k < n
- src ≠ dst
Hints
Hint 1
Dijkstra keeps only the cheapest way to reach each city, but the cheapest way may use too many stops while a dearer one would leave room to continue.
Hint 2
After round i of Bellman–Ford, the distances are exact for routes of at most i flights. Run exactly k + 1 rounds.
Hint 3
Within a round, read only the distances from the previous round. Otherwise one round can chain two flights.
Where people lose marks
- Running k rounds instead of k + 1: k stops means k + 1 flights.
- Updating costs in place within a round, which lets one round use several flights.
- Running Dijkstra on cities alone and stopping when dst is popped.
Dry run on 4,[[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]],0,3,1
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 3
Before any flight: 0 costs 0, everything else ∞.
-
Step 2 / 3
Round 1 (routes of at most 1 flight), reading only round 0's costs: 1: 0 + 100 = 100.
-
Step 3 / 3
Round 2 (routes of at most 2 flights), reading only round 1's costs: 2: 100 + 100 = 200; 3: 100 + 600 = 700. After k + 1 = 2 rounds the answer is cost[3] = 700. The 400 route via 2 needs a third flight, which no round allowed.
How to think about it
The constraint is on the number of edges, which is exactly what Bellman–Ford's rounds count: after round
i, cost[v] is the cheapest price to reach v with at most i flights. So run k + 1 rounds and read
cost[dst].
One detail decides correctness. In the ordinary algorithm, updating distances in place during a round is harmless (it only speeds things up), but here it would let a round use two flights in a row if the edges happen to be listed in the right order. Each round must read a copy of the previous round's costs and write into a new array.
Plain Dijkstra fails: it settles each city at its cheapest price, discarding a dearer arrival that used fewer stops. Dijkstra over states (city, flights used) works too, at O(k · m log(k · n)).
Complexity. Time O(k · m) · Space O(n)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def cheapest_flight(n, flights, src, dst, k):
INF = float('inf')
cost = [INF] * n
cost[src] = 0
for _ in range(k + 1): # round i allows routes of at most i flights
nxt = cost[:] # read last round, write this one
for u, v, p in flights:
if cost[u] + p < nxt[v]:
nxt[v] = cost[u] + p
cost = nxt
return -1 if cost[dst] == INF else cost[dst]#include <climits>
#include <vector>
int solve(int n, const std::vector<std::vector<int>>& flights, int src, int dst, int k) {
const long long INF = LLONG_MAX / 4;
std::vector<long long> cost(n, INF);
cost[src] = 0;
for (int round = 0; round <= k; ++round) { // k + 1 rounds
std::vector<long long> next = cost; // read last round, write this one
for (const auto& f : flights)
if (cost[f[0]] + f[2] < next[f[1]]) next[f[1]] = cost[f[0]] + f[2];
cost = next;
}
return cost[dst] >= INF ? -1 : (int)cost[dst];
}class Solution {
public int cheapestFlight(int n, int[][] flights, int src, int dst, int k) {
final long INF = Long.MAX_VALUE / 4;
long[] cost = new long[n];
java.util.Arrays.fill(cost, INF);
cost[src] = 0;
for (int round = 0; round <= k; round++) { // k + 1 rounds
long[] next = cost.clone(); // read last round, write this one
for (int[] f : flights)
if (cost[f[0]] + f[2] < next[f[1]]) next[f[1]] = cost[f[0]] + f[2];
cost = next;
}
return cost[dst] >= INF ? -1 : (int) cost[dst];
}
}function cheapestFlight(n, flights, src, dst, k) {
let cost = new Array(n).fill(Infinity);
cost[src] = 0;
for (let round = 0; round <= k; round++) { // k + 1 rounds: at most k + 1 flights
const next = cost.slice(); // read last round, write this one
for (const [u, v, p] of flights) if (cost[u] + p < next[v]) next[v] = cost[u] + p;
cost = next;
}
return cost[dst] === Infinity ? -1 : cost[dst];
}fn solve(n: i64, flights: &[[i64; 3]], src: i64, dst: i64, k: i64) -> i64 {
const INF: i64 = i64::MAX / 4;
let mut cost = vec![INF; n as usize];
cost[src as usize] = 0;
for _ in 0..=k { // k + 1 rounds
let mut next = cost.clone(); // read last round, write this one
for f in flights {
let (u, v, p) = (f[0] as usize, f[1] as usize, f[2]);
if cost[u] + p < next[v] {
next[v] = cost[u] + p;
}
}
cost = next;
}
if cost[dst as usize] >= INF { -1 } else { cost[dst as usize] }
}import Data.List (foldl')
import qualified Data.Map.Strict as M
solve :: Int -> [[Int]] -> Int -> Int -> Int -> Int
solve _ flights src dst k = maybe (-1) id (M.lookup dst final)
where
-- a map from city to cost; absent means not reachable yet
final = iterate oneRound (M.singleton src 0) !! (k + 1)
oneRound cost = foldl' (step cost) cost flights -- read cost, write into the copy
step cost next [u, v, p] = case M.lookup u cost of
Just cu | maybe True (cu + p <) (M.lookup v next) -> M.insert v (cu + p) next
_ -> nextVariants to try
- Return the route itself, by storing a predecessor per round.
- Each stop also has a fee: add it to the price of every flight out of the stop city.
- Minimise the number of stops among the cheapest routes (compare pairs (price, stops)).
Next problems
Shortest distances from one node
Return the shortest distance from a source to every node of a weighted directed graph: Dijkstra's algorithm with a heap.
Open the problem → Medium25 minTime for a signal to reach every node
Breadth-first search counts edges; when edges have travel times, a heap settles the nearest node first.
Open the problem → Medium20 minShortest distances with negative edges
Return the shortest distance from a source to every node when weights can be negative, or report a negative cycle the source can reach.
Open the problem →Write a solution and run it against the real test table.
Keep going
Shortest distances from one node
Return the shortest distance from a source to every node of a weighted directed graph: Dijkstra's algorithm with a heap.
Open the problem → Medium25 minTime for a signal to reach every node
Breadth-first search counts edges; when edges have travel times, a heap settles the nearest node first.
Open the problem → Medium20 minShortest distances with negative edges
Return the shortest distance from a source to every node when weights can be negative, or report a negative cycle the source can reach.
Open the problem → GraphsThe pattern behind it
Grids, networks and dependencies are all graphs. Breadth-first search finds shortest paths, depth-first search and union-find find what is connected, Dijkstra handles weighted edges, and a queue of nodes with no remaining prerequisites gives an order.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.