比赛 |
2025暑期集训第8场 |
评测结果 |
AAAAAAAAAA |
题目名称 |
抢掠计划 |
最终得分 |
100 |
用户昵称 |
Hollow07 |
运行时间 |
0.162 s |
代码语言 |
C++ |
内存使用 |
19.56 MiB |
提交时间 |
2025-08-13 09:11:28 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct edge{
ll to,val,next;
} e[510000];
ll m,n,p,s,cnt,g[510000],u[510000],v[510000],w[510000],hd[510000];
ll bar[510000],dis[510000],dfn[510000],low[510000],stk[510000],sum[510000];
bool vis[510000];
queue <ll> q;
ll ans,top,tot,total;
void add(ll u,ll v){
cnt++;
e[cnt].to=v;
e[cnt].next=hd[u];
hd[u]=cnt;
}
void build(ll u,ll v,ll w){
cnt++;
e[cnt].to=v;
e[cnt].val=w;
e[cnt].next=hd[u];
hd[u]=cnt;
}
void clear(){
cnt=0;
memset(e,0,sizeof(e));
memset(hd,0,sizeof(hd));
}
void Tarjan(ll x){
dfn[x]=low[x]=++total;
stk[++top]=x;vis[x]=1;
for(int i=hd[x];i;i=e[i].next){
ll t=e[i].to;
if(!dfn[t]){
Tarjan(t);
low[x]=min(low[x],low[t]);
}else if(vis[t])
low[x]=min(low[x],dfn[t]);
}
if(dfn[x]==low[x]){
tot++;
do{
ll tp=stk[top];
sum[tot]+=w[tp];
vis[tp]=0;
g[tp]=tot;
}while(stk[top--]!=x);
}
}
void spfa(ll s){
for(int i=1;i<=tot;i++) dis[i]=0;
ll gs=g[s];
q.push(gs);
vis[gs]=1;
dis[gs]=sum[gs];
while(!q.empty()){
ll h=q.front();q.pop();
vis[h]=0;
for(int i=hd[h];i;i=e[i].next){
ll t=e[i].to;
if(dis[t]<dis[h]+e[i].val){
dis[t]=dis[h]+e[i].val;
if(!vis[t]){
q.push(t);
vis[t]=1;
}
}
}
}
}
int main(){
// freopen("in.in","r",stdin);
freopen("atm.in","r",stdin);
freopen("atm.out","w",stdout);
scanf("%lld %lld",&n,&m);
for(int i=1;i<=m;i++){
scanf("%lld %lld",&u[i],&v[i]);
add(u[i],v[i]);
}
for(int i=1;i<=n;i++) scanf("%lld",&w[i]);
scanf("%lld %lld",&s,&p);
for(int i=1;i<=p;i++) scanf("%lld",&bar[i]);
for(int i=1;i<=n;i++)
if(!dfn[i]) Tarjan(i);
clear();
for(int i=1;i<=m;i++)
if(g[u[i]]!=g[v[i]])
build(g[u[i]],g[v[i]],sum[g[v[i]]]);
spfa(s);
for(int i=1;i<=p;i++)
ans=max(ans,dis[g[bar[i]]]);
printf("%lld",ans);
return 0;
}