AcWing 342. Road and route problem solving (shortest path, topological sorting)

AcWing 342. Roads and routes
y It's always a problem , exactly , It's more useful than writing ten simple questions . A problem with a large amount of code , But I learned a lot , From roads to topological sorting , Using the topological sorting, we can know that each point will only be visited once , This is also a way to find the shortest way , So run in the Unicom block first jk shortest path , Then topological sorting of all connected blocks , You can find the shortest path of the whole diagram

#include<bits/stdc++.h>

using namespace std;

#define x first
#define y second

typedef pair<int, int>PII;

const int N = 25010, M = 150010, INF = 0x3f3f3f3f;

int h[N], ne[M], e[M], w[M], idx;
vector<int> block[N];  // Store connecting blocks  
queue<int> q;  // Store the number of the connected block , Used for topological sorting 
int n, mp, mr, S;
int id[N];  // Record which connected block each point is in 
int din[N];  // Record the penetration of each connected block  
int cnt;  // Record the number of connecting blocks  
int dist[N];
bool st[N];

void add(int a, int b, int c){
    
	e[idx] = b;
	w[idx] = c;
	ne[idx] = h[a];
	h[a] = idx ++ ;
}

void dijkstra(int u){
      //u Is the connected block number , Run in the connected block jk shortest path  
	
	priority_queue<PII, vector<PII>, greater<PII>>heap;
	
	for(auto op : block[u]){
    
		heap.push({
    dist[op], op});
	} 
	
	while(heap.size()){
    
		auto op = heap.top();
		heap.pop();
		
		int ver = op.y;
		int dis = op.x;
		
		if(st[ver]) continue;
		st[ver] = true;
		
		for(int i = h[ver]; ~i; i = ne[i]){
    
			int j = e[i];
			if(id[ver] != id[j] && -- din[id[j]] == 0) q.push(id[j]);
			if(dist[j] > dist[ver] + w[i]){
    
				dist[j] = dist[ver] + w[i];
				if(id[j] == id[ver]) heap.push({
    dist[j], j});
			}
		}
	}
}

void topsort(){
    
	memset(dist, 0x3f, sizeof dist);
	dist[S] = 0;
	for(int i = 1; i <= cnt; i ++ ){
    
		if(!din[i]) q.push(i);  // The degree of engagement is 0 Connected blocks of join the team , Topological sort  
 	}
 	
 	while(q.size()){
    
		int op = q.front();
		q.pop();
		
		dijkstra(op);  // The degree of 0 Running within the connected block of dijkstra 
	}
}

void dfs(int u, int bid){
    
	id[u] = bid;
	block[bid].push_back(u);
	
	for(int i = h[u]; ~i; i = ne[i]){
    
		int j = e[i];
		if(!id[j]) dfs(j, bid);
	}
} 

int main()
{
    
	cin>>n>>mr>>mp>>S;
	memset(h, -1, sizeof h);
	while(mr -- ){
    
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		add(a, b, c);
		add(b, a, c);
	}
	
	
	for(int i = 1; i <= n; i ++ ){
    
		if(!id[i]){
    
			cnt ++ ;
			dfs(i, cnt);
		}
	}
	
	while(mp -- ){
    
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		
		add(a, b, c);
		din[id[b]] ++ ;
	}
	
	topsort();
	
	for(int i = 1; i <= n; i ++ ){
    
		if(dist[i] > INF / 2) cout<<"NO PATH"<<endl;
		else cout<<dist[i]<<endl;
	}
	return 0;
}