1067.圣斗士黃金十二宮（三）射手宮的迷宮
Time Limit: 3000 MS         Memory Limit: 65536 K 
Total Submissions: 334 (43 users)         Accepted: 87 (33 users) 
[ My Solution ] 

Description
　　通過天蝎宮的星矢一行人來到射手宮前。
　　射手宮的主人是13年前為了保護(hù)還是女孩的雅典娜而被教皇派人殺害的艾俄洛斯。所以此時(shí)的射手宮是無人看守的。射手座是一個(gè)巨大迷宮，幸運(yùn)的是星矢他們事先已經(jīng)得到了這個(gè)迷宮的地圖。這個(gè)迷宮有n個(gè)小島組成，部分小島之間存在一個(gè)雙向的傳送門，每個(gè)傳送門都有一個(gè)最大傳送能力，傳送能力越強(qiáng)的傳送門一次傳送的東西也就越多。為了防止后面的追兵，他們每次離開一個(gè)小島后就會(huì)將這個(gè)小島關(guān)閉起來。另外本著“不拋棄不放棄”的精神，他們一行人必須統(tǒng)一行動(dòng)。
　　剛開始星矢他們?cè)谄瘘c(diǎn)的位置。在起點(diǎn)處，他們發(fā)現(xiàn)了很多很多可以在戰(zhàn)斗中補(bǔ)充小宇宙的藥草。為了方便后面的戰(zhàn)斗，星矢他們決定帶上盡可能多的這種藥草。但是傳送門的傳送能力有限，星矢他們應(yīng)該如何移動(dòng)才能夠帶盡可能多的藥草。圖中，1->2->4->7和1->2->4->5->7，這兩條路徑最大的傳送能力都是6，任意選擇其中一條都可以滿足要求。



Input
　　第一行為兩個(gè)正整數(shù)n, m(2 <= n <= 100,000, 0 < m <= 200,000)，表示迷宮中島嶼數(shù)目和傳送門的數(shù)目。島嶼編號(hào)為1到n，1是起點(diǎn)，n是終點(diǎn)。
　　接下來m行每行三個(gè)正整數(shù)f , t , v表示島嶼f和島嶼t之間有一道傳送門相連，傳送能力為v(0 < v <= 100,000)，保證沒有兩個(gè)傳送門連接了相同的兩島嶼。



Output
　　輸出星矢他們的行動(dòng)路徑，即他們路過的島嶼編號(hào)，用空格隔開。如果存在多條路徑，您可以輸出任意一條。如果不存在這樣的路徑，輸出一個(gè)-1。



Sample Input
7 9
1 2 10
1 3 1
3 4 4
2 4 6
2 6 12
6 7 3
5 7 8
4 5 9
4 7 9



Sample Output
1 2 4 7





RunId 28225 of Problem 1067
Submit Time: 2008-10-26 17:04:41    Language: G++    Code Length: 1478 B 
    Result: Accepted    Time: 1528 MS    Memory: 9124 K    Judge: Apple




#include <stdio.h>   
#include <stdlib.h>   
#include <queue>   
using namespace std;   
typedef struct arcnode{   
    long adjvex;   
    struct arcnode *nextarc;   
    long info;   
}arcnode;   
typedef struct{   
    arcnode *vertices[100001];   
    long vexnum, arcnum;   
}algraph;   
void print(long* p, long n)   
{   
    if (n == 1)   
        printf("%ld ", n);   
    else{   
        print(p, p[n]);   
        printf("%ld ", n);   
    }   
}   
long d[100001]={0};   
bool record[100001]={0};   
long way[100001]={0};   
int main()   
{   
    algraph graph;   
    scanf("%ld %ld", &graph.vexnum, &graph.arcnum);   
    for (long s=1; s<=graph.vexnum; s++)   
        graph.vertices[s] = NULL;   
    for (long t=1; t<=graph.arcnum; t++){   
        arcnode *p = (arcnode*)malloc(sizeof(arcnode));   
        long vex;   
        scanf("%ld %ld %ld", &vex, &p->adjvex, &p->info);   
        p->nextarc = graph.vertices[vex];   
        graph.vertices[vex] = p;   
        arcnode *r = (arcnode*)malloc(sizeof(arcnode));   
        r->adjvex = vex;   
        r->info = p->info;   
        r->nextarc = graph.vertices[p->adjvex];   
        graph.vertices[p->adjvex] = r;   
    }   
    queue<long> q;   
    q.push(1);   
    record[1] = 1;   
    d[1] = 100000;   
    while (!q.empty()){   
        long i = q.front();   
        for (arcnode* p=graph.vertices[i]; p!=NULL; p=p->nextarc){   
            long temp = d[i]>p->info?p->info:d[i];   
            if (d[p->adjvex] < temp){   
                if (record[p->adjvex] != 1)   
                    q.push(p->adjvex);   
                d[p->adjvex] = temp;   
                way[p->adjvex] = i;   
            }   
        }   
        q.pop();   
    }   
    if (way[graph.vexnum] == 0)   
        printf("-1");   
    else  
        print(way, graph.vexnum);   
    return 0;   
}