题面传送门 显然不可以最长路。 司机肯定喜欢走长的路径，所以先把最大生成树跑出来。 然后再最大生成树上跑倍增不就好了? 代码实现:
#include<cstdio> #include<cstring> #include<algorithm> #define min(a,b) ((a)<(b)?(a):(b)) using namespace std; int n,m,k,x,y,ans,flag[10039],f[10039],fa[10039][20],minn[10039][20],d[10039],lg[10039],tots,un,wn,w[10039]; struct yyy{int to,w,z;}; struct ljb{ int head,h[10039]; yyy f[200039]; inline void add(int x,int y,int z){ f[++head]=(yyy){y,z,h[x]}; h[x]=head; } }s; struct question{int x,y,z;}sf[200039]; inline bool cmp(question x,question y){return x.z>y.z;} inline int find(int x){return f[x]==x?x:f[x]=find(f[x]);} inline void dfs(int x,int last){ d[x]=d[last]+1; fa[x][0]=last; minn[x][0]=w[x]; for(int i=1;i<=lg[d[x]];i++) fa[x][i]=fa[fa[x][i-1]][i-1],minn[x][i]=min(minn[x][i-1],minn[fa[x][i-1]][i-1]); int cur=s.h[x]; yyy tmp; while(cur!=-1){ tmp=s.f[cur]; if(tmp.to!=last) w[tmp.to]=tmp.w,dfs(tmp.to,x); cur=tmp.z; } } inline void swap(int &x,int &y){x^=y,y^=x,x^=y;} inline int lca(int x,int y){ int ans=1e9; if(d[x]<d[y]) swap(x,y); while(d[x]>d[y]) ans=min(ans,minn[x][lg[d[x]-d[y]]-1]),x=fa[x][lg[d[x]-d[y]]-1]; if(x==y) return ans; for(int k=lg[d[x]]-1;k>=0;k--) if(fa[x][k]!=fa[y][k]) ans=min(ans,min(minn[x][k],minn[y][k])),x=fa[x][k],y=fa[y][k]; return min(ans,min(minn[x][0],minn[y][0])); } int main(){ register int i,j; memset(s.h,-1,sizeof(s.h)); memset(minn,0x3f,sizeof(minn)); scanf("%d%d",&n,&m); for(i=1;i<=n;i++) f[i]=i; for(i=1;i<=n;i++) lg[i]=lg[i-1]+(1<<lg[i-1]==i); for(i=1;i<=m;i++){ scanf("%d%d%d",&sf[i].x,&sf[i].y,&sf[i].z); un=find(sf[i].x);wn=find(sf[i].y); if(un!=wn) f[un]=wn; } for(i=1;i<=n;i++){ flag[find(i)]++; if(flag[find(i)]==1) ans++; } for(i=1;i<=n;i++) f[i]=i; sort(sf+1,sf+m+1,cmp); for(i=1;i<=m;i++){ un=find(sf[i].x);wn=find(sf[i].y); if(un!=wn){ f[un]=wn; tots++; s.add(sf[i].x,sf[i].y,sf[i].z); s.add(sf[i].y,sf[i].x,sf[i].z); //printf("%d %d %d\n",sf[i].x,sf[i].y,sf[i].z); if(tots==n-ans) break; } } w[1]=1e9; dfs(1,1); /*for(i=1;i<=n;i++){ for(j=0;j<=lg[d[i]];j++) printf("%d ",fa[i][j]); printf("\n"); }*/ scanf("%d",&k); for(i=1;i<=k;i++){ scanf("%d%d",&x,&y); if(find(x)!=find(y)) printf("-1\n"); else printf("%d\n",lca(x,y)); } }