记录编号	605002	评测结果	AAAAAAAAAA
题目名称	2449.[APIO2009] 抢掠计划	最终得分	100
用户昵称	彭欣越	是否通过	通过
代码语言	C++	运行时间	0.078 s
提交时间	2025-08-13 12:24:17	内存使用	7.65 MiB

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=500010;
int n,m,s,p,a[N],mk[N],dis[N],ans;
int tot,tot1,head[N],head1[N];
int dfn[N],low[N],vis[N],st[N],col[N],val[N],cnt,scc,idx,jsq;
struct node {
	int u,v,w,nxt;
}e[N],e1[N];
void add (int u,int v) {
	e[++tot].v=v;
	e[tot].u=u;
	//e[tot].w=w;
	e[tot].nxt=head[u];
	head[u]=tot;
}
void tarjan (int now) {
	dfn[now]=++cnt;
	low[now]=cnt;
	vis[now]=1;
	st[++idx]=now;
	for (int i=head[now];i;i=e[i].nxt) {
		int v=e[i].v;
		if (!dfn[v]) {
			tarjan(v);
			low[now]=min(low[now],low[v]);
		}else if (vis[v]) {
			low[now]=min(low[now],low[v]);
		}
	}
	int t=0;
	if (low[now]==dfn[now]) {
		jsq++;
		while (t=st[idx--]) {
			col[t]=jsq;
			val[jsq]+=a[t];
			vis[t]=0;
			if (now==t) break;
		}
	}
}
queue<int>q;
void spfa (int s) {
	//cout << 1 <<endl;
    memset(dis,0,sizeof(dis));
	memset(vis,0,sizeof(vis));
	vis[col[s]]=1;
	dis[col[s]]=val[col[s]];
	q.push(col[s]);
	while (!q.empty()) {
		//cout << 1 <<endl;
		int u=q.front();
		q.pop();
		vis[u]=0;
		for (int i=head1[u];i;i=e1[i].nxt) {
			int v=e1[i].v,w=e1[i].w;
			if (dis[v]<dis[u]+w) {
				dis[v]=dis[u]+w;
				//cout << dis[v] <<' '<< v <<endl;
				if (!vis[v]) {
					q.push(v);
					vis[v]=1;
				}
			}
		}
	} 
}
int main () {
	freopen("atm.in","r",stdin);
	freopen("atm.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin >> n >> m;
	for (int i=1;i<=m;i++) {
		int a,b;
		cin >> a >> b;
		add(a,b);
	}
	for (int i=1;i<=n;i++) cin >> a[i];
	cin >> s >> p;
	for (int i=1;i<=p;i++) cin >> mk[i];
	for (int i=1;i<=n;i++) if (!dfn[i]) tarjan(i);
	for (int i=1;i<=m;i++) {
		int x=col[e[i].u],y=col[e[i].v];
		if (x!=y) {
			e1[++tot1].u=x;
			e1[tot1].v=y;
			e1[tot1].w=val[y];
			//cout << val[y] <<endl;
			e1[tot1].nxt=head1[x];
			head1[x]=tot1;
		}
	}
	//cout << val[col[s]] <<endl;
	spfa(s);
	for (int i=1;i<=p;i++) {
		ans=max(ans,dis[col[mk[i]]]);
	}
	cout << ans <<endl;
	return 0;
}