洛谷[P3008]道路与航线

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int MAXN = 100005;
int init() {
    int rv = 0, fh = 1;
    char c = getchar();
    while(c <'0' || c > '9') {
        if(c == '-') fh = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        rv = (rv<<1) + (rv<<3) + c - '0';
        c = getchar();
    }
    return fh * rv;
}
int head[MAXN], n, m1, m2, s, nume, id[MAXN], tot, dis[MAXN], cnt[MAXN];
bool f[MAXN];
vector <int> ve[25005];
struct edge{
    int to, nxt, dis;
}e[MAXN<<1];
void adde(int from, int to, int dis) {
    e[++nume].to = to;
    e[nume].nxt = head[from];
    e[nume].dis = dis;
    head[from] = nume;
}
void dfs(int u) {
    if(id[u]) return;
    id[u] = tot;
    ve[tot].push_back(u);
    for(int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        dfs(v);
    }
}
struct node{
    int num, val;
    bool operator <(const node & b) const{
        return val > b.val;
    }
};
priority_queue  q;
queue <int> qq;
void dij(int x){ 
    for(int i = 0; i <(int)ve[x].size(); i++) q.push((node){ve[x][i], dis[ve[x][i]]});
    while(!q.empty()) {
        node u = q.top(); q.pop();
        if(f[u.num]) continue;
        f[u.num] = 1;
        for(int i = head[u.num]; i; i = e[i].nxt) {
            node v;
            v.num = e[i].to;
            if(id[v.num] == id[u.num] && dis[v.num] > dis[u.num] + e[i].dis) {
                dis[v.num] = dis[u.num] + e[i].dis;
                v.val = dis[v.num];
                q.push(v);
            }
            if(id[v.num] != id[u.num]) {
                dis[v.num] = min(dis[v.num], dis[u.num] + e[i].dis);
                cnt[id[v.num]]--;
                if(!cnt[id[v.num]]) {
                    qq.push(id[v.num]);
                }
            }
        }
    }
}
int main() {
    n = init(); m1 = init(); m2 = init(); s = init();
    for(int i = 1; i <= m1; i++) {
        int u = init(), v = init(), di = init();
        adde(u, v, di); adde(v, u, di); 
    }
    for(int i = 1; i <= n; i++) {if(!id[i]) tot++;dfs(i);}
    for(int i = 1; i <= m2; i++) {
        int u = init(), v = init(), di = init();
        adde(u, v, di);cnt[id[v]]++;
    }
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    for(int i = 1; i <= tot; i++) if(!cnt[i]) qq.push(i);
    while(!qq.empty()) {
        int v = qq.front(); qq.pop();
        dij(v);
    }
    for(int i = 1; i <= n; i++) {
        if(dis[i] > 100000000) printf("NO PATH\n");
        else printf("%d\n", dis[i]);
    }
    return 0;
}