题目链接：https://loj.ac/problem/10096

做法

这题水到我都不想说什么了，反正就是缩完点然后直接上LPFA（你们管她叫SPFA吗？）求最长路。完。

#include 
#include 
#include 
#include 
#define Re register
using namespace std;
const int maxN = 500005;
int N, M, S, P;
struct EE {
    int u, v;
} E[maxN];
struct Edge {
    int nxt, to;
} e[maxN];
int cnte = 1, head[maxN];
inline void add_Edge(int i, int j) { e[++cnte].nxt = head[i], e[cnte].to = j, head[i] = cnte; }
int scc[maxN], dfn[maxN], cnt_dfn, top, stk[maxN], low[maxN], c[maxN], dis[maxN], val[maxN], cnt_scc;
bool vis[maxN], ins[maxN];
void tarjan(int u) {
    low[u] = dfn[u] = ++cnt_dfn;
    stk[++top] = u, ins[u] = true;
    for (int i = head[u], v; i; i = e[i].nxt) {
        if (!dfn[v = e[i].to]) {
            tarjan(v), low[u] = min(low[u], low[v]);
        } else if (ins[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        Re int k;
        ++cnt_scc;
        do {
            k = stk[top--];
            ins[k] = false;
            scc[k] = cnt_scc;
            val[cnt_scc] += c[k];
        } while (k != u);
    }
}
void LPFA(int S) {
    memset(dis, -0x3f, sizeof(dis));
    queue<int> Q;
    Q.push(S), vis[S] = true, dis[S] = val[S];
    while (!Q.empty()) {
        Re int u = Q.front();
        Q.pop();
        vis[u] = false;
        for (int i = head[u]; i; i = e[i].nxt) {
            Re int v = e[i].to;
            if (dis[v] < dis[u] + val[v]) {
                dis[v] = dis[u] + val[v];
                if (!vis[v])
                    Q.push(v), vis[v] = true;
            }
        }
    }
}
int main() {
    cin >> N >> M;
    for (int i = 1; i <= M; ++i) {
        scanf("%d%d", &E[i].u, &E[i].v);
        add_Edge(E[i].u, E[i].v);
    }
    for (int i = 1; i <= N; ++i) scanf("%d", &c[i]);
    cin >> S >> P;
    for (int i = 1; i <= N; ++i)
        if (!dfn[i])
            tarjan(i);
    memset(head, 0, sizeof(head)), cnte = 1;
    for (int i = 1; i <= M; ++i)
        if (scc[E[i].u] != scc[E[i].v])
            add_Edge(scc[E[i].u], scc[E[i].v]);
    LPFA(scc[S]);
    int Ans = -1;
    for (int x, i = 1; i <= P; ++i) {
        scanf("%d", &x);
        Ans = max(Ans, dis[scc[x]]);
    }
    printf("%d\n", Ans);
    return 0;
}