LeetCode 3112.访问消失节点的最少时间：单源最短路的Dijkstra算法

【LetMeFly】3112.访问消失节点的最少时间：单源最短路的Dijkstra算法

力扣题目链接：https://leetcode.cn/problems/minimum-time-to-visit-disappearing-nodes/

给你一个二维数组 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：

输出：[0,-1,4]

解释：

我们从节点 0 出发，目的是用最少的时间在其他节点消失之前到达它们。

• 对于节点 0 ，我们不需要任何时间，因为它就是我们的起点。
• 对于节点 1 ，我们需要至少 2 单位时间，通过 edges[0] 到达。但当我们到达的时候，它已经消失了，所以我们无法到达它。
• 对于节点 2 ，我们需要至少 4 单位时间，通过 edges[2] 到达。

示例 2：

输出：[0,2,3]

解释：

我们从节点 0 出发，目的是用最少的时间在其他节点消失之前到达它们。

• 对于节点 0 ，我们不需要任何时间，因为它就是我们的起点。
• 对于节点 1 ，我们需要至少 2 单位时间，通过 edges[0] 到达。
• 对于节点 2 ，我们需要至少 3 单位时间，通过 edges[0] 和 edges[1] 到达。

示例 3：

输出：[0,-1]

解释：

当我们到达节点 1 的时候，它恰好消失，所以我们无法到达节点 1 。

提示：

• 1 <= n <= 5 * 104
• 0 <= edges.length <= 105
• edges[i] == [ui, vi, lengthi]
• 0 <= ui, vi <= n - 1
• 1 <= lengthi <= 105
• disappear.length == n
• 1 <= disappear[i] <= 105

解题方法：单源最短路的Dijkstra算法

关于单源最短路的Dijkstra算法的视频讲解，可以查看这个视频。

大致思路是：从起点开始，每次将所有的能一部到达的节点放入优先队列中。优先队列中存放的是每个节点的首次能到达的时间以及节点编号，能最先到达的最先出队。

每次从优先队列中取出一个元素，这样就得到了这个元素的最快到达时间。以此节点开始将所有相邻的没有确定过最短时间的节点入队。直到队列为空为止，就得到了从起点到其他任意一点的最短耗时。

关于本题，有个额外条件就是节点消失时间。很简单，在每次遍历当前节点的相邻节点时，若无法在某相邻节点消失之前到达，则不将其入队。

• 时间复杂度$O(n+m\log m)$，其中$n$是节点数量，$m$是边的数量。
• 空间复杂度$O(n+m)$

AC代码

C++

class Solution {
public:vector<int> minimumTime(int n, vector<vector<int>>& edges, vector<int>& disappear) {vector<vector<pair<int, int>>> graph(n);for (vector<int>& edge : edges) {graph[edge[0]].push_back({edge[1], edge[2]});graph[edge[1]].push_back({edge[0], edge[2]});}vector<int> ans(n, -1);priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;  // [<time, toNode>, ...pq.push({0, 0});while (pq.size()) {auto [thisTime, thisNode] = pq.top();pq.pop();if (ans[thisNode] != -1) {continue;}ans[thisNode] = thisTime;for (auto [nextNode, length] : graph[thisNode]) {if (ans[nextNode] != -1 || thisTime + length >= disappear[nextNode]) {continue;}pq.push({thisTime + length, nextNode});}}return ans;}
};

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;class Solution {public int[] minimumTime(int n, int[][] edges, int[] disappear) {List<int[]>[] graph = new ArrayList[n];Arrays.setAll(graph, i -> new ArrayList<>());for (int[] edge : edges) {graph[edge[0]].add(new int[]{edge[1], edge[2]});graph[edge[1]].add(new int[]{edge[0], edge[2]});}int[] ans = new int[n];Arrays.fill(ans, -1);Queue<int[]> pq = new PriorityQueue<>((a, b) -> (a[0] - b[0]));pq.add(new int[]{0, 0});while (!pq.isEmpty()) {int[] temp = pq.poll();int thisTime = temp[0];int thisNode = temp[1];if (ans[thisNode] != -1) {continue;}ans[thisNode] = thisTime;for (int[] temp2 : graph[thisNode]) {int nextNode = temp2[0];int length = temp2[1];if (ans[nextNode] == -1 && thisTime + length < disappear[nextNode]) {pq.add(new int[]{thisTime + length, nextNode});}}}return ans;}
}

Python

from typing import List
import heapqclass Solution:def minimumTime(self, n: int, edges: List[List[int]], disappear: List[int]) -> List[int]:graph = [[] for _ in range(n)]for x, y, d in edges:graph[x].append((y, d))graph[y].append((x, d))ans = [-1] * npq = [(0, 0)]while pq:thisTime, thisNode = heapq.heappop(pq)if ans[thisNode] != -1:continueans[thisNode] = thisTimefor nextNode, length in graph[thisNode]:# print(nextNode, length, ans[nextNode], thisTime + length, disappear[nextNode])  #------------------# print(ans[nextNode] != -1)# print(thisTime + length < disappear[nextNode])if ans[nextNode] == -1 and thisTime + length < disappear[nextNode]:heapq.heappush(pq, (thisTime + length, nextNode))return ansif __name__ == '__main__':sol = Solution()print(sol.minimumTime(3, [[0, 1, 2], [1, 2, 1], [0, 2, 4]], [1, 1, 5]))

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/140530368