本文最后更新于：2023年6月12日 晚上 18:44
力扣2699题题解。
2699
参考了灵神的题解，但感觉对于第二次Dijkstra的正确性有点模糊，重新整理了一下思路。
（以下将所有权值为-1的边视作【可修改边】） #### 第一次Dijkstra：
先将所有为-1（【可修改边】）的边看作1，以求得理论最小路径。
获得 source 到所有点的距离 dist1[] ，以及最短路径 minDist1 =
dist1[destination]
判断结果：
若 minDist1 > target，则无解。返回空数组。
若 minDist1 ==
target，则成功，返回当前全部-1修改为1的边集。
若 minDist1 <
target，则可能可以通过增大一些【可修改边】的值（目前为最小的1），使得最短路径增大。进行第二次Dijkstra。
（但也可能把所有【可修改边】都增大后最短路径依然不变，因为此时
minDist1 上没有【可修改边】）
第二次Dijkstra：
修改第一次最短路径上的【可修改边】，使得这条路径的权值和为target。
同时将其他【可修改边】的权值调的够大，使之不会影响到第二次最短路径为第一次最短路径。
获得 source 到所有点的距离 dist2[]，以及最短路径 minDist2 =
dist2[destination]
如果遇到【可修改边】的情况，则进行增大，增大策略如下：
增大策略（其中Dijkstra是正在检查节点x，然后检查到了【可修改边x-y】）：
source - x - y - destination
这是可能成为最短路径的路径
要成为最短路径target，需满足 dist2[x] + W +
E[y,destination] == target
其中：
dist2[x] 为第二次Dijkstra所获得的 source 到 x
最短距离的准确值
W 为【可修改边x-y】应该要修改成的值
E[y,destination] 为 y 到 destination
的最短距离的不准确值，E[y,destination] ==
minDist1 - dist1[y]
情况判断：
如果y在第一次的最短路径上：
- minDist1 == 起点到y的最短距离dist1[y] +
y到终点的最短距离
- E[y,destination] == y 到终点的最短距离 == minDist1 -
起点到y的最短距离dist1[y]
如果y不在第一次的最短路径上：
minDist1 < 起点到y的最短距离 +
y到终点的最短距离
E[y,destination] == y 到终点的最短距离 < minDist1 -
起点到y的最短距离dist1[y]
此时会把W修改得过大，使得经过这条边的最短路径大于target，但正因为这样，它不会影响到第一次的最短路径。
我们必须找到第一次最短路径上的【可修改边】并合理增大它的权值，使得这条路径权值和为target。
如果第一次最短路径上没有【可修改边】，即使增大了其他路径上的【可修改边】，最短路径也不会变化，依然是第一次最短路径，此时minDist2
< target无解。
最终我们把最短路径上的【可修改边】修改为合理值，并把其他路径上的【可修改边】的值改得过大，避免影响到最短路径。
判断结果：
- 若 minDist2 == target，则成功，返回修改权值后的边集。
- 若 minDist2 <
target，则无解。（第一次最短路径上没有【可修改边】）返回空数组。
- 不存在 minDist2 > target 的情况。
时间复杂度： O((|V|+|E|)*log|E|)
空间复杂度： O(n^2)
我自己按照思路写的比较粗略的C++代码如下，或许改为朴素版还有优化的空间：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
| class Solution {
public:
vector<vector<int>> modifiedGraphEdges(int n, vector<vector<int>>& edges, int source, int destination, int target) {
vector<vector<int>> graph(n, vector<int>(n, 0));
for(auto &e : edges) {
graph[e[1]][e[0]] = graph[e[0]][e[1]] = e[2];
}
vector<int> dist1(n, INT_MAX);
dist1[source] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
vector<int> visited(n, 0);
pq.push({0, source});
while(!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
visited[u] = 1;
for(int v = 0; v < n; ++v) {
if(visited[v] || graph[u][v] == 0) continue;
int w = abs(graph[u][v]);
if(dist1[v] > dist1[u] + w) {
dist1[v] = dist1[u] + w;
pq.push({dist1[v], v});
}
}
}
int minDist1 = dist1[destination];
if(minDist1 > target) return vector<vector<int>>{};
if(minDist1 == target) {
for(auto &e : edges) if(e[2] == -1) e[2] = 1;
return edges;
}
vector<int> dist2(n, INT_MAX);
dist2[source] = 0;
pq.push({0, source});
fill(visited.begin(), visited.end(), 0);
while(!pq.empty()) {
auto [d, x] = pq.top();
pq.pop();
visited[x] = 1;
for(int y = 0; y < n; ++y) {
if(visited[y] || graph[x][y] == 0) continue;
if(graph[x][y] == -1) {
int E = minDist1 - dist1[y];
int W = target - dist2[x] - E;
graph[x][y] = graph[y][x] = (W < 1 ? 1 : W);
}
if(dist2[y] > dist2[x] + graph[x][y]) {
dist2[y] = dist2[x] + graph[x][y];
pq.push({dist2[y], y});
}
}
}
int minDist2 = dist2[destination];
if(minDist2 == target){
for(auto &e : edges) if(e[2] == -1) e[2] = graph[e[0]][e[1]];
return edges;
}
return vector<vector<int>>{};
}
};
|
结果