莫欺少年穷，修魔之旅在这开始—>算法提高课题解

DFS + 拓扑排序 + Dijkstra 的综合应用

综合性极强，这种题很适合训练

思路：

1. 先用 dfs 把所有点分成连通块，目的是为了计算连通块内部的最短路
2. 把连通块看成点按拓扑序入队列，这样子就可以确定这个连通块没法让其他入度不为 0 的连通块更新
3. 把这个连通块中的所有点全部入堆，用 Dijkstra 计算连通块内部所有点的最短路
4. 更新时，如果两个点在同一个连通块就直接入堆，否则让那个点所在的连通块入度 --

#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;

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

int n,m1,m2,S;
int h[N],e[M],w[M],ne[M],idx;
int id[N],cnt;
int dist[N],din[N];
bool st[N];
vector<int> block[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 cnt)
{
    id[u]=cnt;
    block[cnt].push_back(u);
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(!id[j]) dfs(j,cnt);
    }
}

//用堆优化版 Dijkstra 把这个连通块里面的所有点都更新为最短路
void dijkstra(int x)
{
    priority_queue<PII,vector<PII>,greater<PII>> heap;

    for(auto u:block[x]) heap.push({dist[u],u});

    while(heap.size())
    {
        auto t=heap.top();
        heap.pop();

        int ver=t.second,distance=t.first;
        if(st[ver]) continue;
        st[ver]=true;

        for(int i=h[ver];~i;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>distance+w[i])
            {
                dist[j]=distance+w[i];

                //如果两个点在同一个连通块就放入堆
                if(id[ver]==id[j]) heap.push({dist[j],j});
            }

            //两个点不在同一个连通块
            if(id[ver]!=id[j]&&--din[id[j]]==0) q.push(id[j]);
        }
    }
}

//按拓扑序一个个遍历可以保证该连通块无法让其他还没入队的连通块更新
void topsrt()
{
    memset(dist,0x3f,sizeof dist);
    dist[S]=0;

    //把所有入度为 0 的连通块入队
    for(int i=1;i<=cnt;i++)
        if(!din[i]) 
            q.push(i);

    while(q.size())
    {
        auto t=q.front();
        q.pop();
        dijkstra(t);
    }
}

int main()
{
    cin>>n>>m1>>m2>>S;

    memset(h,-1,sizeof h);

    //输入道路
    while(m1--)
    {
        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])
            dfs(i,++cnt);

    //输入航线并确定每个连通块的入度
    while(m2--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        din[id[b]]++;
    }

    //把连通块看成点做拓扑排序
    topsrt();

    for(int i=1;i<=n;i++) 
        if(dist[i]>=INF/2) cout<<"NO PATH"<<endl;
        else cout<<dist[i]<<endl;

    return 0;
}