萌新求助,87分
查看原帖
萌新求助,87分
138650
MoXiaodu楼主2020/7/31 08:08
#include<bits/stdc++.h>
using namespace std;

long long to[500005],head[500005],num[500005],cnt;
long long to2[500005],head2[500005],num2[500005],cnt2,vs[500005];
long long n,m,ss,ts,p,dfn[500005],low[500005],qlt,jl,ans,v[500005],belong[500005],sum[500005];
long long vis[500005],dis[500005];
bool pd[500005],pd2[500005];
stack<long long> s;
long long read(){
	long long f=1,out=0;char c=getchar();
	while(c>'9'||c<'0'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c<='9'&&c>='0'){
		out*=10;out+=c-'0';
		c=getchar();
	}
	return f*out;
}
void add(long long x,long long y){
	cnt++;
	head[cnt]=num[x];
	num[x]=cnt;
	to[cnt]=y;
	return;
}
void add2(long long x,long long y,long long z){
	cnt2++;
	head2[cnt2]=num2[x];
	num2[x]=cnt2;
	to2[cnt2]=y;
	vs[cnt2]=-z;
	return;
}
void tarjan(long long x){
	jl++;
	dfn[x]=low[x]=jl;
	vis[x]=1;
	s.push(x);
	for(long long i=num[x];i;i=head[i]){
		long long tto=to[i];
		if(!dfn[tto]){
			tarjan(tto);
			low[x]=min(low[x],low[tto]);
		}
		else if(vis[tto])low[x]=min(low[x],dfn[tto]);
	}
	if(dfn[x]==low[x]){
		qlt++;
		long long jly=0;
		while(s.top()!=x){
			long long nown=s.top();
			s.pop();
			jly+=v[nown];
			belong[nown]=qlt;
			vis[nown]=0;
			if(ss==nown)ts=qlt;
		}
		if(ss==x)ts=qlt;
		s.pop();
		jly+=v[x];
		sum[qlt]=jly;
		belong[x]=qlt;
		vis[x]=0;
	}
	return;
}
void SPFA(long long sp){
	queue<long long>q;
	memset(dis,0x3f,sizeof(dis));
	dis[sp]=0;q.push(sp);vis[sp]=1;
	while(q.size()){
		long long nown=q.front();
		q.pop();
		vis[nown]=1;
		for(long long i=num2[nown];i;i=head2[i]){
			long long t=to2[i];
			if(dis[t]>dis[nown]+vs[i]){
				dis[t]=dis[nown]+vs[i];
				if(!vis[t])
				{
					vis[t]=1;
					q.push(t);
				}
			}
		}
	}
}
int main(){
	//plan

	n=read(),m=read();
	for(long long i=1;i<=m;i++){
		long long a=read(),b=read();
		add(a,b);
	}
	for(long long i=1;i<=n;i++)
		v[i]=read();
	ss=read(),p=read();
	for(long long i=1;i<=p;i++){
		long long a=read();
		pd[a]=1;
	}
	for(long long i=1;i<=n;i++){
		if(!dfn[i])
		tarjan(i);
	}
	for(long long i=1;i<=n;i++){
		if(pd[i])pd2[belong[i]]=1;
		for(long long j=num[i];j;j=head[j]){
			if(belong[i]!=belong[to[j]]){
				long long t=to[j];
				add2(belong[i],belong[t],sum[belong[t]]);
			}
		}
	}
	SPFA(ts);
	long long ans=sum[ts];
	for(long long i=1;i<=qlt;i++){
		if(pd2[i]&&sum[ts]-dis[i]>ans)
		ans=sum[ts]-dis[i];
	}
	cout<<ans<<endl;
	return 0;
} 
2020/7/31 08:08
加载中...