【H ECJTU_ACM 11级队员2012年暑假训练赛（2）】

H - H

Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u

Description

在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？

Input

输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。
输入保证至少存在1条商店到赛场的路线。

Output

对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间

Sample Input

2 1 1 2 3 3 3 1 2 5 2 3 5 3 1 2 0 0

Sample Output

3 2

 1 // Project name : H
 2 // File name    : main.cpp
 3 // Author       : Izumu
 4 // Date & Time  : Tue Jul 10 13:30:13 2012
 5 
 6 #include<stdio.h>
 7 #include<string.h>
 8 
 9 #define Max 1000001
10 
11 
12 
13 
14 
15 int main()
16 {
17     int n, m, a, b, c, i, j, min;
18     int map[102][102];
19     int dist[102];
20     int v;
21     int flag[102];
22     while(scanf("%d %d", &n, &m) !=EOF && n + m)
23     {
24        memset(flag, 0, sizeof(flag));
25        for (i = 1; i <= n; i++)
26         for (j = 1; j <= n; j++)
27          map[i][j]=Max;
28        
29        for(i = 1; i <= m; i++)
30        {
31         scanf("%d %d %d",&a,&b,&c);
32         map[a][b]=c;
33         map[b][a]=c;
34         flag[a]=flag[b]=1;
35        }
36        flag[1]=0;
37        for(i=1;i<=n;i++)
38         dist[i]=map[1][i];
39        for(i=1;i<n;i++)//要找n-1次
40        {
41         min=Max;
42         for(j=1;j<=n;j++)
43         {
44          if(flag[j]==1 && min>dist[j])
45          {
46           v=j;
47           min=dist[j];
48          }
49         }
50         flag[v]=0;
51         for(j=1;j<=n;j++)
52         {
53          if(flag[j]==1 && map[v][j]+dist[v]<dist[j])
54           dist[j]=map[v][j]+dist[v];
55         }
56        
57        }
58        printf("%d\n",dist[n]);
59     }
60     return 0;
61 }
62 
63 
64 // end 
65 // ism