记录编号	403309	评测结果	AAAAAAAAAA
题目名称	[APIO2009] 抢掠计划	最终得分	100
用户昵称	kZime	是否通过	通过
代码语言	C++	运行时间	0.101 s
提交时间	2017-05-09 21:03:48	内存使用	30.83 MiB

# include <bits/stdc++.h>
# define MAXN 500023
using namespace std;
inline int get_num() {
    int k = 0, f = 1;
    char c = getchar();
    for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
    for(; isdigit(c); c = getchar()) k = k * 10 + c - '0';
    return k * f;
}
int N, M, n, s, w[MAXN], ww[MAXN], head1[MAXN], head2[MAXN], cnt, id, dfn[MAXN], low[MAXN], lky;
int inq[MAXN], bln[MAXN], ins[MAXN], sta[MAXN], top, bar[MAXN], dis[MAXN];
struct edge{
    int to, ne;
    inline edge(){;}
    inline edge(int to_, int ne_) {
        to = to_, ne = ne_;
    }
}e[MAXN << 1];
inline void addedge(int fr, int to, int *head) {
    e[++cnt] = edge(to, head[fr]), head[fr] = cnt;
}
void Tarjan(int u) {
    dfn[u] = low[u] = ++id;
    ins[u] = 1;
    sta[++top] = u;
    for(int i = head1[u]; i; i = e[i].ne) {
        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], low[v]);
        }
    }
    if(low[u] == dfn[u]) {
        ++lky;
        int tmp = u + 1;
        while(tmp != u) {
            tmp = sta[top--];
            bln[tmp] = lky;
            ww[lky] += w[tmp];
            ins[tmp] = 0;
        }
    }
}
inline void SPFA(int s) {
    inq[s] = 1;
    queue <int> q;
    q.push(s);
    dis[s] = ww[s];
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        inq[u] = 0;
        for(int i = head2[u]; i; i = e[i].ne) {
            int v = e[i].to;
            if(dis[v] < dis[u] + ww[v]) {
                dis[v] = dis[u] + ww[v];
                if(!inq[v]) {
                    q.push(v);
                    inq[v] = 1;
                }
            }
        }
    }
}
int main () {
    freopen("atm.in", "r", stdin);
    freopen("atm.out", "w", stdout);
    N = get_num();
    M = get_num();
    for(int i = 1; i <= M; i++) {
        int u = get_num();
        int v = get_num();
        addedge(u, v, head1);
    }
    for(int i = 1; i <= N; i++) {
        w[i] = get_num();
    }
    for(int i = 1; i <= N; i++) {
        if(!dfn[i])Tarjan(i);
    }
    s = get_num();
    n = get_num();
    for(int u = 1; u <= N; u++) {
        for(int i = head1[u]; i; i = e[i].ne) {
            int v = e[i].to;
            if(bln[u] != bln[v]) {
                addedge(bln[u], bln[v], head2);
            }
        }
    }
    SPFA(bln[s]);
    int ans = 0;
    while(n--) {
        int tmp = get_num();
        ans = max(ans, dis[bln[tmp]]);
    }
    printf("%d\n", ans);
    return 0;
}