RT.奇葩并查集做法（马风丑陋见谅）

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
    int Next,to,w;
}e[200010];
int head[100010],cnt,ks[100010],rks[100010],ru[100010],dis[100010];
bool vis[100010];
map<int,int>ma;
vector<int>v[100010];
void add(int x,int y,int z){
    e[++cnt]=(node){head[x],y,z};
    head[x]=cnt;
}
int fa[100010];
int find(int x){
    if(x==fa[x]){
        return x;
    }
    return fa[x]=find(fa[x]);
}
void build(int x,int y){
    int fx=find(x),fy=find(y);
    if(fx==fy){
        return;
    }
    fa[fx]=fy;
}

signed main(){
    int n,m,k,s;
    cin>>n>>m>>k>>s;
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
        add(y,x,z);
        build(x,y);
    }
    for(int i=1;i<=n;i++){
        ks[i]=find(i);
    }
    sort(ks+1,ks+n+1);
    int tot=0;
    for(int i=1;i<=n;i++){
        if(ks[i]!=ks[i-1]){
            rks[i]=++tot;
            ma[ks[i]]=tot;
            v[tot].push_back(i);
        }
        else{
            rks[i]=ma[ks[i]];
            v[ma[ks[i]]].push_back(i);
        }
    }
    for(int i=1;i<=k;i++){
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
        ru[rks[y]]++;
    }
    for(int i=1;i<=n;i++){
        dis[i]=INT_MAX;
    }
    dis[s]=0;
    queue<int>q;
    q.push(rks[s]);
    for(int i=1;i<=tot;i++){
        if(ru[i]==0){
            q.push(i);
        }
    }
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >qq;
    while(q.size()){
        int t=q.front();
        q.pop();
        for(auto i:v[t]){
            qq.push(make_pair(dis[i],i));
        }
        while(qq.size()){
            int u=qq.top().second;
            qq.pop();
            if(vis[u]){
                continue;
            }
            vis[u]=1;
            for(int i=head[u];i;i=e[i].Next){
                int y=e[i].to;
                if(dis[y]>dis[u]+e[i].w){
                    dis[y]=dis[u]+e[i].w;
                    if(rks[y]==rks[u]){
                        qq.push(make_pair(dis[y],y));
                    }
                }
                if(rks[y]!=rks[u]){
                    ru[rks[y]]--;
                    if(!ru[rks[y]]){
                        q.push(rks[y]);
                    }
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(dis[i]==INT_MAX){
            cout<<"NO PATH"<<endl;
            continue;
        }
        cout<<dis[i]<<endl;
    }
	return 0;
}