Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. At most k stops means at most k + 1 flights.
  2. 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