302. Cheapest Flights Within K Stops

Each Bellman-Ford round relaxes edges using distances from the previous round only. Running exactly k+1 rounds allows paths with at most k intermediate stops.

Bound the number of edges, not distance

'At most k stops' means at most k + 1 flights (edges). Bellman-Ford naturally limits path length by the number of relaxation rounds: after round r, prices[v] is the cheapest cost to v using at most r edges.

The key detail: each round must relax using the previous round's prices, so we relax into a temporary copy tmp. Otherwise a city updated earlier in the same round could be used again, sneaking in extra stops.

prices = [INF]*n; prices[src] = 0
repeat k+1 times:
    tmp = prices.copy()
    for (u, v, w) in flights:
        if prices[u] + w < tmp[v]: tmp[v] = prices[u] + w
    prices = tmp
return prices[dst] or -1

Worked example

n=4, flights as given, src=0, dst=3, k=1: with at most 1 stop the cheapest 0→3 is 0→1→3 = 700 (the 0→1→2→3 = 400 route needs 2 stops).

Complexity

• Time: O(k · E).
• Space: O(n).

import java.util.Arrays;

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        int INF = Integer.MAX_VALUE;
        int[] prices = new int[n];
        Arrays.fill(prices, INF);
        prices[src] = 0;
        for (int i = 0; i <= k; i++) {
            int[] tmp = prices.clone();
            for (int[] f : flights) {
                int u = f[0], v = f[1], w = f[2];
                if (prices[u] != INF && prices[u] + w < tmp[v]) {
                    tmp[v] = prices[u] + w;
                }
            }
            prices = tmp;
        }
        return prices[dst] == INF ? -1 : prices[dst];
    }
}