记录编号	460551	评测结果	AAAAAAAAAA
题目名称	[APIO2009] 抢掠计划	最终得分	100
用户昵称	FFF团	是否通过	通过
代码语言	C++	运行时间	0.128 s
提交时间	2017-10-17 18:06:29	内存使用	31.78 MiB

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstring>
using namespace std;
vector<int>g[500005];
vector<int>r[500005];
vector<int>newg[500005];
vector<int>scc[500005];
stack<int>sta;
bool vis[500005],bar[500005];
int w[500005],belong[500005],neww[500005],d[500005]; 
void dfs1(int x){
    int l=g[x].size();
    for(register int i=0;i<l;i++)
    if(!vis[g[x][i]])
    vis[g[x][i]]=1,dfs1(g[x][i]);            
    sta.push(x);
}
void dfs2(int x,int cnt){
    int l=r[x].size();
    for(register int i=0;i<l;i++)
    if(!belong[r[x][i]])
    belong[r[x][i]]=cnt,scc[cnt].push_back(r[x][i]),dfs2(r[x][i],cnt);
}
void SPFA(int s){
    queue<int>q;bool inq[500005];
    q.push(s);inq[s]=1;d[s]=neww[s];
    while(!q.empty()){
        int u=q.front();inq[u]=0;q.pop();
        int l=newg[u].size();
        for(int i=0;i<l;i++){
            int v=newg[u][i];
            if(d[v]<d[u]+neww[v]){
                d[v]=d[u]+neww[v];
                if(!inq[v]){
                    q.push(v);
                    inq[v]=1;
                }
            }
        }
    }
}
int n,m,cnt,ans,s,p;
int main(){
	freopen("atm.in","r",stdin);
	freopen("atm.out","w",stdout);
    scanf("%d%d",&n,&m);
    int x,y;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
        r[y].push_back(x);
    }
    for(int i=1;i<=n;i++)scanf("%d",&w[i]);
    scanf("%d%d",&s,&p);
    for(int i=1;i<=p;i++){
        scanf("%d",&x);
        bar[x]=1;
    }
    for(int i=1;i<=n;i++)
    if(!vis[i])dfs1(i);
    while(!sta.empty()){
        int u=sta.top();sta.pop();
        if(!belong[u])scc[++cnt].push_back(u),belong[u]=cnt,dfs2(u,cnt);
    }
    for(int i=1;i<=cnt;i++){
        int l1=scc[i].size();
        fill(vis+1,vis+cnt+1,0);
        for(int j=0;j<l1;j++){
            int u=scc[i][j],l2=g[u].size();
            for(int k=0;k<l2;k++){
                int v=g[u][k];
                if(belong[u]!=belong[v]&&!vis[belong[v]])newg[i].push_back(belong[v]),vis[belong[v]]=1;
            }
            neww[i]+=w[u];
        }
    }
    SPFA(belong[s]);
    for(int i=1;i<=n;i++)
    if(bar[i])ans=max(ans,d[belong[i]]);
    printf("%d",ans);
    return 0;
}