比赛 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;
}