比赛 2025暑期集训第8场 评测结果 AAAAAAAAAA
题目名称 抢掠计划 最终得分 100
用户昵称 李金泽 运行时间 0.039 s
代码语言 C++ 内存使用 3.94 MiB
提交时间 2025-08-13 11:38:51
显示代码纯文本
#include<cstdio>
#include<queue>
#define N 500005
#define M 500005
#define ll long long
using namespace std;
ll n,m,h[N],cnt,he[N],tot,scc[N],cou,now[N],low[N],sum[N],dfn,st[N],t,d[N],s,k,p[N],x,y,ans;bool b[N];
struct edg{ll v,n;}ed[M<<1];
struct edge{ll v,n;}e[M<<1];
void ad1(ll u,ll v){ed[++tot]={v,he[u]};he[u]=tot;}
void ad2(ll u,ll v){e[++cnt]={v,h[u]};h[u]=cnt;}
queue<ll>q;
ll max(ll x,ll y){return x>y?x:y;}
ll min(ll x,ll y){return x<y?x:y;}
void tarjan(ll u)
{
	st[++t]=u;
	now[u]=low[u]=++dfn;
	for(ll i=he[u];i;i=ed[i].n)
	{
		ll v=ed[i].v;
		if(!now[v])
			tarjan(v),low[u]=min(low[u],low[v]);
		else if(!scc[v])low[u]=min(low[u],now[v]);
	}
	if(now[u]==low[u])
	{
		cou++;
		do{
			scc[st[t]]=cou;
		}while(st[t--]^u);
	}
}
void spfa(){
	q.push(s);d[s]=sum[s];
	while(q.size())
	{
		ll u=q.front();q.pop();
		b[u]=0;
		for(ll i=h[u];i;i=e[i].n)
		{
			ll v=e[i].v;
			if(d[u]+sum[v]>d[v])
			{
				d[v]=d[u]+sum[v];
				if(!b[v])b[v]=1,q.push(v);
			}
		}
	}
}
ll read(){
	ll sum=0;bool f=0;char c=getchar();
	for(;c<48||c>57;c=getchar())if(c==45)f=1;
	for(;c>=48&&c<=57;c=getchar())sum=sum*10+(c&15);
	return f?-sum:sum; 
}
int main(){
	freopen("atm.in","r",stdin);freopen("atm.out","w",stdout);
	n=read(),m=read();
	while(m--)x=read(),y=read(),ad1(x,y);
	for(ll i=1;i<=n;i++)if(!now[i])tarjan(i);
	for(ll i=1;i<=n;i++)
		for(ll j=he[i];j;j=ed[j].n)
			if(scc[i]^scc[ed[j].v])
				ad2(scc[i],scc[ed[j].v]);
	for(ll i=1;i<=n;i++)sum[scc[i]]+=read();
	s=scc[read()],k=read();
	spfa();
	while(k--)ans=max(ans,d[scc[read()]]);
	printf("%lld",ans);
	return 0;
}