题目描述


C++ 代码

#include<cstring>
#include<algorithm>
#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#define x first
#define y second
using namespace std;

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

typedef pair<int,int> PII;

int h[N],e[M],ne[M],w[M],idx;
int n,mr,mp,S;
int id[N];
int bcnt;
vector<int> block[N];
int dist[N];
bool st[N];
int din[N];
queue<int> q;
                                    //本题会卡掉SPFA。
                                    //对于边权为正的道路，用堆优化Dijstra可以解决。
                                    //航道之间无环，所以，把仅有道路组成的图看作一个一个团。
                                    //整个图就可以看作由若干个团组成的拓扑图，可以用拓扑序来扫描得到最小值。
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;i=ne[i])
    {
        int j=e[i];
        if(!id[j])
        {
            dfs(j,bid);
        }
    }
}

void dijkstra(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; 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();
        dijkstra(t);
    }
}

int main()
{
    memset(h,-1,sizeof h);

    scanf("%d%d%d%d",&n,&mr,&mp,&S);

    for(int i=0;i<mr;i++)
    {
        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])
        {
            dfs(i,++bcnt);
        }
    }

    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)
        {
            puts("NO PATH");
        }
        else printf("%d\n",dist[i]);

    return 0;
}