比赛 2025暑期集训第8场 评测结果 AAAAAAAAAA
题目名称 抢掠计划 最终得分 100
用户昵称 淮淮清子 运行时间 0.058 s
代码语言 C++ 内存使用 5.78 MiB
提交时间 2025-08-13 08:59:19
显示代码纯文本
#include <iostream>
#include <queue>
#include <stack>
#include <algorithm>
#include <vector>
#include <cstring>
#include <set>
using namespace std;

const int MAXM = 500005;
const int MAXN = 500005;
int n, m, tot1 = 0, tot2 = 0, num = 0;
int id[MAXN], w[MAXN], sum[MAXN], d[MAXN];
int dfn[MAXN], low[MAXN];
stack<int> st;
bool ins[MAXN], flag[MAXN];
int h1[MAXN], h2[MAXN];
struct node {
    int from, to, next;
} e[MAXM], E[MAXM];

void add1(int x, int y){
    e[++tot1] = {x, y, h1[x]};
    h1[x] = tot1;
}

void add2(int x, int y){
    E[++tot2] = {x, y, h2[x]};
    h2[x] = tot2;
}

void tarjan(int u){
    dfn[u] = low[u] = ++num;
    ins[u] = 1;
    st.push(u);
    for(int i = h1[u];i;i = e[i].next){
        int v = e[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
		else if(ins[v]){
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(dfn[u] == low[u]){
        int v;
        do{
            v = st.top(); st.pop();
            ins[v] = 0;
            id[v] = u;
            if(u != v){
                w[u] += w[v];
            }
        }while (u != v);
    }
}

void dijkstra(int s){
    memset(d, -0x3f, sizeof(d));
    d[s] = w[s];
    set<pair<int, int>, greater<pair<int, int> > > heap;
    heap.insert({d[s], s});
    while(!heap.empty()){
        int u = heap.begin() -> second;
        heap.erase(heap.begin());
        for(int i = h2[u];i;i = E[i].next){
            int v = E[i].to;
            if(d[v] < d[u] + w[v]){
                heap.erase({d[v], v});
                d[v] = d[u] + w[v];
                heap.insert({d[v], v});
            }
        }
    }
}

int main(){
	freopen("atm.in","r",stdin);
	freopen("atm.out","w",stdout);
    cin.tie(0) -> ios::sync_with_stdio(0);
    cin >> n >> m;
    for(int i = 1;i <= m;i ++){
        int u, v;
        cin >> u >> v;
        add1(u, v);
    }
    for(int i = 1;i <= n;i ++){
        cin >> w[i];
    }

    for(int i = 1;i <= n;i ++){
        if (!dfn[i]) tarjan(i);
    }

    for(int i = 1;i <= m;i ++){
        int u = e[i].from, v = e[i].to;
        if(id[u] != id[v]){
            add2(id[u], id[v]);
        }
    }

    for(int i = 1;i <= n;i ++){
        if(id[i] == i){
            sum[i] = w[i];
        }
    }

    int S, P;
    cin >> S >> P;
    for(int i = 1;i <= P;i ++){
        int x; cin >> x;
        flag[id[x]] = true;
    }
    dijkstra(id[S]);
    int ans = 0;
    for(int i = 1;i <= n;i ++){
        if(id[i] == i && flag[i]){
            ans = max(ans, d[i]);
        }
    }

    cout << ans << '\n';

    return 0;
}