Cheapest Flights within K stops

2025-05-02

leetcode, cheapest-flights-within-k-stops

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [from(i), to(i), price(i)] indicates that there is a flight from city from(i) to city to(i) with cost price(i).

You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.

Example 1:

cheapest-flights-within-k-stops-1.png

Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Output: 700
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700.
Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.

Example 2:
cheapest-flights-within-k-stops-2.png

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 2 is marked in red and has cost 100 + 100 = 200.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        int[] cost = new int[n];
        Arrays.fill(cost, Integer.MAX_VALUE);
        cost[src] = 0;   

        for (int i = 0; i <= k; i++) {
            int[] temp = Arrays.copyOf(cost, n);
            for (int[] flight: flights) {
                int u = flight[0], v = flight[1], price = flight[2];
                if (cost[u] != Integer.MAX_VALUE) {
                    temp[v] = Math.min(temp[v], cost[u] + price);
                }
            }
            cost = temp;
        }     
        return cost[dst] == Integer.MAX_VALUE ? -1 : cost[dst];
    }
}