Roads in Berland

Roads in Berland

Floyed 变种,图论

题意

给你\(n\) 个城市之间最短路的邻接矩阵，再给你\(k\) 个修改的路径

问你每次修改之后，最短路的总和是多少

思路

对于每次修改，我们都遍历整个图，看看修改过的道路是否能缩短其他两点之间的距离

如果能缩短，就用总的最短路距离减去他们的差值

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define endl '\n'
const int N = 400;
int g[N][N],n,m;
LL sum = 0;
void modify(int a,int b,int c) {
    if(g[a][b] > c) {
        sum -= g[a][b] - c;
        g[a][b] = g[b][a] = c;
    }
    return ;
}
int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,k,a,b,c;
    cin >> n;
    for(int i = 1;i <= n; ++i)
        for(int j = 1;j <= n; ++j) {
            cin >> g[i][j];
            if(i > j) sum += g[i][j];
        }
    cin >> k;
    while(k --) {
        cin >> a >> b >> c;
        modify(a,b,c);
        for(int i = 1;i <= n; ++i) {
            for(int j = 1;j <= n; ++j) {
                modify(i,j,g[i][a] + c + g[b][j]);
            }
        }
        cout << sum << endl;
    }
    return 0;
}