鼎成中考开卷通有关网站做的电子书,哈尔滨 建网站,wordpress占用,电子商务网站建设感悟本篇源码下载
点击下载
1.12.1. 题目 给你一个 n 个节点的 无向带权连通 图#xff0c;节点编号为 0 到 n - 1 #xff0c;再给你一个整数数组 edges #xff0c;其中 edges[i] [ai, bi, wi] 表示节点 ai 和 bi 之间有一条边权为 wi 的边。 部分边的边权为 -1#xff08…本篇源码下载
点击下载
1.12.1. 题目 给你一个 n 个节点的 无向带权连通 图节点编号为 0 到 n - 1 再给你一个整数数组 edges 其中 edges[i] [ai, bi, wi] 表示节点 ai 和 bi 之间有一条边权为 wi 的边。 部分边的边权为 -1wi -1其他边的边权都为 正 数wi 0。 你需要将所有边权为 -1 的边都修改为范围 [1, 2 * 10^9] 中的 正整数 使得从节点 source 到节点 destination 的 最短距离 为整数 target 。如果有 多种 修改方案可以使 source 和 destination 之间的最短距离等于 target 你可以返回任意一种方案。 如果存在使 source 到 destination 最短距离为 target 的方案请你按任意顺序返回包含所有边的数组包括未修改边权的边。如果不存在这样的方案请你返回一个 空数组 。 注意你不能修改一开始边权为正数的边。 1 n 100 1 edges.length n * (n - 1) / 2 edges[i].length 3 0 ai, bi n wi -1 或者 1 wi 107 ai ! bi 0 source, destination n source ! destination 1 target 109 输入的图是连通图且没有自环和重边。
分析 难点分析
任意边的权加1则任意两点的最短路径要么不变要么加1。前者对应至少有一条最短路径不经过此边后者对应所有最短路径都经过此边。首先所有可变权的边设置为1每轮选择一条可以加权的权边加1。时间复杂度O(109*边数)时间复杂度太高改成按顺序处理可变权边就可以用二分法了时间复杂度降为O(log(109*边数)约等于O(40)。
时间复杂度
每轮需要寻找最短路径由于是稠密图所以用朴素迪氏寻找单源路径。总时间复杂度是O(log(10^9边数)nn),越O(40100*100)。
大致流程
如果可边权边设置为最大值如果最短路径小于目标值返回空。 如果可边权边设置为最小值如果最短路径大于目标值返回空。 二分寻找合适的值。
代码讲解
m_vMore0Edge,m_vLess0Edge分别记录不可变权边和可边权边。 CNeiBo3 是封装好的类用与将权边转成邻接表。 CN2Dis 是封装好的求单源最短路径的类。 Do求最短路径。 CalLess0Edge将增加的权分配给各边。
核心代码
//朴素迪杰斯特拉算法
class CN2Dis { public: CN2Dis(int iSize) :m_iSize(iSize), DIS(m_vDis), PRE(m_vPre) {
} void Cal(int start, const vectorvectorpairint, int vNeiB) { m_vDis.assign(m_iSize, -1); m_vPre.assign(m_iSize, -1); vector vDo(m_iSize);//点是否已处理 auto AddNode [](int iNode) { //const int iPreNode m_vPre[iNode]; long long llPreDis m_vDis[iNode]; vDo[iNode] true;for (const auto it : vNeiB[iNode]){if (vDo[it.first]){continue;}if ((-1 m_vDis[it.first]) || (it.second llPreDis m_vDis[it.first])){m_vDis[it.first] it.second llPreDis;m_vPre[it.first] iNode;}}long long llMinDis LLONG_MAX;int iMinIndex -1;for (int i 0; i m_vDis.size(); i){if (vDo[i]){continue;}if (-1 m_vDis[i]){continue;}if (m_vDis[i] llMinDis){iMinIndex i;llMinDis m_vDis[i];}}return (LLONG_MAX llMinDis) ? -1 : iMinIndex;
};int next start;
m_vDis[start] 0;
while (-1 ! (next AddNode(next)));} void Cal(int start, const vectorvector mat) { m_vDis.assign(m_iSize, LLONG_MAX); m_vPre.assign(m_iSize, -1); vector vDo(m_iSize);//点是否已处理 auto AddNode [](int iNode) { long long llPreDis m_vDis[iNode]; vDo[iNode] true; for (int i 0; i m_iSize; i) { if (vDo[i]) { continue; } const long long llCurDis mat[iNode][i]; if (llCurDis 0) { continue; } m_vDis[i] min(m_vDis[i], m_vDis[iNode] llCurDis); } long long llMinDis LLONG_MAX; int iMinIndex -1; for (int i 0; i m_iSize; i) { if (vDo[i]) { continue; } if (m_vDis[i] llMinDis) { iMinIndex i; llMinDis m_vDis[i]; } } if (LLONG_MAX llMinDis) { return -1; } m_vPre[iMinIndex] iNode;return iMinIndex;
};int next start;
m_vDis[start] 0;
while (-1 ! (next AddNode(next)));} const vector DIS; const vector PRE; private: const int m_iSize; vector m_vDis;//各点到起点的最短距离 vector m_vPre;//最短路径的前一点 };
class CNeiBo3 { public: CNeiBo3(int n, vectorvector edges, bool bDirect, int iBase 0) { m_vNeiB.resize(n); AddEdges(edges, bDirect, iBase); } CNeiBo3(int n) { m_vNeiB.resize(n); } void AddEdges(vectorvector edges, bool bDirect, int iBase 0) { for (const auto v : edges) { m_vNeiB[v[0] - iBase].emplace_back(v[1] - iBase, v[2]); if (!bDirect) { m_vNeiB[v[1] - iBase].emplace_back(v[0] - iBase, v[2]); } } } vectorvectorstd::pairint,int m_vNeiB; };
class Solution {
public:vectorvectorint modifiedGraphEdges(int n, vectorvectorint edges, int source, int destination, int target) {m_n n;m_src source;m_dest destination;for (const auto v : edges){if (-1 v[2]){m_vLess0Edge.emplace_back(v);}else{m_vMore0Edge.emplace_back(v);}}long long left 0, r (long long)(1000 * 1000 * 1000-1)* m_vLess0Edge.size()1;while (r - left 1){const auto mid left (r - left) / 2;const long long ll Do(mid);if ( ll target ){m_vLess0Edge.insert(m_vLess0Edge.end(), m_vMore0Edge.begin(), m_vMore0Edge.end());return m_vLess0Edge;}else if (ll target){r mid;}else{left mid;}}const long long ll Do(left);if (target ll){m_vLess0Edge.insert(m_vLess0Edge.end(), m_vMore0Edge.begin(), m_vMore0Edge.end());return m_vLess0Edge;}return {};}long long Do(long long llAdd){CalLess0Edge(llAdd);CNeiBo3 neiBo(m_n);neiBo.AddEdges(m_vMore0Edge,false);neiBo.AddEdges(m_vLess0Edge, false);CN2Dis dis(m_n);dis.Cal(m_src, neiBo.m_vNeiB);return dis.DIS[m_dest];}void CalLess0Edge(long long llAdd){for (auto v : m_vLess0Edge){const int curAdd (int)min(llAdd, (long long)1000 * 1000 * 1000 - 1);v[2] 1 curAdd;llAdd - curAdd;}}int m_n;int m_src;int m_dest;vectorvectorint m_vMore0Edge,m_vLess0Edge;
};测试用例
由于本文篇幅过长请自行下载测试样例。 其它
视频课程
要是你认为本篇难道较大不好入手推荐你先学习基础算法的课程我已完成部分余下部分持续更新中就在CSDN学院。 https://edu.csdn.net/course/detail/38771
C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
测试环境
操作系统win7 开发环境 VS2019 C17
相关下载
如果你想观其大略建设下载《闻缺陷则喜算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653
博主想队大家说的话墨家名称的来源有所得以墨记之。闻缺陷则喜的来由早发现早修改问题成本更低程序是龙算法是睛
