Practice › Graphs
Cheapest Flights Within K Stops
Medium · Graphs · Asked at Amazon, Google, Airbnb, Microsoft
Each flight u v p goes from city u to city v for price p. Print the cheapest price from src to dst using at most k stops (k intermediate cities, i.e. at most k + 1 flights), or -1 if impossible.
Input
First line: n m. Next m lines: u v p. Last line: src dst k. Cities are 1..n.
Output
The cheapest price, or -1.
Constraints
- 1 ≤ n ≤ 100
- 0 ≤ m ≤ n(n−1)
- 1 ≤ p ≤ 10^4
- 0 ≤ k < n
Bellman-Ford limited to k + 1 rounds. In each round relax from a copy of the previous distances, so one round adds at most one flight.
Example 1
Input
4 5 1 2 100 2 3 100 3 1 100 2 4 600 3 4 200 1 4 1
Output
700
Example 2
Input
3 3 1 2 100 2 3 100 1 3 500 1 3 0
Output
500
Hints
- At most k stops means at most k + 1 flights.
- Run Bellman-Ford for k + 1 rounds only, and in each round relax using a copy of the previous round's prices so a round adds at most one flight.
Approach
price[src] = 0, others ∞. For round = 1..k+1: copy price into next; for every flight (u, v, p) with price[u] finite, next[v] = min(next[v], price[u] + p); then price = next. Reading from the old array is essential — updating in place could chain several flights within one round and exceed the stop limit. Plain Dijkstra on price is wrong here because a cheaper path may use too many stops.
Complexity: O(k · m) time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<array<long long, 3>> f(m);
for (auto &x : f) cin >> x[0] >> x[1] >> x[2];
int src, dst, k;
cin >> src >> dst >> k;
const long long INF = LLONG_MAX / 4;
vector<long long> price(n + 1, INF);
price[src] = 0;
for (int round = 0; round <= k; round++) {
vector<long long> next = price;
for (auto &x : f)
if (price[x[0]] != INF && price[x[0]] + x[2] < next[x[1]]) next[x[1]] = price[x[0]] + x[2];
price = next;
}
cout << (price[dst] == INF ? -1 : price[dst]) << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n, m = data[0], data[1]
f = [(data[2 + 3 * i], data[3 + 3 * i], data[4 + 3 * i]) for i in range(m)]
src, dst, k = data[2 + 3 * m : 5 + 3 * m]
INF = float("inf")
price = [INF] * (n + 1)
price[src] = 0
for _ in range(k + 1):
nxt = price[:]
for u, v, p in f:
if price[u] + p < nxt[v]:
nxt[v] = price[u] + p
price = nxt
print(-1 if price[dst] == INF else price[dst])Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
long[][] f = new long[m][3];
for (int i = 0; i < m; i++) for (int j = 0; j < 3; j++) f[i][j] = sc.nextLong();
int src = sc.nextInt(), dst = sc.nextInt(), k = sc.nextInt();
long INF = Long.MAX_VALUE / 4;
long[] price = new long[n + 1];
Arrays.fill(price, INF);
price[src] = 0;
for (int round = 0; round <= k; round++) {
long[] next = price.clone();
for (long[] x : f) {
int u = (int) x[0], v = (int) x[1];
if (price[u] != INF && price[u] + x[2] < next[v]) next[v] = price[u] + x[2];
}
price = next;
}
System.out.println(price[dst] == INF ? -1 : price[dst]);
}
}Solve Cheapest Flights Within K Stops online · All practice problems