xsy 2018 【NOIP2013】货车运输

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct data{
    int x,y,v;
}t[50001],d[20001];
int n,m,s[10001][21],f[10001][21],fa[10001],h[10001],cnt,fx,fy,ans,p[10001],id[10001],x,y;
bool cmp(data a,data b){
    return a.v>b.v;
}
int father(int a){
    if(fa[a]!=a)fa[a]=father(fa[a]);
    return fa[a];
}
void add(int a,int b,int c){
    cnt++;
    d[cnt].x=b;
    d[cnt].y=h[a];
    d[cnt].v=c;
    h[a]=cnt;
}
void dfs(int a){
    for(int i=1;i<=20;i++){
        f[a][i]=f[f[a][i-1]][i-1];
        s[a][i]=min(s[a][i-1],s[f[a][i-1]][i-1]);
    }
    for(int i=h[a];i;i=d[i].y){
        if(!p[d[i].x]){
            p[d[i].x]=p[a]+1;
            f[d[i].x][0]=a;
            s[d[i].x][0]=d[i].v;
            id[d[i].x]=id[a];
            dfs(d[i].x);
        }
    }
}
void lca(int a,int b){
    if(p[a]>p[b]){
        for(int i=20;i>=0;i--){
            if(p[f[a][i]]>=p[b]){
                ans=min(ans,s[a][i]);
                a=f[a][i];
            }
        }
    }
    if(p[a]<p[b]){
        for(int i=20;i>=0;i--){
            if(p[f[b][i]]>=p[a]){
                ans=min(ans,s[b][i]);
                b=f[b][i];
            }
        }
    }
    for(int i=20;i>=0;i--){
        if(f[a][i]!=f[b][i]){
            ans=min(ans,s[a][i]);
            ans=min(ans,s[b][i]);
            a=f[a][i];
            b=f[b][i];
        }
    }
    if(a!=b){
        ans=min(ans,s[a][0]);
        ans=min(ans,s[b][0]);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)scanf("%d%d%d",&t[i].x,&t[i].y,&t[i].v);
    for(int i=1;i<=n;i++)fa[i]=i;
    sort(t+1,t+m+1,cmp);
    for(int i=1;i<=m;i++){
        fx=father(t[i].x);
        fy=father(t[i].y);
        if(fx!=fy){
            fa[fx]=fy;
            add(t[i].x,t[i].y,t[i].v);
            add(t[i].y,t[i].x,t[i].v);
        }
    }
    for(int i=1;i<=n;i++){
        if(!id[i]){
            p[i]=1;
            id[i]=i;
            dfs(i);
        }
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        ans=10000000;
        scanf("%d%d",&x,&y);
        if(id[x]==id[y]){
            lca(x,y);
            printf("%d\n",ans);
        }else printf("-1\n");
    }
}