CFR 25 C. Roads in Berland ( Floyd Warshall )

Problem - 25C - Codeforces
先做完一次MSSP之後，對於每個動態操作可以直接詢問每個兩端，是否用了這條邊之後會更好。
注意題目是說額外新增路，所以是不一定要取的。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300 + 3;
const int MAXK = 300 + 3;
const int MAXC = 1e3 + 3;
#define int long long

int n;
int dis[ MAXN ][ MAXN ];
int ans[ MAXN ];

signed main(){
    cin >> n;
    for( int i = 1; i <= n; ++i )
        for( int j = 1; j <= n; ++j )
            cin >> dis[ i ][ j ];
    int k; cin >> k;
    for( int i = 1; i <= k; ++i ){
        int a, b, c; cin >> a >> b >> c;
        dis[ a ][ b ] = dis[ b ][ a ] = min( dis[ a ][ b ], c );
        for( int p = 1; p <= n; ++p )
            for( int q = 1; q <= n; ++q )
                if( dis[ p ][ q ] > dis[ p ][ a ] + dis[ a ][ b ] + dis[ b ][ q ] )
                    dis[ p ][ q ] = dis[ p ][ a ] + dis[ a ][ b ] + dis[ b ][ q ];
        for( int p = 1; p <= n; ++p )
            for( int q = p + 1; q <= n; ++q )
                ans[ i ] += dis[ p ][ q ];
    }
    for( int i = 1; i <= k; ++i )
        cout << ans[ i ] << ( i == k ? '\n' : ' ' );
    return 0;
}