警示后人，一个奇怪的地方

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=50005,INF=1e17;
ll n,R,S,P,sum,vis[maxn],deg[maxn],dis[maxn];
bool vit[maxn];
struct edge{
	ll v,w;
	friend bool operator < (edge x,edge y){
		return x.w>y.w;
	}
};
vector <edge> node[maxn];
vector <ll> c[maxn];
queue <ll> q;
void dfs(ll u){
	c[sum].push_back(u);
	vis[u]=sum;
	for(auto [v,w]:node[u]){
		if(vis[v]) continue;
		dfs(v);
	}
}
int main(){
	cin>>n>>R>>P>>S;
	for(int i=1;i<=R;i++){
		ll u,v,w;
		cin>>u>>v>>w;
		node[u].push_back({v,w});
		node[v].push_back({u,w});
	}
	for(int i=1;i<=n;i++){
		if(vis[i]) continue;
		sum++;
		dfs(i);
	}
	for(int i=1;i<=P;i++){
		ll u,v,w;
		cin>>u>>v>>w;
		deg[vis[v]]++;
		node[u].push_back({v,w});
	}
	q.push(vis[S]);//直接入队
	for(int i=1;i<=sum;i++)
		if(deg[i]==0&&i!=vis[S])
			q.push(i);
	for(int i=1;i<=n;i++) dis[i]=INF;
	dis[S]=0;
	while(!q.empty()){
		ll x=q.front();
		q.pop();
		priority_queue <edge> pq;
		for(auto u:c[x])
			pq.push({u,dis[u]});
		memset(vit,0,sizeof(vit));
		while(!pq.empty()){
			auto [u,d]=pq.top();
			pq.pop();
			if(vit[u]) continue;
			vit[u]=1;
			for(auto [v,w]:node[u]){
				if(dis[v]>dis[u]+w){
					dis[v]=dis[u]+w;
					if(vis[u]==vis[v]) 
						pq.push({v,dis[v]});
				}
				if(vis[u]!=vis[v]){
					deg[vis[v]]--;
					if(deg[vis[v]]==0)
						q.push(vis[v]);
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(dis[i]>INF/2)
			cout<<"NO PATH"<<endl;
		else 
			cout<<dis[i]<<endl;
	}
	return 0;
}

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=50005,INF=1e17;
ll n,R,S,P,sum,vis[maxn],deg[maxn],dis[maxn];
bool vit[maxn];
struct edge{
	ll v,w;
	friend bool operator < (edge x,edge y){
		return x.w>y.w;
	}
};
vector <edge> node[maxn];
vector <ll> c[maxn];
queue <ll> q;
void dfs(ll u){
	c[sum].push_back(u);
	vis[u]=sum;
	for(auto [v,w]:node[u]){
		if(vis[v]) continue;
		dfs(v);
	}
}
int main(){
	cin>>n>>R>>P>>S;
	for(int i=1;i<=R;i++){
		ll u,v,w;
		cin>>u>>v>>w;
		node[u].push_back({v,w});
		node[v].push_back({u,w});
	}
	for(int i=1;i<=n;i++){
		if(vis[i]) continue;
		sum++;
		dfs(i);
	}
	for(int i=1;i<=P;i++){
		ll u,v,w;
		cin>>u>>v>>w;
		deg[vis[v]]++;
		node[u].push_back({v,w});
	}
	for(int i=1;i<=sum;i++)
		if(deg[i]==0)//入队度为0的点
			q.push(i);
	for(int i=1;i<=n;i++) dis[i]=INF;
	dis[S]=0;
	while(!q.empty()){
		ll x=q.front();
		q.pop();
		priority_queue <edge> pq;
		for(auto u:c[x])
			pq.push({u,dis[u]});
		memset(vit,0,sizeof(vit));
		while(!pq.empty()){
			auto [u,d]=pq.top();
			pq.pop();
			if(vit[u]) continue;
			vit[u]=1;
			for(auto [v,w]:node[u]){
				if(dis[v]>dis[u]+w){
					dis[v]=dis[u]+w;
					if(vis[u]==vis[v]) 
						pq.push({v,dis[v]});
				}
				if(vis[u]!=vis[v]){
					deg[vis[v]]--;
					if(deg[vis[v]]==0)
						q.push(vis[v]);
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(dis[i]>INF/2)
			cout<<"NO PATH"<<endl;
		else 
			cout<<dis[i]<<endl;
	}
	return 0;
}

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N = 50005, M = 100005;
int n, r, p, s;
struct Edge{
    int v, next, w;
}e[M << 1];
struct node{
    int d, u;
    bool operator < (const node &A) const {
        return d > A.d;
    }
};
int head[N], tot;
void adde(int u, int v, int w) {
    e[tot].v = v; e[tot].w = w; e[tot].next = head[u]; head[u] = tot++;
}
bool vis[N] ;
int cnt;
int bl[N], in[N];
int d[N] ;
vector <int> block[N];
void dfs(int u) {
    vis[u] = 1;
    bl[u] = cnt;
    block[cnt].push_back(u) ;
    for(int i = head[u]; i != -1; i = e[i].next) {
        int v = e[i].v;
        if(vis[v]) continue ;
        dfs(v) ;
    }
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> r >> p >> s;
    memset(head, -1, sizeof(head)) ;
    for(int i = 1; i <= r; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        adde(a, b, c);
        adde(b, a, c);
    }
    for(int i = 1; i <= n; i++) {
        if(!vis[i]) {
            cnt++;
            dfs(i) ;
        }
    }
    for(int i = 1; i <= p; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        adde(a, b, c) ;
        in[bl[b]]++;
    }
    memset(vis, 0, sizeof(vis)) ;
    memset(d, 0x7f, sizeof(d)) ;
    d[s] = 0;
    queue <int> Q;
    Q.push(bl[s]) ;
    for(int i = 1; i <= cnt; i++) if(!in[i]) Q.push(i) ;
    priority_queue <node> q;
    while(!Q.empty()) {
        int blo = Q.front();Q.pop() ;
        for(auto u : block[blo])
            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 = e[i].next) {
                int v = e[i].v;
                if(d[v] > d[u] + e[i].w) {
                    d[v] = d[u] + e[i].w;
                    if(bl[v] == bl[u]) q.push(node{d[v],v}) ;
                }
                if(bl[v] != bl[u] && (--in[bl[v]]) == 0) Q.push(bl[v]) ;
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        if(d[i] > INF) cout << "NO PATH" << '\n' ;
        else cout << d[i] << '\n' ;
    }
    return 0;
}