比赛 |
2025暑期集训第8场 |
评测结果 |
AAAAAAAAAA |
题目名称 |
抢掠计划 |
最终得分 |
100 |
用户昵称 |
二乾五 |
运行时间 |
0.242 s |
代码语言 |
C++ |
内存使用 |
30.14 MiB |
提交时间 |
2025-08-13 11:14:30 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define cpy(a,b) copy(begin(a),end(a),begin(b))
#define ld long double
#define dot(x) fixed<<setprecision(x)
#define foru(a,b,c) for(ll a=b;a<=c;a++)
ll n,m,cc,p;
vector<vector<ll>>a(500005);
set<ll>_98;
ll cash[500005];
bool is98[500005];
ll dcnt,low[500005],dfsn[500005];
ll scc[500005],scnt,sum[500005];
bool stacked[500005];
stack<ll>s;
void tarjan(ll u){
dfsn[u]=low[u]=++dcnt;
s.push(u);stacked[u]=1;
for(auto v:a[u]){
if(!dfsn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}else if(stacked[v]){
low[u]=min(low[u],dfsn[v]);
}
}
if(dfsn[u]==low[u]){
scnt++;
ll x;
do{
x=s.top();
s.pop();
scc[x]=scnt;
if(is98[x])_98.insert(scnt);
sum[scnt]+=cash[x];
stacked[x]=0;
}while(x!=u);
}
}
vector<vector<ll>>b(500005);
ll dist[500005];
bool inq[500005];
int main(){
freopen("atm.in" ,"r",stdin );
freopen("atm.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
cin>>n>>m;
foru(i,1,m){
ll u,v;
cin>>u>>v;
a[u].push_back(v);
}
foru(i,1,n)cin>>cash[i];
cin>>cc>>p;
foru(i,1,p){
ll x;
cin>>x;
is98[x]=1;
}
foru(i,1,n){
if(!dfsn[i]){
tarjan(i);
}
}
foru(u,1,n){
for(auto v:a[u]){
if(scc[u]!=scc[v]){
b[scc[u]].push_back(scc[v]);
}
}
}
memset(dist,-1,sizeof(dist));
queue<ll>q;
dist[scc[cc]]=sum[scc[cc]];
q.push(scc[cc]);
inq[scc[cc]]=1;
while(!q.empty()){
ll u=q.front();
q.pop();
inq[u]=0;
for(auto v:b[u]){
if(dist[v]<dist[u]+sum[v]){
dist[v]=dist[u]+sum[v];
if(!inq[v]){
q.push(v);
inq[v]=1;
}
}
}
}
ll ans=0;
for(auto s:_98)ans=max(ans,dist[s]);
cout<<ans;
return 0;
}