Submission #353857

---

Source Code Expand

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <map>
#include <functional>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
 
const int NOROAD = 1000000;
int dp[401][401];

int main() {
	cin.tie(0);
    ios::sync_with_stdio(false);
    
    for(auto &i : dp) for(auto &j : i) j = NOROAD;
    
    int N, M;
    cin >> N >> M;
    
    for(int i = 0; i < M; i++){
        int A, B, C;
        cin >> A >> B >> C;
        A--; B--;
        dp[A][B] = dp[B][A] = C;
    }
    
    auto minRoute = [&](int c) -> void{
        //for(int c = 0; c < N; c++){
            for(int f = 0; f < N; f++){
                for(int t = 0; t < N; t++){
                    if(f == t) continue;
                    if(c == f || c == t) continue;
                    //cout << f << " " << t << " " << dp[f][t] << " " << c << " " << dp[f][c] << " " << dp[c][t] << endl;
                    dp[f][t] = min(dp[f][t], dp[f][c] + dp[c][t]);
                }
                //dp[f][t] = min(dp[f][t], dp[t][f]);
            }
        //}
    };
    //minRoute();
    
    auto solve = [&](){
        //minRoute();
        ll sum = 0;
        for(int i = 0; i < N; i++){
            for(int j = i+1; j < N; j++){
                //cout << dp[i][j] << " ";
                sum += dp[i][j];
            }
            //cout << endl;
        }
        return sum;
    };
    
    int K;
    cin >> K;
    
    for(int c = 0; c < N; c++) minRoute(c);
    ll ans = solve();
    
    for(int i = 0; i < K; i++){
        int X, Y, Z;
        cin >> X >> Y >> Z;
        X--; Y--;
        if(dp[X][Y] <= Z && dp[Y][X] <= Z){
            cout << ans << endl;
            continue;
        }
        dp[X][Y] = dp[Y][X] = Z;
        minRoute(X);
        minRoute(Y);
        
        ans = solve();
        cout << ans << endl;
    }
    
	return 0;
}

Submission Info

Judge Result