[M最短路] lc3112. 访问消失节点的最少时间(堆优化Dijkstra+最短路+模板题)

1. 题目来源

链接：3112. 访问消失节点的最少时间

• 关联：
  • [图+最短路+模板] 五大最短路常用模板

2. 题目解析

图论最短路的题目，分析思路如下：

• 源点类型：单源
• 图类型：稀疏图
• 数据范围：较大，Dijkstra 朴素不可用。

所以，顺利成章喽，堆优化 Dijkstra 上就完事了。

只需要注意下，在进行松弛操作时，需要判断 x–>y 点的最短路路径下，y 点是否还存在 即可。

还是得常常复习下图论模板及应用场景，对它理解还是不够深，此类模板题愣了一会会，还手生写的很慢。

• 时间复杂度：$O(n+mlogm)$
• 空间复杂度：$O(n+m)$

class Solution {
public:
    vector<int> minimumTime(int n, vector<vector<int>>& edges, vector<int>& disappear) {
        vector<vector<pair<int, int>>> adj(n);
        for (auto & e : edges) {
            int x = e[0], y = e[1], w = e[2];
            adj[x].push_back({y, w});
            adj[y].push_back({x, w});
        }

        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push({0, 0});

        vector<int> dist(n, -1);
        dist[0] = 0;
        vector<int> st(n);
        while (pq.size()) {
            auto [d, x] = pq.top(); pq.pop();

            if (st[x]) continue;
            st[x] = true;

            for (auto& [y, length] : adj[x]) {
                if (d + length < disappear[y] && (dist[y] < -1 || d + length < dist[y])) {
                    pq.push({d + length, y});
                    dist[y] = d + length;
                }
            }
        }

        return dist;
    }
};