社区讨论

求调昨晚ABC_e,玄关

学术版参与者 4已保存回复 10

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
10 条
当前快照
1 份
快照标识符
@mdkwdgnp
此快照首次捕获于
2025/07/27 07:44
7 个月前
此快照最后确认于
2025/11/04 03:40
4 个月前
查看原帖
AC×2,WA×27AC\times 2,WA\times 27
CPP
// Problem: E - Development
// Contest: AtCoder - AtCoder Beginner Contest 416
// URL: https://atcoder.jp/contests/abc416/tasks/abc416_e
// Memory Limit: 1024 MB
// Time Limit: 3500 ms
// 
// by WoodReal12
// 
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
// #include <atcoder/all>
#define int long long 
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define endl "\n"
#define pc putchar
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
using namespace std;
// using namespace atcoder;
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
template <typename T> inline bool read(T &x){
    x=0;int f=1;char c=gc();
    for(;c!=EOF&&!isdigit(c);c=gc())if(c=='-')f=-1;
    if(c==EOF)return 0;
    for(;c!=EOF&&c>='0'&&c<='9';c=gc())x=(x<<1)+(x<<3)+(c^48);
    x*=f;return 1;
}
template <typename T,typename ...Targs>
inline bool read(T &x,Targs& ...args){return read(x)&&read(args...);}
template <typename T> void print(T x){
    if(x<0)pc('-'),x=-x;
    if(x>=10)print(x/10);
    pc(x%10+'0');
}
int n,m;
int k,t;
int dis[5005][5005];
int d[50005];
signed main(){
	memset(dis,0x3f,sizeof(dis));
	// cout<<(int)dis[1]<<endl;
	read(n,m);
	for(int i=1,u,v,w;i<=m;i++){
		read(u,v,w);
		dis[u][v]=w;
		dis[v][u]=w;
	}
	read(k,t);
	for(int i=1;i<=k;i++){
		read(d[i]);
	}
	for(int i=1;i<=k;i++){
		for(int j=1;j<=k;j++){
			dis[d[i]][d[j]]=min(dis[d[i]][d[j]],t);
			dis[d[j]][d[i]]=min(dis[d[j]][d[i]],t);
		}
	}
	
	for(int i=1;i<=n;i++)
		dis[i][i]=0;
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
			}
		}
	}
	int q;
	read(q);
	int cnt=k;
	while(q--){
		int op;
		read(op);
		if(op==1){
			int u,v,w;
			read(u,v,w);
			dis[u][v]=min(dis[u][v],w);
			dis[v][u]=min(dis[v][u],w);
			for(int i=1;i<=n;i++)
				dis[u][i]=min(dis[u][v]+dis[v][i],dis[u][i]);
			for(int i=1;i<=n;i++)
				dis[i][u]=dis[u][i];
			for(int i=1;i<=n;i++)
				dis[v][i]=min(dis[u][v]+dis[u][i],dis[v][i]);
			for(int i=1;i<=n;i++)
				dis[i][v]=dis[v][i];
		}
		if(op==2){
			int x;
			read(x);
			for(int i=1;i<=cnt;i++)
				dis[x][d[i]]=min(dis[x][d[i]],t),dis[d[i]][x]=min(dis[d[i]][x],t);
			for(int i=1;i<=n;i++){
				for(int j=1;j<=cnt;j++){
					dis[x][i]=min(dis[x][i],dis[x][d[j]]+dis[d[j]][i]);
					dis[i][x]=dis[x][i];
					dis[d[j]][i]=min(dis[d[j]][i],dis[d[j]][x]+dis[x][i]);
					dis[i][d[j]]=dis[d[j]][i];
				}
			}
			d[++cnt]=x;
		}
		if(op==3){
			int ans=0;
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++){
					if(dis[i][j]<0x3f3f3f3f3f3f3f3f)
						ans+=dis[i][j];
				}
			cout<<ans<<endl;
		}
	}
	return 0;
}

回复

10 条回复,欢迎继续交流。

正在加载回复...