Sweaty Imposter

Cheapest Flights Within K Stops

MediumGraph BFS/DFSNeetCode 150MidOpen on LeetCodeUpdated

There are n cities labeled 0 to n - 1, and flights[i] = [from, to, price] is a one-way flight. Given a source src, a destination dst, and an integer k, return the cheapest price from src to dst using at most k stops in between, or -1 if no such route exists.

Examples

n = 4, flights = [[0,1,50],[1,3,50],[0,2,20],[2,1,10],[0,3,200]], src = 0, dst = 3, k = 1 returns 100

0123

With one stop allowed, 0 to 1 to 3 costs 100. The cheaper route 0 to 2 to 1 to 3 needs two stops.

n = 4, flights = [[0,1,50],[1,3,50],[0,2,20],[2,1,10],[0,3,200]], src = 0, dst = 3, k = 2 returns 80

Two stops now allow 0 to 2 to 1 to 3 for 20 + 10 + 50 = 80.

n = 3, flights = [[0,1,10]], src = 0, dst = 2, k = 5 returns -1

No flight reaches city 2.

Constraints

  • 1 <= n <= 100
  • 0 <= flights.length <= n * (n - 1) / 2
  • 1 <= price <= 10^4
  • There are no repeated flights and no flight from a city to itself.
  • 0 <= src, dst, k < n and src != dst

Hints

Hint 1

Plain Dijkstra finds the cheapest route but ignores how many flights it takes. What does the stop limit translate to in edges?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

At most k stops means at most k + 1 flights, which is exactly what Bellman-Ford's rounds count. Keep prices, the cheapest known cost to each city, with prices[src] = 0. Run k + 1 rounds; in each, copy prices and relax every flight from the previous round's values into the copy. Reading from the old array ensures each round extends routes by exactly one flight. After the last round, prices[dst] is the answer, or -1 if it is still infinite. O(k * E) time and O(n) space.

Time

O(k * E)

Space

O(n)

Pitfall

Relaxing in place within a round. A city updated earlier in the same round can be used again right away, so a route takes several flights in one round and breaks the stop limit.

Solutions

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        final int INF = Integer.MAX_VALUE;
        int[] prices = new int[n];
        Arrays.fill(prices, INF);
        prices[src] = 0;
        for (int round = 0; round <= k; round++) {
            int[] next = prices.clone();
            for (int[] f : flights) {
                if (prices[f[0]] == INF) continue;
                next[f[1]] = Math.min(next[f[1]], prices[f[0]] + f[2]);
            }
            prices = next;
        }
        return prices[dst] == INF ? -1 : prices[dst];
    }
}
Drill This