本文时间知识点
单源最短路
LeetCode100276. 最短路径中的边
给你一个 n 个节点的无向带权图，节点编号为 0 到 n - 1 。图中总共有 m 条边，用二维数组 edges 表示，其中 edges[i] = [ai, bi, wi] 表示节点 ai 和 bi 之间有一条边权为 wi 的边。
对于节点 0 为出发点，节点 n - 1 为结束点的所有最短路，你需要返回一个长度为 m 的 boolean 数组 answer ，如果 edges[i] 至少 在其中一条最短路上，那么 answer[i] 为 true ，否则 answer[i] 为 false 。
请你返回数组 answer 。
注意，图可能不连通。
示例 1：
输入：n = 6, edges = [[0,1,4],[0,2,1],[1,3,2],[1,4,3],[1,5,1],[2,3,1],[3,5,3],[4,5,2]]
输出：[true,true,true,false,true,true,true,false]
解释：
以下为节点 0 出发到达节点 5 的 所有 最短路：
路径 0 -> 1 -> 5 ：边权和为 4 + 1 = 5 。
路径 0 -> 2 -> 3 -> 5 ：边权和为 1 + 1 + 3 = 5 。
路径 0 -> 2 -> 3 -> 1 -> 5 ：边权和为 1 + 1 + 2 + 1 = 5 。
示例 2：
输入：n = 4, edges = [[2,0,1],[0,1,1],[0,3,4],[3,2,2]]
输出：[true,false,false,true]
解释：
只有一条从节点 0 出发到达节点 3 的最短路 0 -> 2 -> 3 ，边权和为 1 + 2 = 3 。
提示：
2 <= n <= 5 * 104
m == edges.length
1 <= m <= min(5 * 104, n * (n - 1) / 2)
0 <= ai, bi < n
ai != bi
1 <= wi <= 105
图中没有重边。
单源最短路
准备修改 堆优化迪氏定理。优化过程中，发现直接使用 迪氏定理就可以了。浪费了20分钟。如果边{n1,n2,w} 是最短路径的边，则一定是以下情况之一：
计算这两条路径的最短路，就可以了。
提前计算好：0到各点的最短路径，(n-1)到各点的最短路。
时间复杂度： O(mlogm)+O(m) m是边数。
代码
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; } }; typedef pair<long long, int> PAIRLLI; class CHeapDis { public: CHeapDis(int n,long long llEmpty = LLONG_MAX/10):m_llEmpty(llEmpty) { 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; } 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; }; class Solution { public: vector<bool> findAnswer(int n, vector<vector<int>>& edges) { auto neiBo = CNeiBo::Three(n, edges, false); CHeapDis dis1(n),dis2(n); dis1.Cal(0, neiBo); dis2.Cal(n - 1, neiBo); const long long llMinDis = dis1.m_vDis[n - 1]; vector<bool> ret; for (const auto& v : edges) { bool b1 = ( llMinDis ==(v[2] + dis1.m_vDis[v[0]] + dis2.m_vDis[v[1]])); bool b2 = (llMinDis == (v[2] + dis2.m_vDis[v[0]] + dis1.m_vDis[v[1]])); ret.emplace_back(b1 || b2); } return ret; } };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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++**实现。
