求条闭关

#include<bits/stdc++.h>
//因为爱，所以坚持 
using namespace std;
#define int long long
const int INF = 0x3f3f3f3f;

struct edge{
    int v,next,w;
}ed[200050];
struct node{
    int d,u;
    bool operator < (const node& nod) const {
        return d > nod.d;
    }
};
int n,r,p,s,head[100050],tot,cnt,bl[100050],ok[100050],d[100050];
bool vis[100050];
vector<int> es[100050];
void add(int u, int v, int w){
    ed[tot].v = v; 
	ed[tot].w = w; 
	ed[tot].next = head[u]; 
	head[u] = tot++;
}
void dfs(int u){
    vis[u] = 1;
    bl[u] = cnt;
    es[cnt].push_back(u);
    for(int i = head[u];i != -1;i = ed[i].next){
        int v = ed[i].v;
        if(vis[v]) continue;
        dfs(v);
    }
}

signed main(){
    ios::sync_with_stdio(false); 
	cin.tie(0);
	cin>>n>>p>>r>>s;
    memset(head,-1,sizeof(head));
    for(int i = 1,a,b,c;i <= r;i++){
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    for(int i = 1;i <= n;i++){
        if(!vis[i]){
            cnt++;
            dfs(i);
        }
    }
    for(int i = 1,a,b,c;i <= p;i++){
        cin>>a>>b>>c;
        add(a,b,c);
        ++ok[bl[b]];
    }
	memset(d,0x7f,sizeof(d));
    memset(vis,0,sizeof(vis));
    d[s] = 0;
    queue<int> Q;
    Q.push(bl[s]);
    for(int i = 1;i <= cnt;i++) if(!ok[i]) Q.push(i);
    priority_queue<node> q;
    while(!Q.empty()){
        int xi = Q.front();
		Q.pop();
        for(auto u : es[xi]) q.push(node{d[u],u});
        while(!q.empty()){
            node now = q.top(); 
			q.pop();
            int u = now.u;
            if(vis[u]) continue;
            vis[u] = 1;
            for(int i = head[u];i != -1;i = ed[i].next){
                int v = ed[i].v;
                if(d[v] > d[u]+ed[i].w) {
                    d[v] = d[u]+ed[i].w;
                    if(bl[v] == bl[u]) q.push(node{d[v],v}) ;
                }
                if(bl[v] != bl[u] && (--ok[bl[v]]) == 0) Q.push(bl[v]);
            }
        }
    }
    for(int i = 1;i <= n;i++){
        if(d[i] > INF) cout<<"NO PATH"<<endl;
        else cout<<d[i]<<endl;
    }
    return 0;
}