记录编号	605012	评测结果	AAAAAAAAAA
题目名称	2449.[APIO2009] 抢掠计划	最终得分	100
用户昵称	Ruyi	是否通过	通过
代码语言	C++	运行时间	0.104 s
提交时间	2025-08-13 13:46:09	内存使用	9.49 MiB

#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,ans,tot,h[500001],my[500001],ss,g[500001],dis[500001],dfn[500001],low[500001],sum[500001],cnt,vis[500001],colnum,u[500001],v[500001];
struct edge{
    int to,nxt;
}e[500001];
stack<int> s;
queue<int> q;
void add(int x,int y){
    e[++tot].to=y;
    e[tot].nxt=h[x];
    h[x]=tot;
}
void tarjan(int x){
    dfn[x]=low[x]=++cnt;
    s.push(x);
    vis[x]=1;
    for(int i=h[x];i;i=e[i].nxt){
        int v=e[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[x]=min(low[x],low[v]);
        }else if(vis[v]) low[x]=min(low[x],dfn[v]);
    }
    if(low[x]==dfn[x]){
        colnum++;
        int y;
        do{
            y=s.top();
            s.pop();
            vis[y]=0;
            sum[colnum]+=my[y];
            g[y]=colnum;
        }while(x!=y);
    }
    return ;
}
void f(int x){
    for(int i=1;i<=colnum;i++) dis[i]=0;
 	int gs=g[x];
    q.push(gs);
 	vis[gs]=true;
 	dis[gs]=sum[gs];
 	while(!q.empty()){
 		int fz=q.front();q.pop();
 		vis[fz]=false;
 		for(int i=h[fz];i;i=e[i].nxt){
 			int t=e[i].to;
 			if(dis[t]<dis[fz]+my[i]){
 				dis[t]=dis[fz]+my[i];
 				if(!vis[t]){
 					q.push(t);
 					vis[t]=true;
 				}
 			}
 		}
 	}
 	return ;
}
void build(int u,int v,int w){
 	cnt++;
 	e[cnt].to=v;
 	my[cnt]=w;
 	e[cnt].nxt=h[u];
 	h[u]=cnt;
}
int main(){
    freopen("atm.in","r",stdin);
    freopen("atm.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>u[i]>>v[i];
        add(u[i],v[i]);
    }
    for(int i=1;i<=n;i++) cin>>my[i];
    for(int i=1;i<=n;i++)
    if(!dfn[i]) tarjan(i);
    memset(h,0,sizeof(h));
    memset(e,0,sizeof(e));
    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]]]);
    cin>>ss>>a;
    f(ss);
    for(int i=1;i<=a;i++){
        cin>>b;
        ans=max(ans,dis[g[b]]);
    }
    cout<<ans<<endl;
    return 0;
}