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 heapq

class 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] * n
        pq = [(0, 0)]
        while pq:
            thisTime, thisNode = heapq.heappop(pq)
            if ans[thisNode] != -1:
                continue
            ans[thisNode] = thisTime
            for 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 ans


if __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