题目描述
难度分:1546
输入n(2≤n≤300),m(0≤m≤n×(n−1)2),q(1≤q≤2×105),表示一个n点m边的无向图。保证图中无自环和重边。
然后输入m条边,每条边输入x,y,w(1≤w≤109),表示一条边权为w的无向边连接x和y。节点编号从1开始。
然后输入q个询问,格式如下:
1 i
:删掉输入的第i(1≤i≤m)条边。保证这条边没被删除。
2 x y
:输出从x到y的最短距离。如果无法到达,输出−1。
保证第一种询问不超过300个。
输入样例1
3 3 5
1 2 5
1 3 10
2 3 6
2 1 3
1 2
2 1 3
1 1
2 1 3
输出样例1
10
11
-1
输入样例2
4 6 6
2 3 1
2 4 1
3 4 1
1 2 1
1 3 1
1 4 1
1 4
1 5
1 6
2 1 2
2 1 3
2 1 4
输出样例2
-1
-1
-1
算法
Floyd算法
n≤300,比较容易想到Floyd算法。我们知道删边之后更新两点之间的最短路是比较困难的,但是加边就不一样了,对于一张图,如果往其中加一条边,可以O(n2)来更新Floyd的距离矩阵。双重循环枚举点对,对于给定的点对(u,v),加边(x,y,w)之后,考虑将u引到x经过这条边到y再到v(或者将u引到y经过这条边到x再到v),看能不能缩短加边前的距离dist[u][v]=min(dist[u][v],w+dist[u][x]+dist[y][v],w+dist[u][y]+dist[x][v])。
于是我们先将该删的边全部删掉,利用Floyd算法O(n3)处理出距离矩阵。然后倒序遍历每条查询,一旦碰到删边操作就O(n2)加边更新距离矩阵dist。否则就直接查表dist[x][y],如果是正无穷,本条询问的答案就是−1。
倒序遍历完所有询问之后,再正序输出所有答案就可以了。
复杂度分析
时间复杂度
Floyd算法预处理的时间复杂度为O(n3)。遍历每条询问,如果是查表,时间复杂度就是O(1);如果是加边,时间复杂度就是O(n2)。而加边操作最多就是O(n)级别,所以处理所有询问的时间复杂度就是O(q+n3)。因此,整个算法的时间复杂度为O(q+n3)。
空间复杂度
空间消耗在于Floyd算法点对之间的距离矩阵,即O(n2),这也是整个算法的额外空间复杂度。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 310;
const LL INF = 1e18;
int n, m, q;
LL d[N][N];
int main() {
scanf("%d%d%d", &n, &m, &q);
vector<array<int, 3>> edges;
for(int i = 1; i <= m; i++) {
int x, y, w;
scanf("%d%d%d", &x, &y, &w);
edges.push_back({x, y, w});
}
unordered_set<int> del;
vector<vector<int>> queries;
for(int index = 0; index < q; index++) {
int t;
scanf("%d", &t);
if(t == 1) {
int i;
scanf("%d", &i);
del.insert(i);
queries.push_back({t, i});
}else {
int x, y;
scanf("%d%d", &x, &y);
queries.push_back({t, x, y});
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(i != j) d[i][j] = INF;
}
}
for(int i = 0; i < m; i++) {
if(del.count(i + 1)) continue;
int x = edges[i][0], y = edges[i][1], w = edges[i][2];
d[x][y] = d[y][x] = w;
}
for(int k = 1; k <= n; k++) {
for(int i = 1; i < n; i++) {
for(int j = i + 1; j <= n; j++) {
d[i][j] = d[j][i] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
vector<LL> ans;
for(int index = q - 1; index >= 0; index--) {
int typ = queries[index][0];
if(typ == 1) {
int idx = queries[index][1];
int x = edges[idx - 1][0], y = edges[idx - 1][1], w = edges[idx - 1][2];
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(i == j) continue;
d[i][j] = min(d[i][j], w + min(d[i][y] + d[x][j], d[i][x] + d[y][j]));
}
}
}else {
int x = queries[index][1], y = queries[index][2];
ans.push_back(d[x][y] == INF? -1: d[x][y]);
}
}
reverse(ans.begin(), ans.end());
for(LL res: ans) {
printf("%lld\n", res);
}
return 0;
}