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