POJ1797(Heavy Transportation)

单源最短路的变形，需要很好的理解dijkstra最短路算法的思想。

View Code

 1 #include <stdio.h>
 2 #include <memory.h>
 3 #define MIN(a,b) ((a)<(b)?(a):(b))
 4 #define MAX(a,b) ((a)>(b)?(a):(b))
 5 #define N 1000
 6 int g[N][N],w[N],n,m;
 7 char vis[N];
 8 void dijkstra()
 9 {
10     int i,v,k,max;
11     memset(vis,0,sizeof(vis));
12     for(i=1;i<n;i++)    w[i]=g[0][i];
13     for(i=1;i<n;i++)
14     {
15         max=0;
16         for(v=1;v<n;v++)    if(!vis[v]&&w[v]>=max)  max=w[k=v];
17         vis[k]=1;
18         for(v=1;v<n;v++)    w[v]=MAX(w[v],MIN(w[k],g[k][v]));
19     }
20 }
21 int main()
22 {
23     int t,i,j,a,b,d,kase=0;
24     scanf("%d",&t);
25     while(t--)
26     {
27         scanf("%d%d",&n,&m);
28         for(i=0;i<n;i++)
29         {
30             for(j=i+1;j<n;j++)  g[i][j]=g[j][i]=-1;
31         }
32         for(i=0;i<m;i++)
33         {
34             scanf("%d%d%d",&a,&b,&d);
35             a--,b--;
36             g[a][b]=g[b][a]=d;
37         }
38         dijkstra();
39         printf("Scenario #%d:\n",++kase);
40         printf("%d\n\n",w[n-1]);
41     }
42     return 0;
43 }