poj1797Heavy Transportation

dijkstra。
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<queue>
 4 #include<algorithm>
 5 using namespace std;
 6 const int maxn=1010;
 7 int pic[maxn][maxn];
 8 int vis[maxn];
 9 int dc[maxn];
10 int t,n,m;
11 void dijkstra()
12 {
13 
14 
15     for(int j=0;j<n;j++)
16     {
17      int m=-1,x;
18      for(int i=1;i<=n;i++)
19         if(!vis[i]&&dc[i]>m) m=dc[x=i];
20         vis[x]=1;
21      for(int i=1;i<=n;i++)
22          if(!vis[i]&&dc[i]<min(dc[x],pic[x][i]))
23          {
24              dc[i]=min(dc[x],pic[x][i]);
25          }
26 
27     }
28 
29 
30 }
31 
32 int main()
33 {
34     scanf("%d",&t);
35     int u,v,w;
36     for(int i=1;i<=t;i++)
37     {
38         scanf("%d%d",&n,&m);
39         memset(pic,0,sizeof(pic));
40         while(m--)
41         {
42             scanf("%d%d%d",&u,&v,&w);
43             pic[u][v]=pic[v][u]=w;
44         }
45         for(int i=1;i<=n;i++)
46         {
47             vis[i]=0;
48             dc[i]=pic[1][i];
49         }
50         dijkstra();
51         printf("Scenario #%d:
%d

",i,dc[n]);
52     }
53     return 0;
54 
55 }