3112. 访问消失节点的最少时间 Medium

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

题目大意:只有在各结点的规定时间内才能访问各结点的情况下计算从0到达各结点的最短时间。

分析:

(1)由题可知这是单源最短路径问题,因此使用dijkstra算法;

(2)由于题中结点个数较多,因此使用优先级队列存储已访问过的结点中可以直接到达的未访问过的结点来加速查找距离0结点最近且未访问过的点;

(3)对于在规定时间外访问的结点只需不将其加入优先级队列即可。

class Solution {
public:
    vector<int> minimumTime(int n, vector<vector<int>>& edges, vector<int>& disappear) {
        int x,y,t,node,time,nt;
        vector<int> ans(n,-1);
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
        vector<vector<pair<int,int>>> map(n);
        for(const auto& edge:edges){
            x=edge[0];y=edge[1];t=edge[2];
            if(x==y) continue;
            map[x].emplace_back(y,t);
            map[y].emplace_back(x,t);
        }
        q.emplace(0,0);
        ans[0]=0;
        while(q.size()){
            auto [time,node]=q.top();
            q.pop();
            if(time!=ans[node]) continue;
            for(const auto& [nextNode,nextTime]:map[node]){
                if((nt=time+nextTime)<disappear[nextNode]&&(ans[nextNode]==-1)||nt<ans[nextNode]){
                    ans[nextNode]=nt;
                    q.emplace(nt,nextNode);
                }
            }
        }
        return ans;
    }
};

相关推荐

最近更新

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

    2024-07-21 00:24:03       94 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-21 00:24:03       101 阅读
  3. 在Django里面运行非项目文件

    2024-07-21 00:24:03       82 阅读
  4. Python语言-面向对象

    2024-07-21 00:24:03       91 阅读

热门阅读

  1. Python print() 格式化输出

    2024-07-21 00:24:03       29 阅读
  2. Web学习day05

    2024-07-21 00:24:03       27 阅读
  3. 高阶面试-hw算法整理

    2024-07-21 00:24:03       22 阅读
  4. std::bind 简单实验

    2024-07-21 00:24:03       27 阅读
  5. 中电金信:语言服务游戏行业解决方案

    2024-07-21 00:24:03       26 阅读
  6. 数据库之数据类型

    2024-07-21 00:24:03       23 阅读
  7. 代码保存板块

    2024-07-21 00:24:03       27 阅读
  8. Git 代码管理面试59题(一)

    2024-07-21 00:24:03       25 阅读
  9. Kudu节点数规划

    2024-07-21 00:24:03       30 阅读
  10. Emacs

    2024-07-21 00:24:03       26 阅读
  11. 提升 Google 对网站兴趣的关键:颜值与内容并重

    2024-07-21 00:24:03       16 阅读