本文涉及知识点
单源最短路
Leetcode3112. 访问消失节点的最少时间
给你一个二维数组 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
单源最短路
不能用朴素单源最短路，时间复杂度O(nn)=O(108)
用堆优化单源路径，时间复杂度O(eloge)=O(105log105)
最封装类上加一个判断条件：如果距离大于等于disappear[i]则忽略。
代码
class CNeiBo { public: static vector<vector<int>> Two(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0) { vector<vector<int>> vNeiBo(n); for (const auto& v : edges) { vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase); if (!bDirect) { vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase); } } return vNeiBo; } static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0) { vector<vector<std::pair<int, int>>> vNeiBo(n); for (const auto& v : edges) { vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase, v[2]); if (!bDirect) { vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase, v[2]); } } return vNeiBo; } static vector<vector<int>> Grid(int rCount, int cCount, std::function<bool(int, int)> funVilidCur, std::function<bool(int, int)> funVilidNext) { vector<vector<int>> vNeiBo(rCount * cCount); auto Move = [&](int preR, int preC, int r, int c) { if ((r < 0) || (r >= rCount)) { return; } if ((c < 0) || (c >= cCount)) { return; } if (funVilidCur(preR, preC) && funVilidNext(r, c)) { vNeiBo[cCount * preR + preC].emplace_back(r * cCount + c); } }; for (int r = 0; r < rCount; r++) { for (int c = 0; c < cCount; c++) { Move(r, c, r + 1, c); Move(r, c, r - 1, c); Move(r, c, r, c + 1); Move(r, c, r, c - 1); } } return vNeiBo; } static vector<vector<int>> Mat(vector<vector<int>>& neiBoMat) { vector<vector<int>> neiBo(neiBoMat.size()); for (int i = 0; i < neiBoMat.size(); i++) { for (int j = i + 1; j < neiBoMat.size(); j++) { if (neiBoMat[i][j]) { neiBo[i].emplace_back(j); neiBo[j].emplace_back(i); } } } return neiBo; } }; //堆（优先队列)优化迪杰斯特拉算法 狄克斯特拉(Dijkstra)算法详解 typedef pair<long long, int> PAIRLLI; class CMyHeapDis { public: CMyHeapDis(vector<int>& disappear,int n, long long llEmpty = LLONG_MAX / 10) :m_llEmpty(llEmpty),m_disappear(disappear) { m_vDis.assign(n, m_llEmpty); } void Cal(int start, const vector<vector<pair<int, int>>>& vNeiB) { std::priority_queue<PAIRLLI, vector<PAIRLLI>, greater<PAIRLLI>> minHeap; minHeap.emplace(0, start); while (minHeap.size()) { const long long llDist = minHeap.top().first; const int iCur = minHeap.top().second; minHeap.pop(); if (m_llEmpty != m_vDis[iCur]) { continue; } if (llDist >= m_disappear[iCur]) { continue; } m_vDis[iCur] = llDist; for (const auto& it : vNeiB[iCur]) { minHeap.emplace(llDist + it.second, it.first); } } } vector<long long> m_vDis; const long long m_llEmpty; vector<int>& m_disappear; }; class Solution { public: vector<int> minimumTime(int n, vector<vector<int>>& edges, vector<int>& disappear) { auto neiBo = CNeiBo::Three(n, edges, false); CMyHeapDis dis(disappear,n,m_llNotMay); dis.Cal(0, neiBo); vector<int> vRet; for (int i = 0; i < n; i++) { vRet.emplace_back((m_llNotMay==dis.m_vDis[i])?-1: dis.m_vDis[i]); } return vRet; } const long long m_llNotMay = 1'000'000'000'000LL; };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
