如何做网站报价,苏州做网站公司精选苏州聚尚网络,西安官方网站建设,北京十大平面设计公司本文时间知识点
单源最短路 图论知识汇总
LeetCode100276. 最短路径中的边
给你一个 n 个节点的无向带权图#xff0c;节点编号为 0 到 n - 1 。图中总共有 m 条边#xff0c;用二维数组 edges 表示#xff0c;其中 edges[i] [ai, bi, wi] 表示节点 ai 和 bi 之间有一条…本文时间知识点
单源最短路 图论知识汇总
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 → n 2 → ( n − 1 ) 0 \rightarrow n1 \rightarrow n2 \rightarrow (n-1) 0→n1→n2→(n−1) 0 → n 2 → n 1 → ( n − 1 ) 0 \rightarrow n2 \rightarrow n1 \rightarrow (n-1) 0→n2→n1→(n−1) 计算这两条路径的最短路就可以了。 提前计算好0到各点的最短路径(n-1)到各点的最短路。
时间复杂度 O(mlogm)O(m) m是边数。
代码
class CNeiBo
{
public: static vectorvectorint Two(int n, vectorvectorint edges, bool bDirect, int iBase 0) {vectorvectorint 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 vectorvectorstd::pairint, int Three(int n, vectorvectorint edges, bool bDirect, int iBase 0){vectorvectorstd::pairint, 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 vectorvectorint Grid(int rCount, int cCount, std::functionbool(int, int) funVilidCur, std::functionbool(int, int) funVilidNext){vectorvectorint 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 vectorvectorint Mat(vectorvectorint neiBoMat){vectorvectorint 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 pairlong 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 vectorvectorpairint, int vNeiB){std::priority_queuePAIRLLI, vectorPAIRLLI, greaterPAIRLLI 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);}}}vectorlong long m_vDis;const long long m_llEmpty;
};class Solution {
public:vectorbool findAnswer(int n, vectorvectorint 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];vectorbool 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 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
