ABC E 求条
  • 板块学术版
  • 楼主AnotherDream
  • 当前回复4
  • 已保存回复4
  • 发布时间2025/7/26 22:25
  • 上次更新2025/7/27 15:13:08
查看原帖
ABC E 求条
1208546
AnotherDream楼主2025/7/26 22:25
// Problem: E - Development
// Contest: AtCoder - AtCoder Beginner Contest 416
// Date: 2025-07-26 20:00:16
// URL: https://atcoder.jp/contests/abc416/tasks/abc416_e
// Memory Limit: 1024 MB
// Time Limit: 3500 ms
// Author: __int1024
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define fir first
#define sec second
#define debug cerr<<"The code runs successfully.\n";
#define endl '\n'
#define TRACE 1
#define tcout TRACE && cout
#define fst ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define int long long
const int P = 998244353; 
const int Base = 33331;
#ifdef int
const int INF = 0x3f3f3f3f3f3f3f3f;
#else
const int INF = 0x3f3f3f3f;
#endif
const int N = 5e2 + 10, M = 1e6 + 10;
int dist[N][N],n,m,ap,t,q;
vector<pair<int,int>> g[N];
signed main() {
	fst;
	memset(dist,0x3f,sizeof dist);
	cin>>n>>m;
	for(int i=1;i<=n;i++) dist[i][i]=0;
	for(int i=1;i<=m;i++) {
		int u,v,w;
		cin>>u>>v>>w;
		dist[u][v]=dist[v][u]=min(dist[u][v],w);
	}
	cin>>ap>>t;
	for(int i=1;i<=ap;i++) {
		int x;
		cin>>x;
		dist[0][x]=t/2,dist[x][0]=t-t/2;
	}
	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[j][k]);
			}
		}
	}
	// for(int i=1;i<=n;i++) {
		// for(int j=i+1;j<=n;j++) {
			// cout<<dist[i][j]<<" ";
		// }
		// cout<<endl;
	// }
	cin>>q;
	while(q--) {
		int op;
		cin>>op;
		if(op==1) {
			int u,v,w;
			cin>>u>>v>>w;
			dist[u][v]=dist[v][u]=min(dist[u][v],w);
			for(int i=0;i<=n;i++) {
				for(int j=0;j<=n;j++) {
					dist[i][j]=min(dist[i][j],min(dist[i][u]+dist[v][j],dist[i][v]+dist[u][j])+w);
				}
			}
		}
		else if(op==2) {
			int x;
			cin>>x;
			dist[0][x]=t/2;
			dist[x][0]=t-t/2;
			
			for(int i=0;i<=n;i++) {
				for(int j=0;j<=n;j++) {
					dist[i][j]=min(dist[i][j],min(dist[i][0]+dist[x][j]+dist[0][x],dist[i][x]+dist[0][j]+dist[x][0]));
				}
			}
		}
		else {
			int ans=0;
			for(int i=1;i<=n;i++) {
				for(int j=1;j<=n;j++) {
					if(dist[i][j]!=INF) ans+=dist[i][j];
				}
			}
			cout<<ans<<endl;
		}
	}
	return 0;
}

2025/7/26 22:25
加载中...