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

#include<bits/stdc++.h>
using namespace std;
void read(int &x){bool neg=false;x=0;char ch=0;while(ch<'0'||ch>'9'){if(ch=='-')neg=true;ch=getchar();}if(neg){while(ch>='0'&&ch<='9'){x=x*10+('0'-ch);ch=getchar();}}else{while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}}return;}

int n,m,opop1,opop2,p,s,opop3;
vector<int>g[555555],newg[555555];
int stamp,col,top;
int stk[555555],dfn[555555],color[555555],low[555555],vis[555555],siz[555555],de[555555],newde[555555];
bool bar[555555],newbar[555555];
int ans;

void tarjan(int u){
    low[u]=dfn[u]=++stamp;
    stk[++top]=u;
    vis[u]=1;
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(vis[v]) low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        col++;
        int v;
        do{
            v=stk[top--];
            color[v]=col;
            vis[v]=0;
            siz[col]++;
            newde[col]+=de[v];
            if(bar[v])newbar[col]=1;
            if(s==v)s=col;
        }while(v!=u);
    }
}

void new_build(){
    for(int u=1;u<=n;u++)
        for(int i=0;i<g[u].size();i++){
            int v=g[u][i];
            if(color[u]!=color[v])newg[color[u]].push_back(color[v]);
        }
}

int d[555555];
bool inq[555555];

void SPFA(int x){
    queue<int> q;
	for(int i=1;i<=543210;i++)d[i]=-(4000*500000)-555;
    d[x]=newde[x];
    q.push(x);
    inq[x]=true;
    while(!q.empty()){
        int u=q.front();q.pop();
        inq[u]=0;
        for(int i=0;i<newg[u].size();i++){
            int v=newg[u][i];
            if(d[v]<d[u]+newde[v]){
                d[v]=d[u]+newde[v];
                if(!inq[v]){
                    q.push(v);
                    inq[v]=true;
                }
            }
        }
    }
    for(int i=1;i<=col;i++){
        if(newbar[i]&&d[i]>ans){
            ans=d[i];
        }
    }
}

signed main(){
    freopen("atm.in","r",stdin);freopen("atm.out","w",stdout);
    read(n);read(m);
    for(int i=1;i<=m;i++){
        read(opop1);read(opop2);
        g[opop1].push_back(opop2);
    }
    for(int i=1;i<=n;i++){
        read(de[i]);
    }
    read(s);read(p);
    for(int i=1;i<=p;i++){
        read(opop3);
        bar[opop3]=1;
    }

	tarjan(s);
    new_build();

    for(int i=1;i<=col;i++){
        if(newg[i].size()>0){
            sort(newg[i].begin(),newg[i].end());
            auto last=unique(newg[i].begin(),newg[i].end());
            newg[i].erase(last,newg[i].end());
        }
    }

    SPFA(s);
    printf("%d",ans);
    return 0;
}