显然使A到B的最长边最小的路径一定在最小生成树上，否则一定可以使生成树更小。
求出原图的最小生成树，然后用倍增求路径上最大值就可以了。
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 using namespace std; 6 #define N 15010 7 #define S 15 8 struct Edge{ 9 int f,t,nx,w; 10 Edge(){} 11 Edge(int f,int t,int w):f(f),t(t),w(w){} 12 bool operator < (Edge a)const{ 13 return w>a.w; 14 } 15 }e[N<<1],tmp; 16 priority_queue<Edge>Q; 17 int d[N],i,j,k,x,y,z,n,m,Num,h[N],f[N][S],Max[N][S]; 18 inline int _Max(int x,int y){return x<y?y:x;} 19 inline void Add(int x,int y,int z){ 20 e[++Num].t=y;e[Num].w=z;e[Num].nx=h[x];h[x]=Num; 21 } 22 inline int Find(int x){return f[x][0]==x?x:f[x][0]=Find(f[x][0]);} 23 inline void Dfs(int x,int F){ 24 f[x][0]=F;d[x]=d[F]+1; 25 for(int i=h[x];i;i=e[i].nx) 26 if(e[i].t!=F)Max[e[i].t][0]=e[i].w,Dfs(e[i].t,x); 27 } 28 inline int Query(int x,int y){ 29 if(d[x]<d[y])swap(x,y); 30 int Ans=0; 31 for(int i=S-1;i>=0;i--) 32 if(d[f[x][i]]>=d[y])Ans=_Max(Ans,Max[x][i]),x=f[x][i]; 33 if(x==y)return Ans; 34 for(int i=S-1;i>=0;i--) 35 if(f[x][i]!=f[y][i])Ans=_Max(Ans,_Max(Max[x][i],Max[y][i])),x=f[x][i],y=f[y][i]; 36 return _Max(Ans,_Max(Max[x][0],Max[y][0])); 37 } 38 int main() 39 { 40 scanf("%d%d%d",&n,&m,&k); 41 for(i=1;i<=m;i++)scanf("%d%d%d",&x,&y,&z),Q.push(Edge(x,y,z)); 42 for(i=1;i<=n;i++)f[i][0]=i; 43 for(i=1;i<n;i++){ 44 tmp=Q.top();Q.pop(); 45 while(Find(tmp.f)==Find(tmp.t))tmp=Q.top(),Q.pop(); 46 f[Find(tmp.f)][0]=Find(tmp.t);Add(tmp.f,tmp.t,tmp.w);Add(tmp.t,tmp.f,tmp.w); 47 } 48 Dfs(1,0); 49 for(j=1;j<S;j++) 50 for(i=1;i<=n;i++) 51 f[i][j]=f[f[i][j-1]][j-1],Max[i][j]=_Max(Max[i][j-1],Max[f[i][j-1]][j-1]); 52 while(k--){ 53 scanf("%d%d",&x,&y); 54 printf("%d ",Query(x,y)); 55 } 56 return 0; 57 }