比赛 2025暑期集训第8场 评测结果 AAAAAAAAAA
题目名称 抢掠计划 最终得分 100
用户昵称 OTTF 运行时间 0.308 s
代码语言 C++ 内存使用 38.23 MiB
提交时间 2025-08-13 08:33:54
显示代码纯文本

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

const int N = 5e5 + 114;

int n;
int m;
vector<int> graph[N];
vector<int> another[N];
int a[N];
int s;
int p;
bool park[N];

vector<int> nums;
bool vis[N];
int cc;
int color[N];

vector<int> newGraph[N];
int newA[N];
bool newPark[N];
int dis[N];
bool newVis[N];

int res;

void dfs1 (int now) {
	vis[now] = true;
	for (auto son : graph[now]) {
		if (!vis[son]) {
			dfs1 (son);
		}
	}
	nums.push_back(now);
}

void dfs2 (int now) {
	color[now] = cc;
	for (auto son : another[now]) {
		if (!color[son]) {
			dfs2 (son);
		}
	}
}

void spfa () {
	queue<int> q;
	q.push(color[s]);
	newVis[color[s]] = true;
	dis[color[s]] = newA[color[s]];
	
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		newVis[now] = false;
		
		for (auto son : newGraph[now]) {
			if (dis[now] + newA[son] > dis[son]) {
				dis[son] = dis[now] + newA[son];
				
				if (!newVis[son]) {
					q.push(son);
					newVis[son] = true;
				}
			}
		}
	}
}

int main () {

    freopen ("atm.in", "r", stdin);
	freopen ("atm.out", "w", stdout);

	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		graph[u].push_back(v);
		another[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}

	cin >> s >> p;
	for (int i = 1; i <= p; i++) {
		int num;
		cin >> num;
		park[num] = true;
	}

	for (int i = 1; i <= n; i++) {
		if (!vis[i]) {
			dfs1 (i);
		}
	}
	for (auto it = nums.rbegin(); it != nums.rend(); it++) {
		if (!color[*it]) {
			cc++;
			dfs2 (*it);
		}
	}

	for (int now = 1; now <= n; now++) {
		newA[color[now]] += a[now];
		newPark[color[now]] |= park[now];
		for (auto son : graph[now]) {
			if (color[now] != color[son]) {
				newGraph[color[now]].push_back(color[son]);
			}
		}
	}

	spfa ();

	for (int i = 1; i <= cc; i++) {
		if (newPark[i]) {
			res = max (res, dis[i]);
		}
	}

	cout << res << endl;

	return 0;
}