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

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

题目

题目解析及思路

题目要求返回从0到达其他点的最短时间，但是每个点有一个消失时间，过了消失时间这个点就无法到达

也就是迪杰斯特拉模板 + 如果时间过了就不更新dis

代码

class Solution {
public:
    vector<int> minimumTime(int n, vector<vector<int>>& edges, vector<int>& disappear) {
        //邻接表
        vector<vector<pair<int, int>>> g(n);
        for (auto& e : edges) {
            int x = e[0], y = e[1], wt = e[2];
            g[x].emplace_back(y, wt);
            g[y].emplace_back(x, wt);
        }

        vector<int> dis(n,-1);
        dis[0] = 0;
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> pq;
        pq.emplace(0,0);
        while(!pq.empty()){
            auto [dx,x] = pq.top();
            pq.pop();
            //因为可能在队列中同时存在多个x
            //如果之前取出过x，说明0到x的距离已经是最短了，也就是dis[x]一定小于之前存的dx
            //防止重复遍历已经确定最短的点
            if(dx > dis[x]){
                continue;
            }
            for(auto& [y,d]:g[x]){
                int new_dis = dx + d;
                if(new_dis < disappear[y] && (dis[y] < 0 || new_dis < dis[y])){
                    dis[y] = new_dis;
                    pq.emplace(new_dis,y);
                }
            }
        }
        return dis;
    }
};