题目描述

难度分:$1546$

输入$n(2 \leq n \leq 300)$，$m(0 \leq m \leq \frac{n \times (n-1)}{2})$，$q(1 \leq q \leq 2 \times 10^5)$，表示一个$n$点$m$边的无向图。保证图中无自环和重边。

然后输入$m$条边，每条边输入$x$，$y$，$w(1 \leq w \leq 10^9)$，表示一条边权为$w$的无向边连接$x$和$y$。节点编号从$1$开始。

然后输入$q$个询问，格式如下：

1 i：删掉输入的第$i(1 \leq i \leq 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 \leq 300$，比较容易想到$Floyd$算法。我们知道删边之后更新两点之间的最短路是比较困难的，但是加边就不一样了，对于一张图，如果往其中加一条边，可以$O(n^2)$来更新$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(n^3)$处理出距离矩阵。然后倒序遍历每条查询，一旦碰到删边操作就$O(n^2)$加边更新距离矩阵$dist$。否则就直接查表$dist[x][y]$，如果是正无穷，本条询问的答案就是$-1$。

倒序遍历完所有询问之后，再正序输出所有答案就可以了。

复杂度分析

时间复杂度

$Floyd$算法预处理的时间复杂度为$O(n^3)$。遍历每条询问，如果是查表，时间复杂度就是$O(1)$；如果是加边，时间复杂度就是$O(n^2)$。而加边操作最多就是$O(n)$级别，所以处理所有询问的时间复杂度就是$O(q+n^3)$。因此，整个算法的时间复杂度为$O(q+n^3)$。

空间复杂度

空间消耗在于$Floyd$算法点对之间的距离矩阵，即$O(n^2)$，这也是整个算法的额外空间复杂度。

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;
}