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:

输入: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 * 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 ) O(n+m\log m) O(n+mlogm),其中 n n n是节点数量, m m m是边的数量。
  • 空间复杂度 O ( n + m ) O(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

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-19 16:36:04       172 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-19 16:36:04       190 阅读
  3. 在Django里面运行非项目文件

    2024-07-19 16:36:04       158 阅读
  4. Python语言-面向对象

    2024-07-19 16:36:04       171 阅读

热门阅读

  1. OJ-0718

    2024-07-19 16:36:04       27 阅读
  2. 【Python中的垃圾回收机制是什么】

    2024-07-19 16:36:04       31 阅读
  3. 基于深度学习的人脸表情识别系统

    2024-07-19 16:36:04       32 阅读
  4. Rancher

    Rancher

    2024-07-19 16:36:04      34 阅读
  5. 5、在共享内存无指针编程:句柄HANDLE转换为指针

    2024-07-19 16:36:04       29 阅读
  6. 探索单片机的光耦:定义、作用与应用

    2024-07-19 16:36:04       31 阅读
  7. C 语言实例 - 使用引用循环替换数值

    2024-07-19 16:36:04       36 阅读
  8. 数据结构---数组

    2024-07-19 16:36:04       28 阅读
  9. 【windows】网络信息相关命令

    2024-07-19 16:36:04       32 阅读
  10. python3.11SSL: SSLV3_ALERT_HANDSHAKE_FAILURE

    2024-07-19 16:36:04       32 阅读
  11. 最短路径算法——A*算法

    2024-07-19 16:36:04       31 阅读