比赛 |
2025暑期集训第8场 |
评测结果 |
AAAAAAAAAA |
题目名称 |
抢掠计划 |
最终得分 |
100 |
用户昵称 |
汐汐很希希 |
运行时间 |
0.128 s |
代码语言 |
C++ |
内存使用 |
11.41 MiB |
提交时间 |
2025-08-13 09:52:28 |
显示代码纯文本
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=500010;
int n,m,s,p,v[N],u[N],w[N],bar[N],head[N],d[N],cnt,ans;
int dfn[N],stk[N],low[N],sum[N],newg[N],tot,stamp,top;
bool vis[N];
queue<int> q;
struct Graph
{
int nxt,v,to;
}g[N];
void clear()
{
cnt=0;
memset(g,0,sizeof(g));
memset(head,0,sizeof(head));
}
void add(int u,int v)
{
cnt++;
g[cnt].to=v;
g[cnt].nxt=head[u];
head[u]=cnt;
}
void build(int u,int v,int w)
{
cnt++;
g[cnt].to=v;
g[cnt].v=w;
g[cnt].nxt=head[u];
head[u]=cnt;
}
void tarjan(int x)
{
dfn[x]=low[x]=++stamp;
stk[++top]=x;vis[x]=true;
for(int i=head[x];i;i=g[i].nxt)
{
int t=g[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{
int tp=stk[top];
sum[tot]+=w[tp];
vis[tp]=false;
newg[tp]=tot;
}while(stk[top--]!=x);
}
return;
}
void spfa(int s)
{
for(int i=1;i<=tot;i++) d[i]=0;
int gs=newg[s];
q.push(gs);
vis[gs]=true;
d[gs]=sum[gs];
while(!q.empty())
{
int h=q.front();q.pop();
vis[h]=false;
for(int i=head[h];i;i=g[i].nxt)
{
int t=g[i].to;
if(d[t]<d[h]+g[i].v)
{
d[t]=d[h]+g[i].v;
if(!vis[t])
{
q.push(t);
vis[t]=true;
}
}
}
}
return;
}
int main()
{
freopen("atm.in","r",stdin);
freopen("atm.out","w",stdout);
cin>>n>>m;
clear();
for(int i=1;i<=m;i++)
{
cin>>u[i]>>v[i];
add(u[i],v[i]);
}
for(int i=1;i<=n;i++) cin>>w[i];
cin>>s>>p;
for(int i=1;i<=p;i++) cin>>bar[i];
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
clear();
for(int i=1;i<=m;i++) if(newg[u[i]]!=newg[v[i]]) build(newg[u[i]],newg[v[i]],sum[newg[v[i]]]);
spfa(s);
for(int i=1;i<=p;i++) ans=max(ans,d[newg[bar[i]]]);
cout<<ans<<endl;
return 0;
}