题目描述
给你一个 n
个节点的 无向带权连通 图,节点编号为 0
到 n - 1
,再给你一个整数数组 edges
,其中 edges[i] = [a_i, b_i, w_i]
表示节点 a_i
和 b_i
之间有一条边权为 w_i
的边。
部分边的边权为 -1
(wi = -1
),其他边的边权都为 正 数(wi > 0
)。
你需要将所有边权为 -1
的边都修改为范围 [1, 2 * 10^9]
中的 正整数,使得从节点 source
到节点 destination
的 最短距离 为整数 target
。如果有 多种 修改方案可以使 source
和 destination
之间的最短距离等于 target
,你可以返回任意一种方案。
如果存在使 source
到 destination
最短距离为 target
的方案,请你按任意顺序返回包含所有边的数组(包括未修改边权的边)。如果不存在这样的方案,请你返回一个 空数组。
注意:你不能修改一开始边权为正数的边。
样例
输入:
n = 5, edges = [[4,1,-1],[2,0,-1],[0,3,-1],[4,3,-1]]
source = 0, destination = 1, target = 5
输出:[[4,1,1],[2,0,1],[0,3,3],[4,3,1]]
解释:上图展示了一个满足题意的修改方案,从 0 到 1 的最短距离为 5。
输入:
n = 3, edges = [[0,1,-1],[0,2,5]]
source = 0, destination = 2, target = 6
输出:[]
解释:上图是一开始的图。
没有办法通过修改边权为 -1 的边,使得 0 到 2 的最短距离等于 6,所以返回一个空数组。
输入:
n = 4, edges = [[1,0,4],[1,2,3],[2,3,5],[0,3,-1]]
source = 0, destination = 2, target = 6
输出:[[1,0,4],[1,2,3],[2,3,5],[0,3,1]]
解释:上图展示了一个满足题意的修改方案,从 0 到 2 的最短距离为 6。
限制
1 <= n <= 100
1 <= edges.length <= n * (n - 1) / 2
edges[i].length == 3
0 <= a_i, b_i < n
w_i = -1 或者 1 <= w_i <= 10^7
a_i != b_i
0 <= source, destination < n
source != destination
1 <= target <= 10^9
- 输入的图是连通图,且没有自环和重边。
算法1
(Dijkstra,暴力枚举) $O(mn^2)$
- 先求出不含有 $-1$ 边的最短路,如果起点到终点的距离小于 $target$,则不存在方案;如果起点到终点的距离等于 $target$,则所有 $-1$ 的边修改为无穷大,返回。
- 否则,需要借住 $-1$ 的边来使得最短路变小达到 $target$。
- 按任意顺序枚举 $-1$ 的边,先假设边权为 $-1$,并再次求出起点到终点的最短路 $r$,如果此时最短路小于等于 $target$,则修改这条边的边权为 $target - r + 1$,然后返回答案。
- 如果此时最短路大于 $target$,则说明仅靠当前这些 $-1$ 边还不能让最短路降低,则修改边权为 $1$ 后记录枚举下一个 $-1$ 边。
- 如果直到最后,起点到终点的最短路都大于 $target$,则不存在方案。
时间复杂度
- 对于每条 $-1$ 边,都需要跑一次最短路算法,由于是稠密图,求最短路的时间复杂度为 $O(n^2)$,故总时间复杂度为 $O(mn^2)$。
空间复杂度
- 需要 $O(n^2)$ 的额外空间存储图,距离数组和其他数据结构。
C++ 代码
const int N = 110;
const int INF = 2000000000;
class Solution {
private:
int w[N][N], d[N];
bool v[N];
int dijkstra(int n, int s, int t) {
for (int i = 0; i < n; i++) {
d[i] = INF;
v[i] = false;
}
d[s] = 0;
for (int it = 0; it < n; it++) {
int mind = INF, x;
for (int u = 0; u < n; u++)
if (!v[u] && mind > d[u]) {
mind = d[u];
x = u;
}
if (mind == INF)
break;
v[x] = true;
for (int y = 0; y < n; y++)
if (w[x][y] != -1 && w[x][y] != INF)
d[y] = min(d[y], d[x] + w[x][y]);
}
return d[t];
}
void get_ans(vector<vector<int>> &edges) {
for (auto &e : edges)
if (e[2] == -1)
e[2] = INF;
}
public:
vector<vector<int>> modifiedGraphEdges(int n, vector<vector<int>>& edges,
int source, int destination, int target
) {
const int m = edges.size();
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
w[i][j] = INF;
vector<int> modified;
for (int i = 0; i < m; i++) {
int x = edges[i][0], y = edges[i][1], z = edges[i][2];
w[x][y] = w[y][x] = z;
if (z == -1)
modified.push_back(i);
}
int r = dijkstra(n, source, destination);
if (r < target)
return {};
if (r == target) {
get_ans(edges);
return edges;
}
for (int i : modified) {
auto &e = edges[i];
w[e[0]][e[1]] = w[e[1]][e[0]] = 1;
int r = dijkstra(n, source, destination);
if (r <= target) {
e[2] = target - r + 1;
get_ans(edges);
return edges;
}
e[2] = 1;
}
return {};
}
};
算法2
(Dijkstra,思维题) $O(n^2)$
- 算法 1 中每次都重新求最短路会浪费许多时间,考虑到 Dijkstra 算法实现过程中,每一轮找到的点 $x$,必定已经得到了从起点的最短路,所以修改 $x$ 出发的可修改边,不会影响到已经遍历点的最短路,故可以按这个顺序来避免每次都重新计算所有点的最短路。
- 用点 $x$ 更新其他点的过程中,假设对于点 $y$ 的路径 $(x, y)$ 是可修改的,则可以根据当前从起点到 $x$ 的最短路,加上当前边的长度(待定),在加上 $y$ 到终点(不经过修改边)的最短路,与 $target$ 的关系,得到当前边的长度应该被修改为多少,具体如下:
- 如果 $y$ 到终点(不经过修改边)的最短路为正无穷,或当前从起点到 $x$ 的最短路加 1 再加 $y$ 到终点(不经过修改边)的最短路大于 $target$,则只能让当前边修改为 $1$。
- 否则,修改当前边的边权为恰好满足上述三个值相加为 $target$。
- 这里可能会有一个问题,为什么最后加上的是 $y$ 到终点(不经过修改边)的最短路,如果 $y$ 到终点的最短路是之前修改过的边呢?这里不用担心,如果 $y$ 到终点的最短路是之前修改过的边,则说明 $y$ 最终并不能成为最短路上的点,这样 $(x,y)$ 的值对结果无影响。
- 所以,需要一次预处理找到终点到所有点不经过修改边的最短路。
时间复杂度
- 两次 Dijkstra,故总时间复杂度为 $O(n^2)$。
空间复杂度
- 需要 $O(n^2)$ 的额外空间存储图,距离数组和其他辅助数据结构。
C++ 代码
const int N = 110;
const int INF = 2000000000;
class Solution {
private:
int w[N][N], modified[N][N];
int dr[N], d[N];
bool v[N];
void dijkstra(int n, int s) {
for (int i = 0; i < n; i++) {
dr[i] = INF;
v[i] = false;
}
dr[s] = 0;
for (int it = 0; it < n; it++) {
int mind = INF, x;
for (int u = 0; u < n; u++)
if (!v[u] && mind > dr[u]) {
mind = dr[u];
x = u;
}
if (mind == INF)
break;
v[x] = true;
for (int y = 0; y < n; y++)
if (w[x][y] != -1 && w[x][y] != INF)
dr[y] = min(dr[y], dr[x] + w[x][y]);
}
}
void dijkstra_solve(int n, int s, vector<vector<int>> &edges, int target) {
for (int i = 0; i < n; i++) {
d[i] = INF;
v[i] = false;
}
d[s] = 0;
for (int it = 0; it < n; it++) {
int mind = INF, x;
for (int u = 0; u < n; u++)
if (!v[u] && mind > d[u]) {
mind = d[u];
x = u;
}
if (mind == INF)
break;
v[x] = true;
for (int y = 0; y < n; y++) {
if (w[x][y] == INF)
continue;
if (w[x][y] == -1) {
if (dr[y] == INF || d[x] + 1 + dr[y] > target) {
edges[modified[x][y]][2] = 1;
w[x][y] = w[y][x] = 1;
} else {
edges[modified[x][y]][2] = target - d[x] - dr[y];
w[x][y] = w[y][x] = target - d[x] - dr[y];
}
}
d[y] = min(d[y], d[x] + w[x][y]);
}
}
}
void get_ans(vector<vector<int>> &edges) {
for (auto &e : edges)
if (e[2] == -1)
e[2] = INF;
}
public:
vector<vector<int>> modifiedGraphEdges(int n, vector<vector<int>>& edges,
int source, int destination, int target
) {
const int m = edges.size();
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
w[i][j] = INF;
for (int i = 0; i < m; i++) {
int x = edges[i][0], y = edges[i][1], z = edges[i][2];
w[x][y] = w[y][x] = z;
if (z == -1)
modified[x][y] = modified[y][x] = i;
}
dijkstra(n, destination);
if (dr[source] < target)
return {};
if (dr[source] == target) {
get_ans(edges);
return edges;
}
dijkstra_solve(n, source, edges, target);
if (d[destination] == target) {
get_ans(edges);
return edges;
}
return {};
}
};