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

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+7;
struct edge{
	int to,fr;
}t[N];
vector<int>G[N];
vector<int>f[N];
int dfn[N],low[N],n,m,inst[N],col[N],sccnt,tot,vis[N],a[N],dis[N],newa[N],nazi[N],newna[N],s,p,inque[N];
stack<int>st;
void tarjan(int v){
	dfn[v]=low[v]=++tot;
	st.push(v);
	inst[v]=1;
	for(auto u:G[v]){
		if(!dfn[u]){
			tarjan(u);
			low[v]=min(low[u],low[v]);
		} 
		else if(inst[u]){
			low[v]=min(low[v],dfn[u]);
		}
	}
	if(dfn[v]==low[v]){
		++sccnt;
		int u;
		do{
			u=st.top();
			inst[u]=0;
			st.pop();
			col[u]=sccnt;
			newa[sccnt]+=a[u];			
		}while(v!=u); 
	}
}
void spfa(int st) {
    memset(dis,-0x3f,sizeof(dis));
    memset(inque,0,sizeof(inque));
    queue<int>q;
    dis[st]=newa[st];
    inque[st]=1;
    q.push(st);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        inque[u]=0;
        for(auto v:f[u]) {
            int w=newa[v];
            if(dis[u]+w>dis[v]){
                dis[v]=dis[u]+w;
                if(!inque[v]){
                    inque[v]=1;
                    q.push(v);
                }
            }
        }
    }
}
int main(){
	freopen("atm.in","r",stdin);
	freopen("atm.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		G[u].push_back(v);
		t[i]={v,u};
	}
	for(int i=1;i<=n;i++){
		cin>>a[i];
	} 	
	cin>>s>>p;
	for(int i=1;i<=p;i++){
		cin>>nazi[i];
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			tarjan(i);
		}
	} 	
	for(int i=1;i<=m;i++){
		int u=col[t[i].fr],v=col[t[i].to];
		if(u!=v){
			f[u].push_back(v);
		}
	}
	for(int i=1;i<=p;i++){
		newna[col[nazi[i]]]=1;
	}
	spfa(col[s]); 
	int ans=-0x3f3f3f3f;
	for(int i=1;i<=sccnt;i++) {
	    if(newna[i]){
	        ans=max(ans,dis[i]);
	    }
	}
	cout<<ans;

	return 0;
}