比赛 |
2025暑期集训第8场 |
评测结果 |
AAAAAAAAAA |
题目名称 |
抢掠计划 |
最终得分 |
100 |
用户昵称 |
彭欣越 |
运行时间 |
0.071 s |
代码语言 |
C++ |
内存使用 |
7.63 MiB |
提交时间 |
2025-08-13 09:08:01 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=500010;
int n,m,s,p,a[N],mk[N],dis[N],ans;
int tot,tot1,head[N],head1[N];
int dfn[N],low[N],vis[N],st[N],col[N],val[N],cnt,scc,idx,jsq;
struct node {
int u,v,w,nxt;
}e[N],e1[N];
void add (int u,int v) {
e[++tot].v=v;
e[tot].u=u;
//e[tot].w=w;
e[tot].nxt=head[u];
head[u]=tot;
}
void tarjan (int now) {
dfn[now]=++cnt;
low[now]=cnt;
vis[now]=1;
st[++idx]=now;
for (int i=head[now];i;i=e[i].nxt) {
int v=e[i].v;
if (!dfn[v]) {
tarjan(v);
low[now]=min(low[now],low[v]);
}else if (vis[v]) {
low[now]=min(low[now],low[v]);
}
}
int t=0;
if (low[now]==dfn[now]) {
jsq++;
while (t=st[idx--]) {
col[t]=jsq;
val[jsq]+=a[t];
vis[t]=0;
if (now==t) break;
}
}
}
queue<int>q;
void spfa (int s) {
//cout << 1 <<endl;
memset(dis,0,sizeof(dis));
memset(vis,0,sizeof(vis));
vis[col[s]]=1;
dis[col[s]]=val[col[s]];
q.push(col[s]);
while (!q.empty()) {
//cout << 1 <<endl;
int u=q.front();
q.pop();
vis[u]=0;
for (int i=head1[u];i;i=e1[i].nxt) {
int v=e1[i].v,w=e1[i].w;
if (dis[v]<dis[u]+w) {
dis[v]=dis[u]+w;
//cout << dis[v] <<' '<< v <<endl;
if (!vis[v]) {
q.push(v);
vis[v]=1;
}
}
}
}
}
int main () {
freopen("atm.in","r",stdin);
freopen("atm.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin >> n >> m;
for (int i=1;i<=m;i++) {
int a,b;
cin >> a >> b;
add(a,b);
}
for (int i=1;i<=n;i++) cin >> a[i];
cin >> s >> p;
for (int i=1;i<=p;i++) cin >> mk[i];
for (int i=1;i<=n;i++) if (!dfn[i]) tarjan(i);
for (int i=1;i<=m;i++) {
int x=col[e[i].u],y=col[e[i].v];
if (x!=y) {
e1[++tot1].u=x;
e1[tot1].v=y;
e1[tot1].w=val[y];
//cout << val[y] <<endl;
e1[tot1].nxt=head1[x];
head1[x]=tot1;
}
}
//cout << val[col[s]] <<endl;
spfa(s);
for (int i=1;i<=p;i++) {
ans=max(ans,dis[col[mk[i]]]);
}
cout << ans <<endl;
return 0;
}