比赛 2025暑期集训第8场 评测结果 AAAAAAAAAA
题目名称 抢掠计划 最终得分 100
用户昵称 Hollow07 运行时间 0.162 s
代码语言 C++ 内存使用 19.56 MiB
提交时间 2025-08-13 09:11:28
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define ll long long

struct edge{
    ll to,val,next;
} e[510000];

ll m,n,p,s,cnt,g[510000],u[510000],v[510000],w[510000],hd[510000];
ll bar[510000],dis[510000],dfn[510000],low[510000],stk[510000],sum[510000];
bool vis[510000];
queue <ll> q;
ll ans,top,tot,total;

void add(ll u,ll v){
	cnt++;
	e[cnt].to=v;
	e[cnt].next=hd[u];
	hd[u]=cnt;
}

void build(ll u,ll v,ll w){
	cnt++;
	e[cnt].to=v;
	e[cnt].val=w;
	e[cnt].next=hd[u];
	hd[u]=cnt;
}

void clear(){
	cnt=0;
	memset(e,0,sizeof(e));
	memset(hd,0,sizeof(hd));
}

void Tarjan(ll x){
	dfn[x]=low[x]=++total;
	stk[++top]=x;vis[x]=1;
	for(int i=hd[x];i;i=e[i].next){
		ll t=e[i].to;
		if(!dfn[t]){
			Tarjan(t);
			low[x]=min(low[x],low[t]);
		}else if(vis[t])
			low[x]=min(low[x],dfn[t]);
	}
	if(dfn[x]==low[x]){
		tot++;
		do{
			ll tp=stk[top];
			sum[tot]+=w[tp];
			vis[tp]=0;
			g[tp]=tot;
		}while(stk[top--]!=x);
	}
}

void spfa(ll s){
	for(int i=1;i<=tot;i++) dis[i]=0;
	ll gs=g[s];
	q.push(gs);
	vis[gs]=1;
	dis[gs]=sum[gs];
	while(!q.empty()){
		ll h=q.front();q.pop();
		vis[h]=0;
		for(int i=hd[h];i;i=e[i].next){
			ll t=e[i].to;
			if(dis[t]<dis[h]+e[i].val){
				dis[t]=dis[h]+e[i].val;
				if(!vis[t]){
					q.push(t);
					vis[t]=1;
				}
			}
		}
	}
}
int main(){
//	freopen("in.in","r",stdin);
	freopen("atm.in","r",stdin);
	freopen("atm.out","w",stdout);
	scanf("%lld %lld",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%lld %lld",&u[i],&v[i]);
        add(u[i],v[i]);
    }
    for(int i=1;i<=n;i++) scanf("%lld",&w[i]);
    scanf("%lld %lld",&s,&p);
    for(int i=1;i<=p;i++) scanf("%lld",&bar[i]);
    for(int i=1;i<=n;i++)
    	if(!dfn[i]) Tarjan(i);
    clear();
    for(int i=1;i<=m;i++)
    	if(g[u[i]]!=g[v[i]])
    		build(g[u[i]],g[v[i]],sum[g[v[i]]]);
    spfa(s);
    for(int i=1;i<=p;i++)
    	ans=max(ans,dis[g[bar[i]]]);
    printf("%lld",ans);
    return 0;
}