Submission #67950212

---

Source Code Expand

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

const ll inf=1e15;
const int Maxn=1010;
int n,m,k,T,Q;
ll f[Maxn][Maxn];

inline void Snc(int x,int y){
	for(int i=1;i<=n+1;i++)
		for(int j=1;j<=n+1;j++)
			f[i][j]=min(f[i][j],f[i][x]+f[x][y]+f[y][j]),
			f[i][j]=min(f[i][j],f[i][y]+f[y][x]+f[x][j]);
}
inline void add(int x){
	f[x][n+1]=min(f[x][n+1],1ll*T); Snc(x,n+1);
	f[n+1][x]=0; Snc(n+1,x);	
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n+1;i++)
		for(int j=1;j<=n+1;j++)
			f[i][j]=inf;
	for(int i=1;i<=n+1;i++) f[i][i]=0;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		f[u][v]=f[v][u]=min(f[u][v],1ll*w);
	}
	for(int u=1;u<=n+1;u++)
		for(int i=1;i<=n+1;i++)
			for(int j=1;j<=n+1;j++)
				f[i][j]=min(f[i][j],f[i][u]+f[u][j]);

	cin>>k>>T;
	for(int i=1;i<=k;i++){
		int d; cin>>d;
		add(d);
	}

	cin>>Q;
	while(Q--){
		int opt,x,y,t;
		cin>>opt;
		if(opt==1){
			cin>>x>>y>>t;
			f[x][y]=min(f[x][y],t*1ll);
			f[y][x]=min(f[y][x],t*1ll);
			Snc(x,y);
		}
		if(opt==2){
			cin>>x; add(x);
		}
		if(opt==3){
			ll ans=0;
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					if(f[i][j]!=inf) ans+=f[i][j];
			cout<<ans<<"\n";
		}
	}


	return 0;
}

Submission Info

Judge Result