记录编号	426877	评测结果	AAAAAAAAAA
题目名称	2449.[APIO2009] 抢掠计划	最终得分	100
用户昵称	AAAAAAAAAA	是否通过	通过
代码语言	C++	运行时间	0.042 s
提交时间	2017-07-19 17:41:56	内存使用	24.18 MiB

#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstring>
#define MAXN 500010
#define INF 0x3f3f3f3f
namespace IO {
	char buf[1 << 15], *fs, *ft;
	inline char gc() { return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 15, stdin), fs == ft)) ? 0 : *fs++; }
	inline int qr() {
		int x = 0, ch = gc();
		while (ch<'0' || ch>'9') { ch = gc(); }
		while (ch >= '0'&&ch <= '9') { x = (x << 1) + (x << 3) + ch - '0';ch = gc(); }
		return x;
	}
}using namespace IO;
using namespace std;
/***********************************************************************************************/
struct Edge {
	int t, next;
}e[MAXN],g[MAXN];
int N, M, S, P, head1[MAXN], head2[MAXN], cnt1 = 1, cnt2 = 1;
void Add_Edge1(int from, int to) {
	e[++cnt1].t = to;e[cnt1].next = head1[from];head1[from] = cnt1;
}
void Add_Edge2(int from,int to){
	g[++cnt2].t = to;g[cnt2].next = head2[from];head2[from] = cnt2;
}
int dfn[MAXN], low[MAXN], belong[MAXN], dep, scc, val[MAXN], c[MAXN];
stack<int> s;
bool vis[MAXN];
void Tarjan(int u) {//求强连通分量
	dfn[u] = low[u] = ++dep;
	s.push(u);vis[u] = 1;
	for (int i = head1[u];i;i = e[i].next) {
		int v = e[i].t;
		if (!dfn[v]) {
			Tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if (vis[v])low[u] = min(low[u], dfn[v]);
	}
	if (low[u] == dfn[u]) {
		int temp=0;scc++;
		while (temp != u && !s.empty()) {
			temp = s.top();
			s.pop();
			vis[temp] = 0;belong[temp] = scc;val[scc] += c[temp];
		}
	}
}
void Rebuild() {//缩点重建图
	for (int i = 1;i <= N;i++) {
		for (int j = head1[i];j;j = e[j].next) {
			if (belong[i] != belong[e[j].t]) {
				Add_Edge2(belong[i], belong[e[j].t]);
			}
		}
	}
}
int d[MAXN];
queue<int>q;
bool inq[MAXN];
void SPFA() {
	q.push(belong[S]);inq[belong[S]] = 1;
	d[belong[S]] = val[belong[S]];
	while (!q.empty()) {
		int u = q.front();
		q.pop();inq[u] = 0;
		for (int i = head2[u];i;i = g[i].next) {
			int v = g[i].t;
			if (d[u] + val[v] > d[v]) {
				d[v] = d[u] + val[v];
				if (!inq[v])q.push(v), inq[v] = 1;
			}
		}
	}
}
int main() {
	freopen("atm.in", "r", stdin);
	freopen("atm.out", "w", stdout);
	int x, y, ans = 0;
	N = qr();M = qr();
	for (int i = 1;i <= M;i++) {
		x = qr();y = qr();
		Add_Edge1(x, y);
	}
	for (int i = 1;i <= N;i++)c[i] = qr();
	S = qr();P = qr();
	for (int i = 1;i <= N;i++) { if (!dfn[i])Tarjan(i); }
	Rebuild();
	SPFA();
	for (int i = 1;i <= P;i++) {
		x = qr();
		ans = max(ans, d[belong[x]]);
	}
	printf("%d", ans);
	return 0;
}
//int chh = sb();
//int main() { ; }