SDUTOJ 2498 AOE網上的關鍵路徑（最長路）

SDUTOJ 2498 AOE網上的關鍵路徑（最長路）

AOE網上的關鍵路徑

Time Limit: 1000MS Memory limit: 65536K

題目描述

一個無環的有向圖稱為無環圖（Directed Acyclic Graph），簡稱DAG圖。
AOE(Activity On Edge)網：顧名思義，用邊表示活動的網，當然它也是DAG。與AOV不同，活動都表示在了邊上，如下圖所示：

如上所示，共有11項活動（11條邊），9個事件（9個頂點）。整個工程只有一個開始點和一個完成點。即只有一個入度為零的點（源點）和只有一個出度為零的點（匯點）。
關鍵路徑：是從開始點到完成點的最長路徑的長度。路徑的長度是邊上活動耗費的時間。如上圖所示，1 到2 到 5到7到9是關鍵路徑（關鍵路徑不止一條，請輸出字典序最小的），權值的和為18。

輸入

這裡有多組數據，保證不超過10組，保證只有一個源點和匯點。輸入一個頂點數n(2<=n<=10000),邊數m(1<=m <=50000),接下來m行，輸入起點sv，終點ev,權值w（1<=sv,ev<=n,sv != ev,1<=w <=20)。數據保證圖連通。

輸出

關鍵路徑的權值和，並且從源點輸出關鍵路徑上的路徑（如果有多條，請輸出字典序最小的）。

示例輸入

9 11
1 2 6
1 3 4
1 4 5
2 5 1
3 5 1
4 6 2
5 7 9
5 8 7
6 8 4
8 9 4
7 9 2

示例輸出

18
1 2
2 5
5 7
7 9

提示

AOE網上的關鍵路徑其實就是求最長路，只不過多的是要求求得的最長路的通道的組成
頂點，故設立一個num[1000].b來更新連接一個頂點的下一個頂點。最後從源點到匯點
進行遍歷就可求得最長路的組成頂點，只不過這個題要求如果關鍵路徑不止一條要按
字典序輸出，當時想的有點簡單，敲完就交了，結果WA了，不明白為什麼錯，也不知
道應該改哪裡，感謝巖兄一語點醒夢中人，加了一個條件就A了，感謝巖兄！！！淚流
滿面......

來源

示例程序

#include
#include
#include
#include
#include
#include

using namespace std;
const int INF = 0;

struct node
{
    int x,y,z;
}q[1001000];

struct node1
{
    int a,b;
};

int n,m;
int t;
struct node1 num[1100001];

void add(int x,int y,int z)
{
    q[t].x = x;
    q[t].y = y;
    q[t++].z = z;
}

void BF()
{
    for(int i=0;i<=n;i++)
    {
        num[i].a = INF;
        num[i].b = -1;
    }
    num[n].a = 0;
    int flag = 0;
    for(int i=1;i