本篇源码下载
1.12.1. 题目
给你一个 n 个节点的 无向带权连通 图，节点编号为 0 到 n - 1 ，再给你一个整数数组 edges ，其中 edges[i] = [ai, bi, wi] 表示节点 ai 和 bi 之间有一条边权为 wi 的边。
部分边的边权为 -1（wi = -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 vector<vector<pair<int, 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 vector<vector>& 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, vector<vector>& edges, bool bDirect, int iBase = 0) { m_vNeiB.resize(n); AddEdges(edges, bDirect, iBase); } CNeiBo3(int n) { m_vNeiB.resize(n); } void AddEdges(vector<vector>& 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]); } } } vector<vector<std::pair<int,int>>> m_vNeiB; };
class Solution { public: vector<vector<int>> modifiedGraphEdges(int n, vector<vector<int>>& 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; vector<vector<int>> m_vMore0Edge,m_vLess0Edge; };
测试用例
由于本文篇幅过长，请自行下载测试样例。
其它
视频课程
要是你认为本篇难道较大，不好入手，推荐你先学习基础算法的课程，我已完成部分，余下部分持续更新中，就在CSDN学院。
https://edu.csdn.net/course/detail/38771
C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统：win7 开发环境： VS2019 C++17
相关下载
如果你想观其大略，建设下载《闻缺陷则喜算法册》doc版
