题目描述

农夫约翰正在一个新的销售区域对他的牛奶销售方案进行调查。

他想把牛奶送到T个城镇，编号为1~T。

这些城镇之间通过R条道路 (编号为1到R) 和P条航线 (编号为1到P) 连接。

每条道路 i
或者航线 i 连接城镇Ai到Bi，花费为Ci。

对于道路，0≤Ci≤10,000;然而航线的花费很神奇，花费Ci可能是负数(−10,000≤Ci≤10,000)。

道路是双向的，可以从Ai到Bi，也可以从Bi到Ai，花费都是Ci。

然而航线与之不同，只可以从Ai到Bi。

事实上，由于最近恐怖主义太嚣张，为了社会和谐，出台了一些政策：保证如果有一条航线可以从Ai到Bi，那么保证不可能通过一些道路和航线从Bi回到A。

由于约翰的奶牛世界公认十分给力，他需要运送奶牛到每一个城镇。

他想找到从发送中心城镇S把奶牛送到每个城镇的最便宜的方案。
输入格式

第一行包含四个整数T,R,P,S。

接下来R行，每行包含三个整数（表示一个道路）Ai,Bi,Ci。

接下来P行，每行包含三个整数（表示一条航线）Ai,Bi,Ci。

输出格式

第1..T行：第i行输出从S到达城镇i的最小花费，如果不存在，则输出“NO PATH”。
数据范围

1≤T≤25000,
1≤R,P≤50000,
1≤Ai,Bi,S≤T,

样例

输入样例：

6 3 3 4
1 2 5
3 4 5
5 6 10
3 5 -100
4 6 -100
1 3 -10

输出样例：

NO PATH
NO PATH
5
0
-95
-100

Dijstra+topu

每条道路是双向的，但是航路是单向的；并且航路连接的两点指向明确，无法返回，那么说明道路把这些城镇分为了若干个连通块，并且航线是在这些连通块之间通行而不可能是在连通块内，否则就会使航路连接的两点可以互相到达，与题意矛盾。

所以第一步就要先得到所有的连通块

而所有的航道指向明确且没有环(从A到B，但不可以从B到A)，那么满足拓扑

所以第二步就是按照拓扑序在一个一个的连通块中进行Dijstra运算

对步骤进行细分就是：(自己打了一遍没保存，这里放上课截图)

时间复杂度mlogn

C++ 代码

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

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

typedef pair<int,int> PII;

int T,R,P,S;//T个城镇，R条道路，P条航路，中心城镇S
int h[N],e[M],ne[M],w[M],idx;
int id[N];//记录每一个城镇属于哪个联通块
int st[N];
vector<int>block[N];//记录每一个连通块有哪些点
int bcnt;//有多少个连通块
int ind[N];//记录每个连通块的入度
queue<int>q;//拓扑序入队
int dist[N];

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){//当前是第u个城镇，在第cnt个连通块
    st[u]=1;
    id[u]=cnt;
    block[cnt].push_back(u);
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(st[j])   continue;
        dfs(j,cnt);
    }
}
void Dijstra(int u){//对第u个连通块进行最短路计算
    priority_queue<PII,vector<PII>,greater<PII>>heap;
    // heap.push({dist[block[u][0]],block[u][0]});

    //这里一定要把所有的边都加进去，因为在Dijstra中只会把更新过的在同一个连通块中的点加到堆中
    //而若是某个点在这一循环没被更新，那么就不会进入循环，那么就会有某些块的入度无法减到0，所有会有连通块不被遍历

    for(int i=0;i<block[u].size();i++)
        heap.push({dist[block[u][i]],block[u][i]});
    while(heap.size()){
        PII t=heap.top();
        heap.pop();
        int ver=t.y;
        int d=t.x;
        if(st[ver]) continue;
        st[ver]=1;
        for(int i=h[ver];~i;i=ne[i]){
            int j=e[i];
            if(id[j]!=id[ver]&&--ind[id[j]]==0)    q.push(id[j]);//只要不是本连通块的点并且减一后入度为0，就放入拓扑序
            if(dist[j]>dist[ver]+w[i]){
                dist[j]=dist[ver]+w[i];
                if(id[j]==id[ver])  heap.push({dist[j],j});
            }
        }
    }
}
void topu(){
    memset(dist,0x3f,sizeof dist);
    memset(st,0,sizeof st);
    dist[S]=0;
    while(q.size()){
        int t=q.front();
        q.pop();
        Dijstra(t);
    }
}
int main(){
    cin>>T>>R>>P>>S;
    memset(h,-1,sizeof h);
    for(int i=0;i<R;i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }
    for(int i=1;i<=T;i++){
        if(!st[i])  dfs(i,++bcnt);
    }
    for(int i=0;i<P;i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        ind[id[b]]++;
    }
    for(int i=1;i<=bcnt;i++){
        if(!ind[i])
            q.push(i);
    }
    topu();
    for(int i=1;i<=T;i++){
        if(dist[i]>INF/2)   cout<<"NO PATH"<<endl;
        else    cout<<dist[i]<<endl;
    }
    return 0;
}