读完题，我产生了一个显然的想法：先求出这张图的最大生成树，然后再dfs一遍求出联通块的个数（图可能不连通），之后这张图变成了一棵树，题目就变成了在一棵树上给定一条路径，求这条路径上最小的边权是多少。（-1的情况可以通过并查集直接判断）。

考虑一条路路径(x,y)，我们可以把它拆分成(x,lca(x,y))和(lca(x,y),y)两条路径，我们可以通过倍增实现lca，在预处理时维护两个数组，fa[x][i]表示x的2ⁱ辈祖先是谁，minn[x][i]表示在路径(x,fa[x][i])中最小的边权。minn数组的求法有一点类似ST表。

有了这些，我们就可以解决问题了。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 using namespace std;
  6 inline int read() {
  7     int ret=0;
  8     int op=1;
  9     char c=getchar();
 10     while(c<'0'||c>'9') {if(c=='-') op=-1; c=getchar();}
 11     while(c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
 12     return ret*op;
 13 }
 14 struct node {
 15     int from,to,dis;
 16     bool operator <(const node &x) const {
 17         return dis>x.dis;
 18     }
 19 }a[50010];
 20 struct Edge {
 21     int next,to,dis;
 22 }edge[50010<<1];
 23 int head[50010<<1],num,fa[10010][19],minn[10010][19],f[10010],d[10010],tot,vis[10010];
 24 int n,m;
 25 int find(int x) {
 26     if(f[x]!=x) f[x]=find(f[x]);
 27     return f[x];
 28 }
 29 inline void add(int from,int to,int dis) {
 30     edge[++num].next=head[from]; edge[num].to=to; edge[num].dis=dis; head[from]=num;
 31     swap(from,to);
 32     edge[++num].next=head[from]; edge[num].to=to; edge[num].dis=dis; head[from]=num;
 33 }
 34 void dfs(int u) {
 35     vis[u]=1;
 36     for(int i=head[u];i;i=edge[i].next) {
 37         int v=edge[i].to;
 38         if(!vis[v]) {
 39             d[v]=d[u]+1;
 40             fa[v][0]=u;
 41             minn[v][0]=edge[i].dis;
 42             dfs(v);
 43         }
 44     }
 45 }
 46 int lca(int x,int y) {
 47     int ans=2147483647;
 48     if(d[x]<d[y]) swap(x,y);
 49     for(int i=17;i>=0;i--)
 50         if(d[fa[x][i]]>=d[y]) {
 51             ans=min(ans,minn[x][i]);
 52             x=fa[x][i];
 53         }
 54     if(x==y) return ans;
 55     for(int i=17;i>=0;i--)
 56         if(fa[x][i]!=fa[y][i]) {
 57             ans=min(ans,min(minn[x][i],minn[y][i]));
 58             x=fa[x][i];
 59             y=fa[y][i];
 60         }
 61     return ans=min(ans,min(minn[x][0],minn[y][0]));
 62 }
 63 int main() {
 64     n=read(); m=read();
 65     for(int i=1;i<=m;i++) {
 66         a[i].from=read();
 67         a[i].to=read();
 68         a[i].dis=read();
 69     }
 70     sort(a+1,a+m+1);
 71     for(int i=1;i<=n;i++) f[i]=i;
 72     for(int i=1;i<=m;i++) {
 73         if(tot==n-1) break ;
 74         if(find(a[i].from)!=find(a[i].to)) {
 75             tot++;
 76             add(a[i].from,a[i].to,a[i].dis);
 77             f[find(a[i].from)]=f[find(a[i].to)];
 78         }
 79     }
 80     memset(vis,0,sizeof(vis));
 81     for(int i=1;i<=n;i++) 
 82         if(!vis[i]) {
 83             d[i]=1;
 84             dfs(i);
 85             fa[i][0]=i;
 86             minn[i][0]=999999999;
 87         }
 88     for(int j=1;j<=17;j++)
 89         for(int i=1;i<=n;i++) {
 90             fa[i][j]=fa[fa[i][j-1]][j-1];
 91             minn[i][j]=min(minn[i][j-1],minn[fa[i][j-1]][j-1]);
 92         }
 93     int op=read();
 94     while(op--) {
 95         int x=read(),y=read();
 96         if(find(x)!=find(y)) puts("-1");
 97         else printf("%d\n",lca(x,y));
 98     }
 99     return 0;
100 }

AC Code