LeetCode 题解工作台
K 站中转内最便宜的航班
有 n 个城市通过一些航班连接。给你一个数组 flights ，其中 flights[i] = [from i , to i , price i ] ，表示该航班都从城市 from i 开始，以价格 price i 抵达 to i 。 现在给定所有的城市和航班，以及出发城市 src 和目的地 dst…
6
题型
4
代码语言
3
相关题
当前训练重点
中等 · 图·DFS·traversal
答案摘要
class Solution: def findCheapestPrice(
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·DFS·traversal 题型思路
题目描述
有 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。
提示：
2 <= n <= 1000 <= flights.length <= (n * (n - 1) / 2)flights[i].length == 30 <= fromi, toi < nfromi != toi1 <= pricei <= 104- 航班没有重复，且不存在自环
0 <= src, dst, k < nsrc != dst
解题思路
方法一：Bellman Ford 算法
class Solution:
def findCheapestPrice(
self, n: int, flights: List[List[int]], src: int, dst: int, k: int
) -> int:
INF = 0x3F3F3F3F
dist = [INF] * n
dist[src] = 0
for _ in range(k + 1):
backup = dist.copy()
for f, t, p in flights:
dist[t] = min(dist[t], backup[f] + p)
return -1 if dist[dst] == INF else dist[dst]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the approach: DFS can reach O(n^k) in worst case without pruning, BFS is O(n + flights.length) per level, and DP reduces repeated computations to O(n _k). Space complexity varies: DFS recursion stack is O(n), BFS queue can be O(n_ k), and DP table requires O(n*k) space. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate understands graph traversal constraints and pruning techniques.
- question_mark
Candidate explains how stops limitation affects path exploration and algorithm choice.
- question_mark
Shows awareness of time-space trade-offs for DFS, BFS, and DP in this problem context.
常见陷阱
外企场景- error
Ignoring the maximum stop constraint leads to invalid cheaper paths being selected.
- error
Failing to prune higher-cost paths early causes exponential blow-up in DFS.
- error
Recomputing subproblems without memoization increases runtime unnecessarily.
进阶变体
外企场景- arrow_right_alt
Allow flights with unlimited stops and optimize for shortest cost using standard Dijkstra's algorithm.
- arrow_right_alt
Return the number of different cheapest paths instead of the minimum cost.
- arrow_right_alt
Change the cost metric to include flight durations or combined price-duration trade-offs.