比赛 |
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;
}