HDOJ2544 ( 最短路 ) 【最短路径Dijkstra】

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 #define MAX 0x3f3f3f3f
 5 #define N 105
 6 int cls[N],n,m;
 7 int map[N][N];
 8 int vis[N];
 9 void Dijkstra(int v)
10 {
11     int i,j,min,nxt;
12     for(i=1;i<=n;i++)    cls[i]=map[v][i];
13     memset(vis,0,sizeof(vis));
14     vis[v]=1;
15     for (i=1;i<n;i++)
16     {
17         min=MAX;
18         nxt=v;
19         for (j=1;j<=n;j++)
20         {
21             if(!vis[j]&&cls[j]<min)
22             {
23                 nxt=j;
24                 min=cls[j];
25             }
26         }
27         vis[nxt]=1;
28         for (j=1;j<=n;j++)
29         {
30             if(!vis[j]&&map[nxt][j]<MAX&&(min+map[nxt][j])<cls[j])
31                 cls[j]=cls[nxt]+map[nxt][j];
32         }
33     }
34 }
35 int main()
36 {
37     int a,b,c;
38     while(scanf("%d%d",&n,&m),m||n)
39     {
40         memset(map,MAX,sizeof(map));
41         while (m--)
42         {
43             scanf("%d%d%d",&a,&b,&c);
44             if(map[a][b]>c)    map[a][b]=map[b][a]=c;
45         }
46         Dijkstra(1);
47         printf("%d\n",cls[n]);
48     }
49     return 0;
50 }