1067.txt

厦门大学OJ上的ACM题1067源码

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

Description
　　通过天蝎宫的星矢一行人来到射手宫前。
　　射手宫的主人是13年前为了保护还是女孩的雅典娜而被教皇派人杀害的艾俄洛斯。所以此时的射手宫是无人看守的。射手座是一个巨大迷宫，幸运的是星矢他们事先已经得到了这个迷宫的地图。这个迷宫有n个小岛组成，部分小岛之间存在一个双向的传送门，每个传送门都有一个最大传送能力，传送能力越强的传送门一次传送的东西也就越多。为了防止后面的追兵，他们每次离开一个小岛后就会将这个小岛关闭起来。另外本着“不抛弃不放弃”的精神，他们一行人必须统一行动。
　　刚开始星矢他们在起点的位置。在起点处，他们发现了很多很多可以在战斗中补充小宇宙的药草。为了方便后面的战斗，星矢他们决定带上尽可能多的这种药草。但是传送门的传送能力有限，星矢他们应该如何移动才能够带尽可能多的药草。图中，1->2->4->7和1->2->4->5->7，这两条路径最大的传送能力都是6，任意选择其中一条都可以满足要求。



Input
　　第一行为两个正整数n, m(2 <= n <= 100,000, 0 < m <= 200,000)，表示迷宫中岛屿数目和传送门的数目。岛屿编号为1到n，1是起点，n是终点。
　　接下来m行每行三个正整数f , t , v表示岛屿f和岛屿t之间有一道传送门相连，传送能力为v(0 < v <= 100,000)，保证没有两个传送门连接了相同的两岛屿。



Output
　　输出星矢他们的行动路径，即他们路过的岛屿编号，用空格隔开。如果存在多条路径，您可以输出任意一条。如果不存在这样的路径，输出一个-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;   
}