最小瓶颈路

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int MAXN=1000+10;
 4 const int INF=0x3f3f3f3f;
 5 int n,m,k;
 6 int mapp[MAXN][MAXN];
 7 int ans[MAXN][MAXN],dis[MAXN],pri[MAXN];
 8 bool vis[MAXN];
 9 void prim()
10 {
11     memset(vis,false,sizeof(vis));
12     for(int i=1;i<=n;++i){
13         dis[i]=INF;
14         pri[i]=i;
15     }
16     dis[1]=0;
17     for(int i=1;i<=n;++i){
18         int MAXX=INF,v=-1;
19         for(int j=1;j<=n;++j){  
20             if(!vis[j]&&dis[j]<MAXX){
21                 MAXX=dis[v=j];
22             }
23         }
24         if(v==-1) break;
25         for(int j=1;j<=n;++j)
26         if(vis[j])
27         ans[v][j]=ans[j][v]=max(ans[pri[v]][j],MAXX);
28         //用新加的边，与这个边所带的（点有两个，一个新加的，一个原先就在）
29         //原先的点与j的距离进行比较
30         vis[v]=true;
31         for(int j=1;j<=n;++j){
32             if(!vis[j]&&mapp[v][j]<dis[j]){
33                 dis[j]=mapp[v][j];
34                 pri[j]=v;  //记录这条边的已经在图中的那个端点
35             }
36         }
37     }
38 }
39 
40 int main()
41 {
42     scanf("%d%d%d",&n,&m,&k);
43     int x,y,z;
44     memset(mapp,0x3f,sizeof(mapp));
45     memset(ans,0,sizeof(ans));
46     for(int i=0;i<=n;++i) mapp[i][i]=0;
47     for (int i=0;i<m;++i){
48         scanf("%d%d%d",&x,&y,&z);
49         if(mapp[x][y]>z)
50             mapp[x][y]=mapp[y][x]=z;  //有重边
51     }
52     prim();
53     while(k--){
54         scanf("%d%d",&x,&y);
55         printf("%d\n",ans[x][y]==0?-1:ans[x][y]);
56     }
57     return 0;
58 }