思路:
先把所有可以列车通的缩成一个点,然后用新图建立kruskalkruskalkruskal重构树。 这样就可以倒着贪心模拟了。 代码:#include#define ri register int#define int long long#define fi first#define se secondusing namespace std;const int rlen=1<<18|1;inline char gc(){ static char buf[rlen],*ib,*ob; (ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin)); return ib==ob?-1:*ib++;}inline int read(){ int ans=0; bool f=1; char ch=gc(); while(!isdigit(ch))f^=ch=='-',ch=gc(); while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc(); return f?ans:-ans;}const int N=2e5+5,M=2e5+5;int rt,anc[N],id[N],n,m,q,qry[N],a[N],val[N],pass[N];inline int find(const int&x){ return x^anc[x]?anc[x]=find(anc[x]):x;}struct Node{ int u,v,w;friend inline bool operator<(const Node&a,const Node&b){ return a.w>b.w;}}g[M];vector e[N];int dep[N],st[N][20];void dfs(int p){ for(ri i=1;i<20;++i)st[p][i]=st[st[p][i-1]][i-1]; for(ri i=0,v;i >i)&1)x=st[x][i]; if(x==y)return val[x]; for(ri i=19;~i;--i)if(st[x][i]^st[y][i])x=st[x][i],y=st[y][i]; return val[st[x][0]];}inline void init(){ for(ri i=1;i<=n;++i)id[i]=i,anc[i]=i; for(ri x,pre=0;q;--q){ x=read(); if(!pre)pre=x; id[x]=pre; } sort(g+1,g+m+1); rt=n; for(ri i=1,fx,fy;i<=m;++i){ fx=find(id[g[i].u]),fy=find(id[g[i].v]); if(fx^fy){ val[++rt]=g[i].w,e[rt].push_back(fx),e[rt].push_back(fy),anc[fx]=anc[fy]=anc[rt]=rt;} } dfs(rt);}signed main(){ n=read(),m=read(),q=read(); for(ri i=1;i<=n;++i)qry[i]=read(); for(ri i=1;i<=n;++i)a[i]=read(); for(ri i=1;i<=m;++i)g[i].u=read(),g[i].v=read(),g[i].w=read(); init(); for(ri tmp,pre=0,i=n,p;i;--i){ p=qry[i]; if(a[p]<0)pre-=a[p]; else pass[p]=min(a[p],pre),pre-=pass[p]; if(i^1)tmp=query(id[p],id[qry[i-1]]); if(tmp!=0x3f3f3f3f)pre=min(pre,tmp); } for(ri i=1,p,tmp,pre=0;i<=n;++i){ p=qry[i]; if(a[p]<0)cout<<(tmp=min(-a[p],pre))<<'\n',pre-=tmp; else pre+=pass[p]; } return 0;}