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