Medium

题目描述

有 n 个城市通过一些航班连接。给你一个数组 flights，其中 flights[i] = [fromi, toi, pricei] ，表示该航班都从城市 fromi 开始，到达城市 toi，费用为 pricei。

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

示例 1：

输入: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
输出: 700
解释:
城市航班图如上所示。
从城市 0 到城市 3 经过最多 1 次中转的最优路径用红色标出，费用为 100 + 600 = 700。
请注意，通过城市 [0,1,2,3] 的路径更便宜，但无效，因为它经过了 2 次中转。

示例 2：

输入: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
输出: 200
解释:
城市航班图如上所示。
从城市 0 到城市 2 经过最多 1 次中转的最优路径用红色标出，费用为 100 + 100 = 200。

示例 3：

输入: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
输出: 500
解释:
城市航班图如上所示。
从城市 0 到城市 2 不经过中转的最优路径用红色标出，费用为 500。

提示：

  • 2 <= n <= 100
  • 0 <= flights.length <= (n * (n - 1) / 2)
  • flights[i].length == 3
  • 0 <= fromi, toi < n
  • fromi != toi
  • 1 <= pricei <= 10^4
  • 两个城市之间不会有多条航班
  • 0 <= src, dst, k < n
  • src != dst

解题思路

解题思路

这是一个带约束的最短路径问题。我们需要在最多 K 次中转的限制下，找到从源点到目标点的最小花费。

方法1：动态规划 (推荐) 使用二维 DP，dp[i][j] 表示经过最多 i 次中转到达城市 j 的最小花费。状态转移方程为：

dp[i][to] = min(dp[i][to], dp[i-1][from] + price)

这里需要注意的是，为了避免在同一轮迭代中使用刚更新的值，需要使用临时数组。

方法2：Dijkstra + 优先队列 传统 Dijkstra 算法的变种，在优先队列中存储 (cost, city, stops)，确保不超过 K 次中转。

方法3：BFS 使用 BFS 逐层遍历，每一层代表一次中转，最多进行 K+1 层（包括起点）。

DP 方法在这个问题中最为直观和高效，因为它直接利用了问题的最优子结构特性。时间复杂度为 O(K * E)，其中 E 是边数，空间复杂度为 O(N)。

代码实现

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<int> dp(n, INT_MAX);
        dp[src] = 0;
        
        for (int i = 0; i <= k; i++) {
            vector<int> temp = dp;
            for (auto& flight : flights) {
                int from = flight[0], to = flight[1], price = flight[2];
                if (dp[from] != INT_MAX) {
                    temp[to] = min(temp[to], dp[from] + price);
                }
            }
            dp = temp;
        }
        
        return dp[dst] == INT_MAX ? -1 : dp[dst];
    }
};

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        dp = [float('inf')] * n
        dp[src] = 0
        
        for i in range(k + 1):
            temp = dp[:]
            for from_city, to_city, price in flights:
                if dp[from_city] != float('inf'):
                    temp[to_city] = min(temp[to_city], dp[from_city] + price)
            dp = temp
        
        return dp[dst] if dp[dst] != float('inf') else -1

public class Solution {
    public int FindCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        int[] dp = new int[n];
        Array.Fill(dp, int.MaxValue);
        dp[src] = 0;
        
        for (int i = 0; i <= k; i++) {
            int[] temp = new int[n];
            Array.Copy(dp, temp, n);
            
            foreach (var flight in flights) {
                int from = flight[0], to = flight[1], price = flight[2];
                if (dp[from] != int.MaxValue) {
                    temp[to] = Math.Min(temp[to], dp[from] + price);
                }
            }
            dp = temp;
        }
        
        return dp[dst] == int.MaxValue ? -1 : dp[dst];
    }
}

var findCheapestPrice = function(n, flights, src, dst, k) {
    let dp = new Array(n).fill(Infinity);
    dp[src] = 0;
    
    for (let i = 0; i <= k; i++) {
        let temp = [...dp];
        for (let [from, to, price] of flights) {
            if (dp[from] !== Infinity) {
                temp[to] = Math.min(temp[to], dp[from] + price);
            }
        }
        dp = temp;
    }
    
    return dp[dst]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型动态规划解法
时间复杂度O(K × E)
空间复杂度O(N)

其中 K 是允许的最大中转次数，E 是航班数量，N 是城市数量。

相关题目