比赛 |
2025暑期集训第8场 |
评测结果 |
AAAAAAAAAA |
题目名称 |
抢掠计划 |
最终得分 |
100 |
用户昵称 |
李金泽 |
运行时间 |
0.039 s |
代码语言 |
C++ |
内存使用 |
3.94 MiB |
提交时间 |
2025-08-13 11:38:51 |
显示代码纯文本
#include<cstdio>
#include<queue>
#define N 500005
#define M 500005
#define ll long long
using namespace std;
ll n,m,h[N],cnt,he[N],tot,scc[N],cou,now[N],low[N],sum[N],dfn,st[N],t,d[N],s,k,p[N],x,y,ans;bool b[N];
struct edg{ll v,n;}ed[M<<1];
struct edge{ll v,n;}e[M<<1];
void ad1(ll u,ll v){ed[++tot]={v,he[u]};he[u]=tot;}
void ad2(ll u,ll v){e[++cnt]={v,h[u]};h[u]=cnt;}
queue<ll>q;
ll max(ll x,ll y){return x>y?x:y;}
ll min(ll x,ll y){return x<y?x:y;}
void tarjan(ll u)
{
st[++t]=u;
now[u]=low[u]=++dfn;
for(ll i=he[u];i;i=ed[i].n)
{
ll v=ed[i].v;
if(!now[v])
tarjan(v),low[u]=min(low[u],low[v]);
else if(!scc[v])low[u]=min(low[u],now[v]);
}
if(now[u]==low[u])
{
cou++;
do{
scc[st[t]]=cou;
}while(st[t--]^u);
}
}
void spfa(){
q.push(s);d[s]=sum[s];
while(q.size())
{
ll u=q.front();q.pop();
b[u]=0;
for(ll i=h[u];i;i=e[i].n)
{
ll v=e[i].v;
if(d[u]+sum[v]>d[v])
{
d[v]=d[u]+sum[v];
if(!b[v])b[v]=1,q.push(v);
}
}
}
}
ll read(){
ll sum=0;bool f=0;char c=getchar();
for(;c<48||c>57;c=getchar())if(c==45)f=1;
for(;c>=48&&c<=57;c=getchar())sum=sum*10+(c&15);
return f?-sum:sum;
}
int main(){
freopen("atm.in","r",stdin);freopen("atm.out","w",stdout);
n=read(),m=read();
while(m--)x=read(),y=read(),ad1(x,y);
for(ll i=1;i<=n;i++)if(!now[i])tarjan(i);
for(ll i=1;i<=n;i++)
for(ll j=he[i];j;j=ed[j].n)
if(scc[i]^scc[ed[j].v])
ad2(scc[i],scc[ed[j].v]);
for(ll i=1;i<=n;i++)sum[scc[i]]+=read();
s=scc[read()],k=read();
spfa();
while(k--)ans=max(ans,d[scc[read()]]);
printf("%lld",ans);
return 0;
}