80pts求助
查看原帖
80pts求助
596945
nahidaa楼主2024/10/10 14:35
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,k,cnt,headd[800005],head[800005],x,y,z,a[800005],b[800005],fa[800005],zuid,tn,ge,dp[800005];
ll qian;
struct beiz{
	ll dot,len;
}bei[800005][25];
priority_queue<pair<ll,pair<ll,ll> > >pq;
struct road{
	ll v,nextt,weight;
	bool o;
}d[800005];
struct treeroad{
	int v,nextt,length;
}rd[800005];
void add(int x,int y,int z){
	d[++cnt].v=y;
	d[cnt].nextt=headd[x];
	d[cnt].weight=z;
	headd[x]=cnt;
}
void tradd(int x,int y,int z){
	rd[++tn].v=y;
	rd[tn].nextt=head[x];
	rd[tn].length=z;
	head[x]=tn;
}
void putin(int u,int faaa,ll chang){
	tradd(faaa,u,chang);
	tradd(u,faaa,chang);
	for(int i=headd[u];i;i=d[i].nextt){
		if(d[i].o)continue;
		int v=d[i].v,ww=d[i].weight;
		d[i].o=1;
		pq.push(make_pair(ww,make_pair(u,v)));
	}
}
int getfa(int s){
	if(fa[s]!=s)return fa[s]=getfa(fa[s]);
	return s;
}
void build(){
	while(ge<n){
		int len=pq.top().first,v=pq.top().second.second,ffa=pq.top().second.first;
		pq.pop();
		if(getfa(v)!=0){
			putin(v,ffa,len);
			fa[v]=0;
			ge++;
		}
	}
}
void bianli(int u,int faf,ll len,ll dep){
	dp[u]=dep;
	if(u!=0)bei[u][0].len=len;
	else bei[u][0].len=-1;
	if(faf!=-1)bei[u][0].dot=faf;
	for(int i=head[u];i;i=rd[i].nextt){
		int v=rd[i].v,len=rd[i].length;
		if(v!=faf)
		bianli(v,u,len,dep+1);
	}
}
ll lu(int x,int y){
	if(dp[x]>dp[y]){
		swap(x,y);
	}
	ll big=2e9;
	//dp[x]<=dp[y]
	for(int i=20;i>=0;--i){
		if(dp[bei[y][i].dot]>=dp[x]){
			big=min(big,bei[y][i].len);
			y=bei[y][i].dot;
		}
	}
	//dp[x]=dp[y]
	for(int i=20;i>=0;--i){
		if(bei[x][i].dot!=bei[y][i].dot){
			big=min(big,min(bei[x][i].len,bei[y][i].len));
			x=bei[x][i].dot,y=bei[y][i].dot;
		}
	}
	if(x!=y){
		big=min(big,min(bei[x][0].len,bei[y][0].len));
		x=bei[x][0].dot,y=bei[y][0].dot;
	}
	return big;
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m>>k;
	for(int i=1;i<=n;++i){
		fa[i]=i;
		cin>>a[i];
	}
	for(int i=1;i<=n;++i){
		cin>>b[i];
	}
	for(int i=1;i<=m;++i){
		cin>>x>>y>>z;
		add(x,y,z);
		add(y,x,z);
	}
	if(k!=0)for(int i=1;i<=k;++i){
		cin>>x;
		fa[x]=0;
		putin(x,0,2e9);
	}
	else{
		fa[1]=0;
		putin(1,0,2e9);
		k=1;
	}
	ge=k;
	build();
	bianli(0,-1,0,1);
	for(int i=1;i<=20;++i){
		for(int j=0;j<=n;++j){
			if(bei[j][i-1].len<bei[bei[j][i-1].dot][i-1].len){
				bei[j][i].len=bei[j][i-1].len;
			}else{
				bei[j][i].len=bei[bei[j][i-1].dot][i-1].len;
			}
			bei[j][i].dot=bei[bei[j][i-1].dot][i-1].dot;
		}
	}
	int ii=1;
	for(;ii<=n;++ii){
		if(b[a[ii]]>0){
			qian=b[a[ii]];
			++ii;
			break;
		}
		else cout<<"0\n";
	}
	for(int i=ii;i<=n;++i){
		if(b[a[i]]<=0){
			zuid=min(qian,lu(a[i-1],a[i]));
			qian=zuid;
			cout<<min(-b[a[i]],zuid)<<"\n";
			qian-=min(-b[a[i]],zuid);
		}else{
			zuid=min(qian,lu(a[i-1],a[i]));
			qian=zuid+b[a[i]];
		}
	}
	return 0;
}
2024/10/10 14:35
加载中...