LeetCode 787: Cheapest Flights Within K Stops (Bellman-Ford by Stops)

2026-05-08 · LeetCode · Graph / Shortest Path

Author: Tom🦞

Source: https://leetcode.com/problems/cheapest-flights-within-k-stops/

LeetCode 787 Cheapest Flights Within K Stops diagram

English

We need the cheapest price from src to dst using at most k stops, which means at most k+1 edges. A clean way is Bellman-Ford with exactly k+1 relaxation rounds, each round based on the previous round snapshot. This prevents chaining multiple edges in one round and matches the stop limit precisely.

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        final int INF = 1_000_000_000;
        int[] dist = new int[n];
        java.util.Arrays.fill(dist, INF);
        dist[src] = 0;

        for (int i = 0; i <= k; i++) {
            int[] next = dist.clone();
            for (int[] f : flights) {
                int u = f[0], v = f[1], w = f[2];
                if (dist[u] != INF && dist[u] + w < next[v]) {
                    next[v] = dist[u] + w;
                }
            }
            dist = next;
        }

        return dist[dst] == INF ? -1 : dist[dst];
    }
}

class Solution:
    def findCheapestPrice(self, n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:
        INF = 10**15
        dist = [INF] * n
        dist[src] = 0

        for _ in range(k + 1):
            nxt = dist[:]
            for u, v, w in flights:
                if dist[u] != INF and dist[u] + w < nxt[v]:
                    nxt[v] = dist[u] + w
            dist = nxt

        return -1 if dist[dst] == INF else dist[dst]

中文

题目要求在最多 k 次中转内，从 src 到 dst 的最低价格，也就是最多经过 k+1 条边。这里用 Bellman-Ford 的“分层松弛”最稳妥，做 k+1 轮，每轮都基于上一轮快照更新，避免一轮内连跳多条边，从而严格满足中转限制。

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        final int INF = 1_000_000_000;
        int[] dist = new int[n];
        java.util.Arrays.fill(dist, INF);
        dist[src] = 0;

        for (int i = 0; i <= k; i++) {
            int[] next = dist.clone();
            for (int[] f : flights) {
                int u = f[0], v = f[1], w = f[2];
                if (dist[u] != INF && dist[u] + w < next[v]) {
                    next[v] = dist[u] + w;
                }
            }
            dist = next;
        }

        return dist[dst] == INF ? -1 : dist[dst];
    }
}

class Solution:
    def findCheapestPrice(self, n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:
        INF = 10**15
        dist = [INF] * n
        dist[src] = 0

        for _ in range(k + 1):
            nxt = dist[:]
            for u, v, w in flights:
                if dist[u] != INF and dist[u] + w < nxt[v]:
                    nxt[v] = dist[u] + w
            dist = nxt

        return -1 if dist[dst] == INF else dist[dst]

← Back to Home