比赛 20160902 评测结果 AAAAAAAAAA
题目名称 抢掠计划 最终得分 100
用户昵称 KZNS 运行时间 0.057 s
代码语言 C++ 内存使用 14.44 MiB
提交时间 2016-09-02 20:14:22
显示代码纯文本
//KZNS
#include <cstdio>
#include <stack>
#include <vector>
#include <queue>
using namespace std;
#define Nmax 500003
int N, M;
vector<int> gp[Nmax];
int v[Nmax] = {0};
int S;
void rin() {
	scanf("%d %d", &N, &M);
	int a, b;
	for (int i = 0; i < M; i++) {
		scanf("%d %d", &a, &b);
		gp[a].push_back(b);
	}
	for (int i = 1; i <= N; i++)
		scanf("%d", v+i);
	scanf("%d", &S);
}
int lw[Nmax];
int fa[Nmax];
int ttmm = 1;
stack<int> stk;
bool isk[Nmax] = {0};
void TJ(int x) {
	int T, t;
	lw[x] = T = ttmm++;
	stk.push(x);
	isk[x] = true;
	for (int i = 0; i < gp[x].size(); i++) {
		t = gp[x][i];
		if (!lw[t])
			TJ(t);
		if (isk[t])
			lw[x] = min(lw[x], lw[t]);
	}
	if (lw[x] == T) {
		t = stk.top();
		stk.pop();
		isk[t] = false;
		while (t != x) {
			v[x] += v[t];
			for (int i = 0; i < gp[t].size(); i++)
				gp[x].push_back(gp[t][i]);
			fa[t] = x;
			t = stk.top();
			stk.pop();
			isk[t] = false;
		}
		fa[t] = x;
	}
}
int sm[Nmax] = {0};
int lsd[Nmax] = {0};
void SPFA() {
	queue<int> ls;
	ls.push(fa[S]);
	lsd[fa[S]] = true;
	sm[fa[S]] = v[fa[S]];
	int u, t;
	while (!ls.empty()) {
		u = ls.front();
		ls.pop();
		lsd[u] = false;
		for (int i = 0; i < gp[u].size(); i++) {
			t = fa[gp[u][i]];
			if (t != u) {
				if (sm[u] + v[t] > sm[t]) {
					sm[t] = sm[u]+v[t];
					if (!lsd[t]) {
						ls.push(t);
						lsd[t] = true;
					}
				}
			}
		}
	}
}
void ansit() {
	int p, a, ans = 0;
	scanf("%d", &p);
	while (p--) {
		scanf("%d", &a);
		ans = max(ans, sm[fa[a]]);
	}
	printf("%d\n", ans);
}
int main() {
	freopen("atm.in", "r", stdin);
	freopen("atm.out", "w", stdout);
	rin();
	TJ(S);
	SPFA();
	ansit();
	return 0;
}
//UBWH