社区讨论
求调昨晚ABC_e,玄关
学术版参与者 4已保存回复 10
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 10 条
- 当前快照
- 1 份
- 快照标识符
- @mdkwdgnp
- 此快照首次捕获于
- 2025/07/27 07:44 7 个月前
- 此快照最后确认于
- 2025/11/04 03:40 4 个月前
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 条回复,欢迎继续交流。
正在加载回复...