bzoj1179: [Apio2009]Atm

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <stack>
#include <queue>
#include <cstring>

using namespace std;
typedef long long lli;
const int maxn = 500100, maxm = 500100;
const lli infinit = 0x007f7f7f7f7f7f7fll;

class Graph
{
public:
    struct edge
    {
        int u, v;
        edge *next;
    };
    edge *edges[maxn], epool[maxm];
    int n, ecnt;
    void addedge(int u, int v)
    {
        edge *p = &epool[++ecnt];
        p->u = u; p->v = v;
        p->next = edges[u]; edges[u] = p;
        return ;
    }
    void clear(void)
    {
        memset(edges, 0, sizeof(edges));
        memset(epool, 0, sizeof(epool));
        n = ecnt = 0;
        return ;
    }
};

class Tarjan : public Graph
{
public:
    int dfn[maxn], low[maxn];
    int belong[maxn]; // This is the result of the final procedure...
    int bcnt, dcnt;
    stack<int> stk;
    bool instk[maxn];
    // My greatest gratitude to @byvoid for this article...
    // https://www.byvoid.com/blog/scc-tarjan
    void dfs(int p)
    {
        dfn[p] = low[p] = ++dcnt; // Assign DFS number index
        stk.push(p);
        instk[p] = true;
        for (edge *ep = edges[p]; ep; ep = ep->next) {
            int q = ep->v;
            if (!dfn[q]) {
                dfs(q);
                if (low[p] > low[q])
                    low[p] = low[q];
            } else if (instk[q] && dfn[q] < low[p])
                low[p] = dfn[q];
        }
        if (dfn[p] == low[p]) {
            bcnt++; // Assign new belong / block counter / index
            int q = 0;
            do {
                q = stk.top();
                stk.pop();
                instk[q] = false;
                belong[q] = bcnt;
            } while (q != p);
        }
        return ;
    }
    void eval(void)
    {
        while (!stk.empty())
            stk.pop();
        bcnt = dcnt = 0;
        memset(dfn, 0, sizeof(dfn));
        memset(low, 0, sizeof(low));
        for (int i = 1; i <= n; i++)
            if (!dfn[i])
                dfs(i);
        return ;
    }
} graph;

class SPFA : public Graph
{
public:
    lli dist[maxn];
    lli weight[maxn];
    bool inque[maxn];
    int s;
    void eval(void)
    {
        queue<int> que;
        for (int i = 1; i <= n; i++)
            inque[i] = false, dist[i] = infinit;
        que.push(s);
        inque[s] = true;
        dist[s] = weight[s];
        while (!que.empty()) {
            int p = que.front();
            que.pop();
            for (edge *ep = edges[p]; ep; ep = ep->next) {
                if (dist[p] + weight[ep->v] > dist[ep->v] || dist[ep->v] >= infinit) {
                    dist[ep->v] = dist[p] + weight[ep->v];
                    if (!inque[ep->v]) {
                        que.push(ep->v);
                        inque[ep->v] = true;
                    }
                }
            }
            inque[p] = false;
        }
        return ;
    }
} spfa;

int n, m, S, P;
int v[maxn];
int pub[maxn], pubcnt;

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    graph.n = n;
    spfa.n = n;
    for (int i = 1, a, b; i <= m; i++) {
        scanf("%d%d", &a, &b);
        graph.addedge(a, b);
    }
    for (int i = 1; i <= n; i++)
        scanf("%d", &v[i]);
    scanf("%d%d", &S, &P);
    for (int i = 1, a; i <= P; i++) {
        scanf("%d", &a);
        pub[++pubcnt] = a;
    }
    // Done input (That was a lot of input!)
    graph.eval();
    // Done evaluating graph values, now building new graph for SPFA.
    for (int i = 1; i <= m; i++) {
        Graph::edge* ed = &graph.epool[i];
        int p = graph.belong[ed->u],
            q = graph.belong[ed->v];
        if (p != q)
            spfa.addedge(p, q);
    }
    for (int i = 1; i <= n; i++)
        spfa.weight[graph.belong[i]] += v[i];
    spfa.s = graph.belong[S];
    spfa.eval();
    lli res = 0;
    for (int i = 1; i <= pubcnt; i++) {
        if (spfa.dist[graph.belong[pub[i]]] < infinit)
            res = max(res, spfa.dist[graph.belong[pub[i]]]);
    }
    printf("%lld", res);
    return 0;
}