比赛 2025暑期集训第8场 评测结果 AAAAAAAAAA
题目名称 抢掠计划 最终得分 100
用户昵称 徐诗畅 运行时间 0.055 s
代码语言 C++ 内存使用 5.88 MiB
提交时间 2025-08-13 08:10:11
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5; 
int n,m,s,p,head[N],cnt,SCC,cnt1;
struct edge{int v,w,next;}e[1000005],e1[5000005]; 
int head1[N],val[N],vis[N],dis[N];
int a[N],end_[N],dfn[N],low[N],num,inst[N],scc[N];
stack<int> st;
int in[N];
queue<int> q;
void addedge1(int u,int v){e[++cnt].v=v; e[cnt].next=head[u]; head[u]=cnt;}
void addedge2(int u,int v,int w){e1[++cnt1].v=v; e1[cnt1].w=w; e1[cnt1].next=head1[u]; head1[u]=cnt1;}
void dfs(int k){
	dfn[k]=low[k]=++num;
	st.push(k); inst[k]=1;
	for(int i =head[k];i;i=e[i].next){
		int v=e[i].v;
		if(!dfn[v]){
			dfs(v);
			low[k]=min(low[k],low[v]);
		}
		else if(inst[v]){
			low[k]=min(low[k],dfn[v]);
		}
	}
	if(dfn[k]==low[k]){
		int t; SCC++;
		do{
			t=st.top(); st.pop();
			inst[t]=0; scc[t]=SCC;
		}while(t!=k);
	}
}
int main(){
	freopen("atm.in","r",stdin);
	freopen("atm.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i = 1;i<=m;i++){
		int u,v; scanf("%d%d",&u,&v);
		addedge1(u,v);
	}
	for(int i = 1;i<=n;i++) scanf("%d",&a[i]);
	scanf("%d%d",&s,&p);
	for(int i = 1;i<=p;i++) scanf("%d",&end_[i]);
	for(int i = 1;i<=n;i++)
	if(!dfn[i])
	dfs(i);
	for(int i = 1;i<=n;i++) val[scc[i]]+=a[i];
	//for(int i = 1;i<=SCC;i++) cout<<val[i]<<endl;
	for(int u = 1;u<=n;u++){
		for(int i = head[u];i;i=e[i].next){
			int v=e[i].v;
			if(scc[u]!=scc[v]){
				addedge2(scc[u],scc[v],val[scc[v]]);
			}
		} 
	}
	q.push(scc[s]);
	memset(dis,0,sizeof(dis));
	dis[scc[s]]=val[scc[s]]; vis[scc[s]]=1;
	while(!q.empty()){
		int u =q.front(); q.pop();
		vis[u]=0;
		for(int i =head1[u];i;i=e1[i].next){
			int v=e1[i].v;
			if(dis[v]<dis[u]+e1[i].w){
				dis[v]=dis[u]+e1[i].w;
				if(vis[v]==0){
					q.push(v);
					vis[v]=1;
				}
			}
		}
	}
	int ans=0;
	for(int i = 1;i<=p;i++)
	ans=max(ans,dis[scc[end_[i]]]);
	printf("%d",ans);
	return 0; 
}