hdu2544最短路(dijkstra)

dijkstra
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int INF=0x3f3f3f3f;
 4 const int maxn=1200;
 5 
 6 int dist[maxn],g[maxn][maxn],N;
 7 bool vis[maxn];
 8 
 9 void dijkstra()
10 {
11     for(int i=1;i<=N;i++)
12         dist[i]=(i==1)?0:INF;
13     memset(vis,0,sizeof(vis));
14 
15     for(int i=1;i<=N;i++)
16     {
17         int mark=-1,mindis=INF;
18         for(int j=1;j<=N;j++)
19         {
20             if(!vis[j]&&dist[j]<mindis)
21             {
22                 mindis=dist[j];
23                 mark=j;
24             }
25         }
26         vis[mark]=1;
27         for(int j=1;j<=N;j++)
28         {
29             if(!vis[j])
30             {
31                 dist[j]=min(dist[j],dist[mark]+g[mark][j]);
32             }
33         }
34     }
35 }
36 void init()
37 {
38     for(int i=0;i<1200;i++)
39     {
40         for(int j=0;j<1200;j++)
41         {
42             if(i==j)g[i][j]=0;
43             else g[i][j]=INF;
44         }
45     }
46  } 
47 int main()
48 {
49     int M;
50     while(~scanf("%d %d",&N,&M),N+M)
51     {
52         init();
53         for(int i=0;i<M;i++)
54         {
55             int a,b,c;
56             scanf("%d %d %d",&a,&b,&c);
57             if(c<g[a][b])g[a][b]=g[b][a]=c;
58         }
59         dijkstra();
60         printf("%d
",dist[N]);
61     }
62     return 0;
63 }
View Code