HDUOJ --2544最短路（基础）

 1 #include<stdio.h>
 2 #include<string.h>
 3 const int inf=0x3f3f3f3f ;
 4 int path[101];
 5 int sta[101][101],lowcost[101];
 6 void Dijkstra( int cost[][101], int n )
 7 {
 8     int i,j,min;
 9     int vis[101]={1};
10     for(i=0; i<n ; i++)
11     {
12         lowcost[i]=cost[0][i];
13         path[i]=0;
14     }
15     lowcost[0]=0;
16     path[0]=-1;  
17     int pre= 0;
18     for( i=1 ; i<n ;i++)
19     {
20         min=inf;
21         for(j=0 ; j<n ;j++)
22         {
23             if(vis[j]==0&&lowcost[pre]+cost[pre][j]<lowcost[j])
24             {
25                 lowcost[j]=lowcost[pre]+cost[pre][j];
26                 path[j]=pre;
27             }
28         }
29         for(j=0; j<n ;j++)
30         {
31             if(vis[j]==0&&lowcost[j]<min)
32             {
33                 min=lowcost[j];
34                 pre=j;
35             }
36         }
37         vis[pre]=1;
38     }
39    printf("%d\n",lowcost[n-1]);
40 }
41 
42 int main()
43 {
44     int n,m,x,y,val,i,j;
45     while(scanf("%d%d",&n,&m),n+m)
46     {
47         for(i=0;i<n;i++)
48         {
49             for(j=0;j<n;j++)
50             {
51                 sta[i][j]=inf;
52             }
53         }
54         while(m--)
55         {
56             scanf("%d%d%d",&x,&y,&val);
57             sta[y-1][x-1]=sta[x-1][y-1]=val;
58         }
59         Dijkstra(sta,n);
60     }
61     return 0;
62 }