787. Cheapest Flights Within K Stops

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

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:

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:

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.

Example 3:

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

Constraints:

• 1 <= n <= 100
• 0 <= flights.length <= (n * (n - 1) / 2)
• flights[i].length == 3
• 0 <= fromi, toi < n
• fromi != toi
• 1 <= pricei <= 104
• There will not be any multiple flights between two cities.
• 0 <= src, dst, k < n
• src != dst

Solution:

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        // Initialize the distance array
        int[][] dist = new int[n][k + 2]; // 4, 1+2 =3
        /** 
                0 1 2
            0   - - -
            1   - - -
            2   - - - 
            3   - - -
         */
         // 将数组中的每一行都填充为无穷大 (表示初始时所有城市的最小成本未知)
        for (int[] row : dist){
            Arrays.fill(row, Integer.MAX_VALUE);
        }

        dist[src][0] = 0; // start: source city // 设置起点城市src在0次中转的成本为0
                /** 
                0 1 2
            0   0 0 -
            1   - - -
            2   - - - 
            3   - - -
         */
        // Iterate over the number of stops from 0 to k + 1
        // because allow k stops, so there will be k+ 1 edge
        // 从1次中转开始循环, 到(k+1)次中转为止
        for (int stops = 1; stops <= k + 1; stops++){
            // 在每一轮中转开始时, 将上一轮的成本拷贝到当前轮次
            for (int i = 0; i < n; i++){
                dist[i][stops] = dist[i][stops - 1];
                // dist[0][1] = dist[0][0] = 0
                // dist[1][1] = dist[1][0] = -
            }

            // 遍历所有的航班信息
            for (int[] flight : flights){
                // [0, 1, 100]
                int from = flight[0];//0
                int to = flight[1];//1
                int price = flight[2]; // 100
                if (dist[from][stops - 1] != Integer.MAX_VALUE){
                    // dist[0][0] = 0
                    dist[to][stops] = Math.min(dist[to][stops], dist[from][stops - 1] + price);
                    // dist[1][1] = Math.min(dist[1][1], dist[0][1] + 100);
                    // dist[1][1] = Math.min(-, 100)
                    // dist[1][1] = 100
                }
            }
        }

        // Find the minimum cost to reach dst with up to k + 1 stops
        int minCost = Integer.MAX_VALUE;
        for (int stops = 0; stops <= k + 1; stops++){
            minCost = Math.min(minCost, dist[dst][stops]);
        }

        return minCost == Integer.MAX_VALUE ? -1 : minCost;
    }
}

int[][] dist = new int[n][k + 2];

n: 数组的行数等于城市的数量, 每一行代表一个城市

k+2 : 需要考虑从0次中转到k+1次中转的情况