LeetCode 题解工作台
访问消失节点的最少时间
给你一个二维数组 edges 表示一个 n 个点的无向图，其中 edges[i] = [u i , v i , length i ] 表示节点 u i 和节点 v i 之间有一条需要 length i 单位时间通过的无向边。 同时给你一个数组 disappear ，其中 disappear[i] 表…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 堆
答案摘要
我们先创建一个邻接表 ，用于存储图的边。然后创建一个数组 ，用于存储从节点 到其他节点的最短距离。初始化 $\textit{dist}[0] = 0$，其余节点的距离初始化为无穷大。 然后，我们使用 Dijkstra 算法计算从节点 到其他节点的最短距离。具体步骤如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 堆 题型思路
题目描述
给你一个二维数组 edges 表示一个 n 个点的无向图，其中 edges[i] = [ui, vi, lengthi] 表示节点 ui 和节点 vi 之间有一条需要 lengthi 单位时间通过的无向边。
同时给你一个数组 disappear ，其中 disappear[i] 表示节点 i 从图中消失的时间点，在那一刻及以后，你无法再访问这个节点。
注意，图有可能一开始是不连通的，两个节点之间也可能有多条边。
请你返回数组 answer ，answer[i] 表示从节点 0 到节点 i 需要的 最少 单位时间。如果从节点 0 出发 无法 到达节点 i ，那么 answer[i] 为 -1 。
示例 1：
输入：n = 3, edges = [[0,1,2],[1,2,1],[0,2,4]], disappear = [1,1,5]
输出：[0,-1,4]
解释：
我们从节点 0 出发，目的是用最少的时间在其他节点消失之前到达它们。
- 对于节点 0 ，我们不需要任何时间，因为它就是我们的起点。
- 对于节点 1 ，我们需要至少 2 单位时间，通过
edges[0]到达。但当我们到达的时候，它已经消失了，所以我们无法到达它。 - 对于节点 2 ，我们需要至少 4 单位时间，通过
edges[2]到达。
示例 2：
输入：n = 3, edges = [[0,1,2],[1,2,1],[0,2,4]], disappear = [1,3,5]
输出：[0,2,3]
解释：
我们从节点 0 出发，目的是用最少的时间在其他节点消失之前到达它们。
- 对于节点 0 ，我们不需要任何时间，因为它就是我们的起点。
- 对于节点 1 ，我们需要至少 2 单位时间，通过
edges[0]到达。 - 对于节点 2 ，我们需要至少 3 单位时间，通过
edges[0]和edges[1]到达。
示例 3：
输入：n = 2, edges = [[0,1,1]], disappear = [1,1]
输出：[0,-1]
解释：
当我们到达节点 1 的时候，它恰好消失，所以我们无法到达节点 1 。
提示：
1 <= n <= 5 * 1040 <= edges.length <= 105edges[i] == [ui, vi, lengthi]0 <= ui, vi <= n - 11 <= lengthi <= 105disappear.length == n1 <= disappear[i] <= 105
解题思路
方法一：堆优化的 Dijkstra
我们先创建一个邻接表 ，用于存储图的边。然后创建一个数组 ，用于存储从节点 到其他节点的最短距离。初始化 ，其余节点的距离初始化为无穷大。
然后，我们使用 Dijkstra 算法计算从节点 到其他节点的最短距离。具体步骤如下：
- 创建一个优先队列 ，用于存储节点的距离和节点编号，初始时将节点 加入队列，距离为 。
- 从队列中取出一个节点 ，如果 的距离 大于 ，说明 已经被更新过了，直接跳过。
- 遍历节点 的所有邻居节点 ，如果 且 ，则更新 ，并将节点 加入队列。
- 重复步骤 2 和步骤 3，直到队列为空。
最后，我们遍历 数组，如果 ，则 ，否则 。
时间复杂度 ，空间复杂度 。其中 是边的数量。
class Solution:
def minimumTime(
self, n: int, edges: List[List[int]], disappear: List[int]
) -> List[int]:
g = defaultdict(list)
for u, v, w in edges:
g[u].append((v, w))
g[v].append((u, w))
dist = [inf] * n
dist[0] = 0
pq = [(0, 0)]
while pq:
du, u = heappop(pq)
if du > dist[u]:
continue
for v, w in g[u]:
if dist[v] > dist[u] + w and dist[u] + w < disappear[v]:
dist[v] = dist[u] + w
heappush(pq, (dist[v], v))
return [a if a < b else -1 for a, b in zip(dist, disappear)]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the number of nodes and edges processed in the priority queue, generally O((n + edges.length) log n). Space complexity is dominated by the adjacency list, priority queue, and result array, typically O(n + edges.length). |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check whether the candidate correctly handles nodes that disappear before being reached.
- question_mark
Listen for usage of priority queue with Dijkstra to manage earliest arrival times.
- question_mark
Watch if the candidate optimizes multiple edges between nodes efficiently.
常见陷阱
外企场景- error
Forgetting to compare current traversal time with node disappear time, causing incorrect reachable nodes.
- error
Not handling multiple edges between the same nodes properly, leading to suboptimal paths.
- error
Assuming the graph is connected and not accounting for unreachable nodes.
进阶变体
外企场景- arrow_right_alt
Nodes disappear at random intervals instead of a fixed array, requiring dynamic updates during traversal.
- arrow_right_alt
Edges may have time-dependent weights, increasing complexity of minimum arrival computation.
- arrow_right_alt
Start node is not fixed at 0, requiring generalized multi-source shortest path handling.