Submission #67981215

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll INF = 1e18;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, M;
    cin >> N >> M;
    
    ll dp[501][501];
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= N; j++) {
            dp[i][j] = INF;
        }
        dp[i][i] = 0;
    }
    
    for (int i = 1; i <= M; i++) {
        int A, B; ll C;
        cin >> A >> B >> C;
        dp[A][B] = dp[B][A] = min(dp[A][B], 2*C);
    }
    
    int K; ll T;
    cin >> K >> T;
    for (int i = 1; i <= K; i++) {
        int D;
        cin >> D;
        dp[0][D] = dp[D][0] = T;
    }
    
    for (int k = 0; k <= N; k++)
        for (int i = 0; i <= N; i++)
            for (int j = 0; j <= N; j++)
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
                
    auto update_edge = [&dp, N](int A, int B, ll C) {
        dp[A][B] = dp[B][A] = min(dp[A][B], C);
        for (int i = 0; i <= N; i++)
            for (int j = 0; j <= N; j++)
                dp[i][j] = min({dp[i][j], dp[i][A] + dp[A][B] + dp[B][j], dp[i][B] + dp[B][A] + dp[A][j]});
    };
    
    int Q;
    cin >> Q;
    while (Q--) {
        int cmd;
        cin >> cmd;
        if (cmd == 1) {
            int A, B; ll C;
            cin >> A >> B >> C;
            update_edge(A, B, 2*C);
        } else if (cmd == 2) {
            int D;
            cin >> D;
            update_edge(0, D, T);
        } else {
            ll sum = 0;
            for (int i = 1; i <= N; i++)
                for (int j = 1; j <= N; j++)
                    sum += (dp[i][j] < INF) * dp[i][j];
            cout << sum/2 << "\n";
        }
    }
    return 0;
}

Submission Info

Judge Result