道路与航线

这个题有负环，看一下边数，用 spfa 没一点问题，但是这个题会卡 spfa
注意到航线是单向的dag，并且道路是没有负权的，所以可以在每个 block 里跑 dijkstra
外部跑 topsort，这样就可以根据 拓扑序去更新了

注意点

(1) 我第一次想的是更新的话就把他的入度减去，但是这样是不对的，因为有可能第一个 block里有两个不一样的点，一个
是正航线，一个是负航线，那么此时如果负航线先被更新的话，正的就更新不了了，但是应该被更新，所以要写到外面去，
一旦遍历到就减去入度
(2) 可能会有的点和 S 不连通， 但是由于 topsort 一定会做完，所以如果航线是负数，也会被更新，所以应该写大
于一个大数

//拓扑排序 + dijkstra
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cstdio>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 25010, M = 150010, INF = 0x3f3f3f3f;

int n, mr, mp, S; // mr 双向道路  mp 单向航线
int h[N], e[M], ne[M], w[M], idx;
int dist[N];
bool st[N];
int id[N], bcnt; // 每个点属于哪个 block
int din[N];
vector<int> block[N]; // 每一个块中的 vertix
queue<int> q; // topsort 的队列

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

void dfs(int u, int bid){
    id[u] = bid;
    block[bid].push_back(u);
    for(int i = h[u];~i;i = ne[i]){
        int j = e[i];
        if (!id[j]) dfs(j, bid);
    }
}

void dijkstra(int bid){

    priority_queue<PII, vector<PII>, greater<PII>> heap;
    for (auto ver : block[bid]) heap.push({dist[ver], ver});

    while(heap.size()){

        auto t = heap.top();
        heap.pop();

        int ver = t.y, distance = t.x;
        if (st[ver]) continue;
        st[ver] = true;

        for(int i = h[ver];~i;i = ne[i]){
            int j = e[i];
            if(dist[j] > dist[ver] + w[i]){
                dist[j] = dist[ver] + w[i];
                if (id[ver] == id[j]) heap.push({dist[j], j});
                //else if( -- din[id[j]] == 0) q.push(id[j]); (1)
            }
            if(id[ver] != id[j] && -- din[id[j]] == 0) q.push(id[j]);
        }
    }
}

void topsort(){

    memset(dist, 0x3f, sizeof dist);
    dist[S] = 0;

    for(int i = 1;i <= bcnt;i ++ )
        if(!din[i])
            q.push(i);

    while(q.size()){
        auto t = q.front();
        q.pop();
        dijkstra(t);
    }
}

int main(){

    cin >> n >> mr >> mp >> S;
    memset(h, -1, sizeof h);

    while(mr -- ){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }

    for(int i = 1;i <= n;i ++ )
        if(!id[i])
            dfs(i, ++ bcnt);

    while(mp -- ){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        din[id[b]] ++ ;
    }

    topsort();
    for(int i = 1;i <= n;i ++ ){
        if(dist[i] > INF / 2) puts("NO PATH"); // (2)
        else printf("%d\n", dist[i]);
    }

    return 0;
}