dijkstra

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

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 500010, M = 2 * N, INF = 0x3f3f3f3f;

int n, m;
int id[N];
bool st[N];
bool pub[N];
int dist[N];
int monkey[N];
int s, pub_cnt;
stack<int> stk;
bool in_stk[N];
int sum[N], scc_cnt;
int dfn[N], low[N], timestamp;
int h[N], hr[N],e[M], ne[M], idx;

void add(int h[], int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx;
    idx ++ ;
}

void tarjan(int u)
{
    low[u] = dfn[u] = ++ timestamp;
    stk.push(u), in_stk[u] = true;
    
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if (in_stk[j]) low[u] = min(low[u], dfn[j]);
    }
    
    if (dfn[u] == low[u])
    {
        int y;
        scc_cnt ++ ;
        do
        {
            y = stk.top();
            stk.pop();
            in_stk[y] = false;
            id[y] = scc_cnt;
            if (monkey[y] != INF) sum[scc_cnt] += monkey[y];
        } while (y != u);
    }
}

void dijkstra(int s)
{
    priority_queue<PII, vector<PII>, greater<PII>> q;
    memset(dist, -0x3f, sizeof dist);
    dist[id[s]] = sum[id[s]];
    q.push({dist[id[s]], id[s]});
    
    while (q.size())
    {
        auto t = q.top();
        q.pop();
        
        int ver = t.y, distance = t.x;
        
        if (st[ver]) continue;
        st[ver] = true;
        
        for (int i = hr[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] < distance + sum[j])
            {
                dist[j] = distance + sum[j];
                q.push({dist[j], j});
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    
    memset(h, -1, sizeof h);
    memset(hr, -1, sizeof hr);
    memset(monkey, 0x3f, sizeof monkey);
    
    while (m -- )
    {
        int a, b;
        scanf("%d %d", &a, &b);
        add(h, a, b);
    }
    
    for (int i = 1; i <= n; i ++ )
    {
        int x;
        scanf("%d", &x);
        monkey[i] = min(x, monkey[i]);
    }
    
    cin >> s >> pub_cnt;
    while (pub_cnt -- )
    {
        int id_pub;
        scanf("%d", &id_pub);
        pub[id_pub] = true;
    }
    
    for (int i = 1; i <= n; i ++ )
        if (!dfn[i])
            tarjan(i);
    
    for (int i = 1; i <= n; i ++ )
        for (int j = h[i]; j != -1; j = ne[j])
        {
            int k = e[j];
            int a = id[i], b = id[k];
            if (a != b) add(hr, a, b);
        }
    
    dijkstra(s);
    long long res = 0;
    for (int i = 1; i <= n; i ++ ) 
        if (dist[id[i]] != -INF && pub[i]) res = max(res, (long long)dist[id[i]]);
        
    cout << res << endl;
    
    return 0;
}

spfa

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

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 500010, M = 2 * N, INF = 0x3f3f3f3f;

int n, m;
int id[N];
bool st[N];
bool pub[N];
int dist[N];
int monkey[N];
int s, pub_cnt;
stack<int> stk;
bool in_stk[N];
int sum[N], scc_cnt;
int dfn[N], low[N], timestamp;
int h[N], hr[N],e[M], ne[M], idx;

void add(int h[], int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx;
    idx ++ ;
}

void tarjan(int u)
{
    low[u] = dfn[u] = ++ timestamp;
    stk.push(u), in_stk[u] = true;
    
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if (in_stk[j]) low[u] = min(low[u], dfn[j]);
    }
    
    if (dfn[u] == low[u])
    {
        int y;
        scc_cnt ++ ;
        do
        {
            y = stk.top();
            stk.pop();
            in_stk[y] = false;
            id[y] = scc_cnt;
            sum[scc_cnt] += monkey[y];
        } while (y != u);
    }
}

void dijkstra(int s)
{
    priority_queue<PII, vector<PII>, greater<PII>> q;
    memset(dist, -0x3f, sizeof dist);
    dist[id[s]] = sum[id[s]];
    q.push({dist[id[s]], id[s]});
    
    while (q.size())
    {
        auto t = q.top();
        q.pop();
        
        int ver = t.y, distance = t.x;
        
        if (st[ver]) continue;
        st[ver] = true;
        
        for (int i = hr[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] < distance + sum[j])
            {
                dist[j] = distance + sum[j];
                q.push({dist[j], j});
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    
    memset(h, -1, sizeof h);
    memset(hr, -1, sizeof hr);
    
    while (m -- )
    {
        int a, b;
        scanf("%d %d", &a, &b);
        add(h, a, b);
    }
    
    for (int i = 1; i <= n; i ++ ) scanf("%d", &monkey[i]);
    
    cin >> s >> pub_cnt;
    while (pub_cnt -- )
    {
        int id_pub;
        scanf("%d", &id_pub);
        pub[id_pub] = true;
    }
    
    for (int i = 1; i <= n; i ++ )
        if (!dfn[i])
            tarjan(i);
    
    for (int i = 1; i <= n; i ++ )
        for (int j = h[i]; j != -1; j = ne[j])
        {
            int k = e[j];
            int a = id[i], b = id[k];
            if (a != b) add(hr, a, b);
        }
    
    dijkstra(s);
    int res = 0;
    for (int i = 1; i <= n; i ++ ) 
        if (dist[id[i]] != -INF && pub[i]) res = max(res, dist[id[i]]);
        
    cout << res << endl;
    
    return 0;
}