Submission #67943870

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define overload4(a, b, c, d, name, ...) name
#define rep1(n) for (ll i = 0; i < n; ++i)
#define rep2(i, n) for (ll i = 0; i < n; ++i)
#define rep3(i, a, b) for (ll i = a; i < b; ++i)
#define rep4(i, a, b, c) for (ll i = a; i < b; i += c)
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
void solve();
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    ll t = 1;
    // cin >> t;
    for (int i = 1; i <= t; i++) solve();
    return 0;
}
ll dy[4] = {1, 0, -1, 0}, dx[4] = {0, 1, 0, -1};
void solve() {
    ll n, m;
    cin >> n >> m;
    constexpr ll INF = 1e18;
    vector<vector<ll>> dist(n + 1, vector<ll>(n + 1, INF));
    for (ll i = 0; i < n + 1; i++) dist[i][i] = 0;
    rep(i, m) {
        ll a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        dist[a][b] = min(dist[a][b], c);
        dist[b][a] = min(dist[b][a], c);
    }
    ll k, T;
    cin >> k >> T;
    set<ll> st;
    vector<ll> d(k);
    rep(i, k) {
        cin >> d[i];
        d[i]--;
        st.insert(d[i]);
        dist[d[i]][n] = 0;
        dist[n][d[i]] = T;
    }
    rep(k, n + 1) rep(i, n + 1) rep(j, n + 1) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    ll res = 0;
    rep(i, n) rep(j, n) {
        if (dist[i][j] == INF) continue;
        res += dist[i][j];
    }
    ll q;
    cin >> q;
    auto update = [&](ll a, ll b, ll c) {
        if (dist[a][b] > c) {
            if (a != n and b != n) {
                if (dist[a][b] != INF) res -= dist[a][b];
                res += c;
            }
            dist[a][b] = c;
        }
    };
    while (q--) {
        ll t;
        cin >> t;
        if (t == 1) {
            ll a, b, c;
            cin >> a >> b >> c;
            a--, b--;
            if (dist[a][b] <= c) continue;
            rep(i, n + 1) rep(j, n + 1) {
                update(i, j, dist[i][a] + c + dist[b][j]);
                update(i, j, dist[i][b] + c + dist[a][j]);
            }
        } else if (t == 2) {
            ll x;
            cin >> x;
            x--;
            if (st.count(x)) continue;
            st.insert(x);
            rep(i, n + 1) rep(j, n + 1) {
                update(i, j, dist[i][x] + dist[n][j]);
                update(i, j, dist[i][n] + T + dist[x][j]);
            }
        } else {
            cout << res << "\n";
        }
    }
}

Submission Info

Judge Result