LeetCode 题解工作台
规定时间内到达终点的最小花费
一个国家有 n 个城市，城市编号为 0 到 n - 1 ，题目保证 所有城市 都由双向道路 连接在一起 。道路由二维整数数组 edges 表示，其中 edges[i] = [x i , y i , time i ] 表示城市 x i 和 y i 之间有一条双向道路，耗费时间为 time i 分钟。两…
3
题型
5
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们定义 表示经过 分钟，从城市 到达城市 的最小花费。初始时 $f[0][0] = \textit{passingFees}[0]$，其余的 $f[0][j] = +\infty$。 接下来，我们在 $[1, \textit{maxTime}]$ 的时间范围内，遍历所有的边，对于每一条边 $(x, y, t)$，如果 $t \leq i$，那么我们：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
一个国家有 n 个城市，城市编号为 0 到 n - 1 ，题目保证 所有城市 都由双向道路 连接在一起 。道路由二维整数数组 edges 表示，其中 edges[i] = [xi, yi, timei] 表示城市 xi 和 yi 之间有一条双向道路，耗费时间为 timei 分钟。两个城市之间可能会有多条耗费时间不同的道路，但是不会有道路两头连接着同一座城市。
每次经过一个城市时，你需要付通行费。通行费用一个长度为 n 且下标从 0 开始的整数数组 passingFees 表示，其中 passingFees[j] 是你经过城市 j 需要支付的费用。
一开始，你在城市 0 ，你想要在 maxTime 分钟以内 （包含 maxTime 分钟）到达城市 n - 1 。旅行的 费用 为你经过的所有城市 通行费之和 （包括 起点和终点城市的通行费）。
给你 maxTime，edges 和 passingFees ，请你返回完成旅行的 最小费用 ，如果无法在 maxTime 分钟以内完成旅行，请你返回 -1 。
示例 1：
输入：maxTime = 30, edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees = [5,1,2,20,20,3] 输出：11 解释：最优路径为 0 -> 1 -> 2 -> 5 ，总共需要耗费 30 分钟，需要支付 11 的通行费。
示例 2：
输入：maxTime = 29, edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees = [5,1,2,20,20,3] 输出：48 解释：最优路径为 0 -> 3 -> 4 -> 5 ，总共需要耗费 26 分钟，需要支付 48 的通行费。 你不能选择路径 0 -> 1 -> 2 -> 5 ，因为这条路径耗费的时间太长。
示例 3：
输入：maxTime = 25, edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees = [5,1,2,20,20,3] 输出：-1 解释：无法在 25 分钟以内从城市 0 到达城市 5 。
提示：
1 <= maxTime <= 1000n == passingFees.length2 <= n <= 1000n - 1 <= edges.length <= 10000 <= xi, yi <= n - 11 <= timei <= 10001 <= passingFees[j] <= 1000- 图中两个节点之间可能有多条路径。
- 图中不含有自环。
解题思路
方法一：动态规划
我们定义 表示经过 分钟，从城市 到达城市 的最小花费。初始时 ，其余的 。
接下来，我们在 的时间范围内，遍历所有的边，对于每一条边 ，如果 ，那么我们：
- 可以先经过 分钟，从城市 到达城市 ，然后再经过 分钟，从城市 到达城市 ，再加上到达城市 的通行费，即 ；
- 也可以先经过 分钟，从城市 到达城市 ，然后再经过 分钟，从城市 到达城市 ，再加上到达城市 的通行费，即 。
最终答案即为 ，其中 。如果答案为 ，则返回 。
时间复杂度 ，其中 和 分别是边的数量和城市的数量。空间复杂度 。
class Solution:
def minCost(
self, maxTime: int, edges: List[List[int]], passingFees: List[int]
) -> int:
m, n = maxTime, len(passingFees)
f = [[inf] * n for _ in range(m + 1)]
f[0][0] = passingFees[0]
for i in range(1, m + 1):
for x, y, t in edges:
if t <= i:
f[i][x] = min(f[i][x], f[i - t][y] + passingFees[x])
f[i][y] = min(f[i][y], f[i - t][x] + passingFees[y])
ans = min(f[i][n - 1] for i in range(m + 1))
return ans if ans < inf else -1
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for an efficient way to manage state transitions across cities and times.
- question_mark
Pay attention to how the candidate handles edge cases, such as when it's impossible to reach the destination in time.
- question_mark
Evaluate the candidate's approach to optimizing performance using priority queues or dynamic programming.
常见陷阱
外企场景- error
Ignoring the time constraint and exploring paths that exceed maxTime.
- error
Not considering multiple paths between two cities with different travel times.
- error
Overlooking edge cases where the destination is unreachable within the time limit.
进阶变体
外企场景- arrow_right_alt
Introduce multiple source and destination cities.
- arrow_right_alt
Modify the problem by allowing one-way roads.
- arrow_right_alt
Vary the passing fees by making them dynamic based on time of day or other conditions.