Roads and routes -- dfs+topsort+dijkstra+ mapping

Algorithm flow

1. Enter all two-way roads first , then DFS Out all connected blocks , Calculate two arrays :id[] Store which connected block each point belongs to ;vector<int> block[] Store the points in each connected block :
2. Enter all routes , At the same time, the penetration of each connected block is counted .
3. Process each connected block in topological order , First, set all entries to 0 The number of the connected block of is added to the queue
in .
4. Take out the number of one connected block from the head of the team at a time bid
5. Will be block[bid] All points in are added to the heap , Then run for all points in the heap dijkstra Algorithm .
6. Take out the smallest point in the heap every time ver.
7. Then traverse ver All the neighbors of j. If id[ver]==id[], So if j Can be updated , Will j Insert into the heap : If id[ver]!= id[j], Will id[j] The penetration of this connected block decreases 1, If reduced 0 了 , Then insert it into the queue of topology sorting

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int N = 25010,M=150010,INF=0x3f3f3f3f;
typedef pair<int, int> PII;
#define x first
#define y second
int e[M],h[N],ne[M],w[M],idx=0;
int n,mr,mp,s;
int bcnt;
vector<int>block[N];
int id[N];
int din[N];
int dist[N];
bool st[N];
queue<int>q;
void add(int a, int b, int c)
{
    
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs(int u,int bid)
{
    
    id[u]=bid,block[bid].push_back(u);
    for(int i=h[u];i!=-1;i=ne[i])
    {
    
        int j=e[i];
        if(!id[j])
            dfs(j,bid);
    }
}
void dij(int bid)
{
    
    priority_queue<PII,vector<PII>,greater<PII> >heap;
    for(auto u:block[bid])
        heap.push({
    dist[u],u});
    
    while(heap.size())
    {
    
        auto t=heap.top();
        heap.pop();
        int ver=t.y,distance=t.x;
        if(st[ver])continue;
        st[ver]=true;
        for(int i=h[ver];i!=-1;i=ne[i])
        {
    
            int j=e[i];
            if(id[j]!=id[ver]&&--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<=bcnt;i++)
        if(!din[i])
            q.push(i);
    while(q.size())
    {
    
        int t=q.front();
        q.pop();
        dij(t);
    }
}
signed main()
{
    
    memset(h, -1, sizeof h);
    cin>>n>>mr>>mp>>s;
    for(int i=1;i<=mr;i++)
    {
    
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    for(int i=1;i<=n;i++)
        if(!id[i])
        {
    
            bcnt++;
            dfs(i,bcnt);
        }
    for(int i=1;i<=mp;i++)
    {
    
        int a,b,c;
        cin>>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;
}