一道dijkstar最短路，但是因为题目保证如果有一条航线可以从 Aᵢ 到 Bᵢ，保证不可能通过一些道路和航线从 Bᵢ 回到 Aᵢ。那么需要拓扑序来处理航线。

#include<bits/stdc++.h>

using namespace std;

const int N = 25011, M = (5e4+11) * 3;

int color = 0;
int n,m,mm,s;
int head[N], tot = 0;
int edge[M], ver[M], nex[M];
int d[N];
int c[N] = {0}; 
int v[N] = {0};
int din[N] = {0};
int colo[N] = {0};

queue<int> q;
vector<int> id[N];

void add(int x, int y, int z){
	ver[++tot] = y;
	edge[tot] = z;
	nex[tot] = head[x];
	head[x] = tot;
}

void dfs(int t, int sum){
	c[t] = color;
	id[color].push_back(t);
	for(int i=head[t]; i; i=nex[i]){
		int y = ver[i];
		if(!c[y])dfs(y, sum);
	}
}

void dija(int k){


	priority_queue<pair<int, int>> dijaq;
	for(int i=0;i<id[k].size();i++)
		dijaq.push(make_pair(-d[id[k][i]], id[k][i]));

	while(dijaq.size()){
		int x = dijaq.top().second; dijaq.pop();
		if(v[x]) continue; v[x] = 1;
		
		for(int i=head[x]; i; i=nex[i]){
			int y = ver[i], z = edge[i];
			
			if(c[y] != c[x] && --din[c[y]] == 0) q.push(c[y]);
		
			if(d[y] > d[x] + z){
				d[y] = d[x] + z;
				if(c[y] == c[x]) dijaq.push(make_pair(-d[y], y));
//				注意此处，，如果不是同一个连通块的，
//				就不要在本次dija内走 ,,
//				需要在topsort中到这个连通块的时候在走他的dija 
			}
		}
	}
}

void topsort(){
	memset(d, 0x3f, sizeof d);
	d[s] = 0;
	
	for(int i=1;i<=color;i++)
		if(!din[i]) q.push(i);
	
	while(q.size()){
		int x = q.front(); q.pop();
		dija(x);
	}
}

int main(){
	int x, y, z;
	cin>>n>>m>>mm>>s;
	for(int i=0;i<m;i++){
		cin>>x>>y>>z;
		add(x, y, z); add(y, x, z);
	}
	
	for(int i=1;i<=n;i++) if(!c[i])dfs(i, ++ color);
	
	for(int i=0;i<mm;i++){
        cin>>x>>y>>z;		
		add(x, y, z);
		din[c[y]] ++;
	}
	
	topsort();

	for(int i=1;i<=n;i++)
	if(d[i] >= 0x3f3f3f3f / 2) printf("NO PATH\n");
	else printf("%d\n",d[i]);
	return 0;
}