Submission #67944705

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const long long inf = 1e18+3;

void solve() {
	int n, m;
	cin >> n >> m;
	vector<vector<long long>> adjm(n+1, vector<long long>(n+1, inf));
	for (int i=0; i<m; i++) {
		int a, b; long long c;
		cin >> a >> b >> c;
		a--; b--;
		long long mn = min(adjm[a][b], c);
		adjm[a][b] = adjm[b][a] = mn;
	}
	int c; long long t;
	cin >> c >> t;
	for (int i=0; i<c; i++) {
		int u;
		cin >> u;
		adjm[u-1][n] = t;
		adjm[n][u-1] = 0;
	}

	vector<vector<long long>> dist(n+1, vector<long long>(n+1, inf));
	for (int i=0; i<=n; i++) {
		for (int j=0; j<=n; j++) {
			dist[i][j] = (i == j ? 0 : adjm[i][j]);
		}
	}
	for (int k=0; k<=n; k++) {
		for (int i=0; i<=n; i++) {
			for (int j=0; j<=n; j++) {
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}

	long long ans = 0;
	for (int i=0; i<n; i++) {
		for (int j=0; j<n; j++) {
			ans += (dist[i][j] == inf ? 0 : dist[i][j]);
		}
	}

	int q;
	cin >> q;
	while (q--) {
		int type;
		cin >> type;
		if (type == 1) {
			int u, v; long long w;
			cin >> u >> v >> w;
			u--; v--;

			long long mn = min(adjm[u][v], w);
			adjm[u][v] = adjm[v][u] = mn;
			for (int i=0; i<=n; i++) {
				for (int j=0; j<=n; j++) {
					if (i < n && j < n) ans -= (dist[i][j] == inf ? 0 : dist[i][j]);
					dist[i][j] = min({
						dist[i][j],
						dist[i][u] + adjm[u][v] + dist[v][j],
						dist[i][v] + adjm[v][u] + dist[u][j]
					});
					if (i < n && j < n) ans += (dist[i][j] == inf ? 0 : dist[i][j]);
				}
			}

		} else if (type == 2) {
			int u;
			cin >> u;
			u--;
			adjm[u][n] = t;
			adjm[n][u] = 0;
			for (int i=0; i<=n; i++) {
				for (int j=0; j<=n; j++) {
					if (i < n && j < n) ans -= (dist[i][j] == inf ? 0 : dist[i][j]);
					dist[i][j] = min({
						dist[i][j],
						dist[i][u] + adjm[u][n] + dist[n][j],
						dist[i][n] + adjm[n][u] + dist[u][j]
					});
					if (i < n && j < n) ans += (dist[i][j] == inf ? 0 : dist[i][j]);
				}
			}
		} else {
			cout << ans << '\n';
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int tcs = 1;
	// cin >> tcs;
	while (tcs--) {
		solve();
	}
	return 0;
}

Submission Info

Judge Result