M787.K站中转内最便宜的航班

Bellman Ford, https://leetcode.cn/problems/cheapest-flights-within-k-stops/

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

现在给定所有的城市和航班，以及出发城市 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, edges = [[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。

提示：

• 1 <= 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

下面给出基于 Bellman–Ford 思想的做法，它在「最多经过 K 次中转」的约束下，求出从 src 到 dst 的最小费用。

---

思路

1. 初始化： 我们用一个长度为 n 的数组 dist 表示当前已知到各城市的最便宜费用，初始时所有城市费用设为 ∞，只有 dist[src] = 0。

2. 松弛操作： Bellman–Ford 的经典算法是对所有边做 n–1 轮松弛，最终可求出任意路径的最短路。但本题对中转次数有限制：至多 K 次中转，也就是路径上最多 K+1 条边。

   因此，我们只需要做 K+1 轮松弛即可。在第 i 轮松弛后，dist[j] 就代表「恰好使用最多 i 条边能到达 j 的最小费用」。

   为了避免本轮松弛互相影响，需要每轮都基于上一轮的 prev_dist 来更新新的 cur_dist，更新完成后再复制回 dist。

3. 返回答案： 做完 K+1 轮后，dist[dst] 即为所求最小费用；若仍为 ∞，则说明无法在 K 次中转以内到达，返回 -1。

代码实现（Python）

from typing import List

class Solution:
    def findCheapestPrice(self, 
                          n: int, 
                          flights: List[List[int]], 
                          src: int, 
                          dst: int, 
                          K: int) -> int:
        # 初始化：到各城最便宜费用
        INF = float('inf')
        dist = [INF] * n
        dist[src] = 0
        
        # 最多允许 K 次中转 -> 最多使用 K+1 条边
        for _ in range(K + 1):
            # 基于上一轮的结果创建新一轮的 dist
            prev = dist[:]  
            
            # 对每条航班边做松弛
            for u, v, w in flights:
                # 若 u 可达，则尝试用 u -> v 这条边更新 v
                if prev[u] + w < dist[v]:
                    dist[v] = prev[u] + w
            
            # 下一轮松弛时，依然要基于本轮更新后的 dist，
            # 因此不需要再额外复制
        
        return dist[dst] if dist[dst] != INF else -1

复杂度分析

• 时间复杂度： 每轮要遍历所有边，边数最多为 O(n²)，共做 K+1 轮松弛，总体为 O((K+1)·E)；在最坏情况下 E≈n²，则为 O(K·n²)。
• 空间复杂度： 仅使用了大小为 n 的数组，故为 O(n)。

Q: 这段代码，可以写为二维数组dist吧

这段代码中使用的一维数组 dist 可以扩展为二维数组 dist[i][j]，其中：

• i 表示使用的中转次数（也可以理解为使用的边数）。
• j 表示城市编号。
• dist[i][j] 表示最多使用 i 条边，从 src 到达城市 j 的最小费用。

使用二维数组的版本代码如下：

from typing import List

class Solution:
    def findCheapestPrice(self, 
                          n: int, 
                          flights: List[List[int]], 
                          src: int, 
                          dst: int, 
                          K: int) -> int:
        INF = float('inf')
        # dist[i][j] 表示使用 i 条边时，到达城市 j 的最小费用
        dist = [[INF] * n for _ in range(K + 2)]
        dist[0][src] = 0

        for i in range(1, K + 2):  # i 表示当前使用的边数
            for j in range(n):
                dist[i][j] = dist[i - 1][j]  # 继承上一次的结果
            for u, v, w in flights:
                if dist[i - 1][u] + w < dist[i][v]:
                    dist[i][v] = dist[i - 1][u] + w

        return dist[K + 1][dst] if dist[K + 1][dst] != INF else -1

说明：

• 外层循环从 1 到 K + 1，表示使用 0 到 K 次中转（即 1 到 K + 1 条边）。
• dist[i][v] 是基于 dist[i - 1][u] 来更新的，防止本轮更新影响同轮的其他松弛。
• 最终结果在 dist[K + 1][dst] 中。若无法到达，则返回 -1。

这种方式更清晰地表示了每一轮松弛时的状态，也便于调试和扩展。

Q: 感觉像是二维dp的小偷背包？

是的，你的直觉非常对！这个问题在本质上和 二维动态规划的 0-1 背包问题（小偷背包） 有不少相似之处。我们可以从动态规划的角度来类比它：

---

🔍 类比：小偷背包问题 vs 最便宜航班问题

小偷背包问题	本问题（最便宜航班）
状态：dp[i][j] 表示前 i 个物品、背包容量为 j 时的最大价值	状态：dist[i][j] 表示使用 i 次中转，到达城市 j 的最小花费
决策：放或不放第 i 个物品	决策：走或不走当前这条航班边 (u, v, w)
状态转移：dp[i][j] = max(...)	状态转移：dist[i][v] = min(dist[i][v], dist[i-1][u] + w)
初始状态：dp[0][0] = 0	初始状态：dist[0][src] = 0

---

📌 区别与特点：

• 不同的是，航班问题中转的“容量”是边数（K + 1 条边），而不是重量或体积。
• 目标不同：背包是“最大价值”，这里是“最小费用”，但核心一样：每步都在做“选择 + 状态更新”。

---

✅ 为什么用二维数组好？

• 更像标准 DP 模板，逻辑清晰。
• 可扩展性强，比如若限制更多属性（如时间、航班数量等），二维甚至多维 DP 更好适配。
• 若要记录路径，也可以通过 dist 的下标方便追踪。

---

所以可以说这个解法是 动态规划 + Bellman-Ford 算法思想的结合，而 Bellman-Ford 本质也是一种动态规划的图论变体。

如果你熟悉背包 DP，这种二维数组的结构会非常自然。

Q：一维写法是状态压缩？

完全正确！你说的一维写法正是状态压缩（State Compression）在动态规划中的经典应用。

---

✅ 状态压缩的原理

在标准的二维动态规划中，如果我们在计算 dp[i][*] 时只依赖于前一行 dp[i-1][\*]，那么就可以只保留两行甚至一行，从而节省空间。

在这道航班题里，二维数组 dist[i][j] 中，每一轮 i 只依赖 i-1 的状态，所以可以用一维数组压缩掉状态维度，提升空间效率。

---

📌 对比分析

写法	结构	空间复杂度	可读性	备注
二维 DP 写法	dist[i][j]	O(K * n)	较清晰	易于理解和调试
一维状态压缩写法	dist[j] 与 prev[j]	O(n)	稍难	需小心避免当前轮干扰上轮状态

---

🚨 一维写法要注意的问题：

一维数组的更新必须基于上一个轮次的快照（通常叫 prev），否则你会在一轮中相互干扰，造成错误的更新。

prev = dist[:]
for u, v, w in flights:
    if prev[u] + w < dist[v]:
        dist[v] = prev[u] + w

这一行 prev[u] + w 就是确保我们从“上一轮的状态”转移到“当前轮的状态”，避免状态污染。

---

🧠 总结一下：

• ✅ 一维版本是对二维 DP 的空间优化，称作状态压缩；
• ✅ 关键是保证上一轮状态独立；
• ✅ 常见于背包问题、图最短路问题（如 Bellman-Ford）、最长子序列等动态规划问题。

你已经触类旁通，非常棒！

使用 BFS + 堆（优先队列），记录每个点在中转次数不超过 k 时的最短路径。

import heapq
from collections import defaultdict

class Solution:
    def findCheapestPrice(self, n, flights, src, dst, k):
        graph = defaultdict(list)
        for u, v, w in flights:
            graph[u].append((v, w))
        
        # 优先队列中存储：总费用, 当前城市, 当前中转次数
        heap = [(0, src, 0)]
        # 记录每个城市在某个中转次数下的最小费用
        visited = dict()

        while heap:
            cost, city, stops = heapq.heappop(heap)
            
            if city == dst:
                return cost
            
            if stops > k:
                continue

            # 剪枝：如果已经以更少的费用到达过这个城市在相同或更少的中转数下，则跳过
            if (city, stops) in visited and visited[(city, stops)] <= cost:
                continue
            visited[(city, stops)] = cost

            for nei, price in graph[city]:
                heapq.heappush(heap, (cost + price, nei, stops + 1))

        return -1