道路與航線（dijkstra和拓撲排序綜合應用）

農夫約翰正在一個新的銷售區域對他的牛奶銷售方案進行調查。

他想把牛奶送到 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 回到 Ai。

由于約翰的奶牛世界公認十分給力，他需要運送奶牛到每一個城鎮。

他想找到從發送中心城鎮 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
           

在已知spfa逾時的情況下我們要怎麼做？

分析題意可知，所有雙向道路連接配接的點必然不可能有航線連接配接，航線也必然不可能形成環

 那麼我們把在一個連通塊中的點看做是一個集合，航線把這些集合串起來會形成一個拓撲圖，也就是有向無環圖

在這種“無法走回頭路”的路線中我們隻要從頭開始周遊就確定可以把所有路線都給周遊到，把所有點也給更新到

具體流程就是先讀入雙向邊，然後把相連的點通過dfs裝到同一個集合中，并且記錄哪些點屬于哪些集合，哪些集合裡有哪些點

然後讀入單向邊，也就是航線，在記錄兩點的同時也要記錄哪個點的入度增加了

之後寫拓撲排序函數，集合标号從小到大周遊，若入度為0就要入隊

之後就是單獨處理隊頭了，每次都要用dijkstra處理一個隊頭，傳給dijkstra的參數是集合标号

dijkstra函數每次都把同一個集合的所有元素push進小根堆中，然後就是做堆優化的dijkstra，但是要注意的是若是搜到了航線就要把目标點的入度減1，同時若是入度減為0就要插入拓撲排序的隊列中

之後判斷，隻有是同一個集合中的點并且被更新過距離才能重新push進小根堆中

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 25010, M = 150010, INF = 0x3f3f3f3f;
int n, mr, mp, S;
int id[N];                                   //id存的是哪個點屬于哪個集合 
int h[N], e[M], w[M], ne[M], idx;
int dist[N], din[N];
vector<int> block[N];
int bcnt;
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; 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]);   //隻要是有一條航線，那麼入度就要減一,但是特别要注意的是隻有不同于集合中的元素才能往q中插入 
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];                              //即使是用dijkstra不能求負權圖，更新一條邊總是可以的吧 
				if (id[j] == id[ver]) heap.push({dist[j], j});
            }
        }
    }
}

void topsort()
{
    memset(dist, 0x3f, sizeof dist);                //把雙向路和航線初始化完畢之後就用拓撲排序去做了 
    dist[S] = 0;                                    //把開始點初始化為0 

    for (int i = 1; i <= bcnt; i ++ )
    if(!din[i]) q.push(i);                          //剛開始把入度為0的連通塊整體加入隊列中 

    while (q.size())                                //然後對每個連通塊内的點做dijkstra 
    {
        int t = q.front();                          //剛開始就隻有一組入度為0的點，但是後面的dijkstra函數運作的時候又會把入度為0的點集又給push進來 
        q.pop();
        dijkstra(t);
    }
}

int main()
{
    cin >> n >> mr >> mp >> S;
    memset(h, -1, sizeof h);

    while (mr -- )
    {
        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);
        }
        
    while (mp -- )                           //然後加入航線(單向) 
    {
        int a, b, c;
        cin >> a >> b >> c;
        din[id[b]] ++ ;
        add(a, b, c);
    }
    
    topsort();
    
    for (int i = 1; i <= n; i ++ )
    if (dist[i] > INF / 2) cout << "NO PATH" << endl;
    else cout << dist[i] << endl;
    return 0;
}
           

要加油啊！！