[LeetCode] 787. Cheapest Flights Within K Stops

There are n cities connected by m flights. Each flight starts from city u and arrives at v with a price w.

Now given all the cities and flights, together with starting city src and the destination dst, your task is to find the cheapest price from src to dst with up to k stops. If there is no such route, output -1.

Example 1:
Input: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
Output: 200
Explanation: 
The graph looks like this:

The cheapest price from city 0 to city 2 with at most 1 stop costs 200, as marked red in the picture.

Example 2:
Input: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
Output: 500
Explanation: 
The graph looks like this:

The cheapest price from city 0 to city 2 with at most 0 stop costs 500, as marked blue in the picture.

Constraints:

• The number of nodes n will be in range [1, 100], with nodes labeled from 0 to n - 1.
• The size of flights will be in range [0, n * (n - 1) / 2].
• The format of each flight will be (src, dst, price).
• The price of each flight will be in the range [1, 10000].
• k is in the range of [0, n - 1].
• There will not be any duplicated flights or self cycles.

K站中转内最便宜的航班。

有 n 个城市通过 m 个航班连接。每个航班都从城市 u 开始，以价格 w 抵达 v。

现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到从 src 到 dst 最多经过 k 站中转的最便宜的价格。 如果没有这样的路线，则输出 -1。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cheapest-flights-within-k-stops
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路是经典的dijkstra算法。首先创建一个邻接矩阵，记录每两个城市之间的price。然后创建一个关于price的最小堆，把（目前所花费的cost，下一个要去到的城市，剩余步数）放入这个最小堆，同时一开始的时候放入的初始值是（0, 起点city, K + 1）。这样遍历的时候，每次从最小堆pop出来一个元素，查看这个元素的下一个遍历到的city是否是最终的dst，如果是，则返回price；如果不是，同时剩余步数 > 0的话，则遍历邻接表里面所有跟当前这个city有连通的部分，加入最小堆。

时间O(nlogn)

空间O(n^2)

Java实现

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        int[][] g = new int[n][n];
        for (int[] f : flights) {
            g[f[0]][f[1]] = f[2];
        }

        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        // <price, source, stop>
        // 因为K是允许中转的次数所以实际可以遍历到K + 1个城市
        queue.offer(new int[] { 0, src, K + 1 });
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int price = cur[0];
            int city = cur[1];
            int remainStops = cur[2];
            if (city == dst) {
                return price;
            }
            if (remainStops > 0) {
                for (int i = 0; i < n; i++) {
                    if (g[city][i] != 0) {
                        queue.offer(new int[] { price + g[city][i], i, remainStops - 1 });
                    }
                }
            }
        }
        return -1;
    }
}

Dijkstra类型题目

LeetCode 题目总结