记录编号	605029	评测结果	AAAAAAAAAA
题目名称	2449.[APIO2009] 抢掠计划	最终得分	100
用户昵称	汐汐很希希	是否通过	通过
代码语言	C++	运行时间	0.121 s
提交时间	2025-08-13 14:40:29	内存使用	11.42 MiB

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=500010;
int n,m,s,p,v[N],u[N],w[N],bar[N],head[N],d[N],cnt,ans;
int dfn[N],stk[N],low[N],sum[N],newg[N],tot,stamp,top;
bool vis[N];
queue<int> q;
struct Graph
{
    int nxt,v,to;
}g[N];
void clear()
{
    cnt=0;
    memset(g,0,sizeof(g));
    memset(head,0,sizeof(head));
}
void add(int u,int v)
{
    cnt++;
    g[cnt].to=v;
    g[cnt].nxt=head[u];
    head[u]=cnt;
}
void build(int u,int v,int w)
{
    cnt++;
    g[cnt].to=v;
    g[cnt].v=w;
    g[cnt].nxt=head[u];
    head[u]=cnt;
}
void tarjan(int x)
{
    dfn[x]=low[x]=++stamp;
    stk[++top]=x;vis[x]=true;
    for(int i=head[x];i;i=g[i].nxt)
    {
        int t=g[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{
            int tp=stk[top];
            sum[tot]+=w[tp];
            vis[tp]=false;
            newg[tp]=tot;
        }while(stk[top--]!=x);
    }
    return; 
}
void spfa(int s)
{
    for(int i=1;i<=tot;i++) d[i]=0;
    int gs=newg[s];
    q.push(gs);
    vis[gs]=true;
    d[gs]=sum[gs];
    while(!q.empty())
    {
        int h=q.front();q.pop();
        vis[h]=false;
        for(int i=head[h];i;i=g[i].nxt)
        {
            int t=g[i].to;
            if(d[t]<d[h]+g[i].v)
            {
                d[t]=d[h]+g[i].v;
                if(!vis[t])
                {
				    q.push(t);
	    	        vis[t]=true;
                }
            }
        }
    }
    return;
}
int main()
{
    freopen("atm.in","r",stdin);
    freopen("atm.out","w",stdout);
    
    cin>>n>>m;
    clear();
    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>>w[i];
    cin>>s>>p;
    for(int i=1;i<=p;i++) cin>>bar[i];
    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
    clear();
    for(int i=1;i<=m;i++) if(newg[u[i]]!=newg[v[i]]) build(newg[u[i]],newg[v[i]],sum[newg[v[i]]]);
    spfa(s);
    for(int i=1;i<=p;i++) ans=max(ans,d[newg[bar[i]]]);
    cout<<ans<<endl;
    return 0;
}