记录编号	265034	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]货车运输	最终得分	100
用户昵称	Sky_miner	是否通过	通过
代码语言	C++	运行时间	0.061 s
提交时间	2016-06-01 08:10:47	内存使用	2.88 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline void read(int &x){
    x=0;char ch;
    while(ch=getchar(),ch<'!');
    while(x=10*x+ch-'0',ch=getchar(),ch>'!');
}
const int maxn = 10000 + 10 ;
const int maxe = 50000 + 10 ;
const int maxd = 22 ;
inline int cat_max(const int &a,const int &b){return a>b ? a:b;}
inline int cat_min(const int &a,const int &b){return a<b ? a:b;}
struct S_Edge{
    int from,to,dis;
}save[maxe];
bool cmp(const S_Edge &a,const S_Edge &b){
    return a.dis > b.dis;
}
inline void swap(int &x,int &y){x^=y;y^=x;x^=y;}
inline void watch(int *f,int n){
    printf("--------begin---------\n");
    for(int i=1;i<=n;++i) printf("%d ",f[i]);
    printf("\n-------end----------\n");
}
struct Edge{
    int to,next,dis;
}G[maxn<<1];//确实是maxn<<1,不是maxe<<1
int head[maxn],cnt;
void add(int u,int v,int dis){
    G[++cnt].to = v;
    G[cnt].dis = dis;
    G[cnt].next = head[u];
    head[u] = cnt;
}
int fath[maxn];
inline int find(const int &x){return fath[x] == x ? x : fath[x] = find(fath[x]); }
int fa[maxn][maxd],deep[maxn],dis[maxn][maxd];
void dfs(int u){
    for(int i=head[u];i;i=G[i].next){
        if( !deep[G[i].to ]){
            deep[ G[i].to ] = deep[u] + 1;
            fa[G[i].to][0] = u;
            dis[G[i].to][0] = G[i].dis;
            dfs(G[i].to);
        }
    }
}
int LCA(int x,int y){
    int ret = 0x7fffffff;
    if( deep[x] < deep[y] ) swap(x,y);
    int i;
    for(i=0;(1<<i)<=deep[x];++i);
    --i;
    for(int j=i;j>=0;--j){
        if( deep[x] - (1<<j) >= deep[y] ){
            ret = cat_min(ret,dis[x][j]);
            x = fa[x][j];
        }
    }
    if( x == y ) return ret;
    for(int j=i;j>=0;--j){
        if( fa[x][j] && fa[x][j] != fa[y][j] ){
            ret =cat_min( ret,cat_min(dis[x][j],dis[y][j]) );
            x = fa[x][j];
            y = fa[y][j];
        }
    }
    ret = cat_min(ret,cat_min(dis[y][0],dis[x][0]));
    return ret;
}
int main(){
    freopen("truck.in","r",stdin);
    freopen("truck.out","w",stdout);
    int n,m;read(n),read(m);
    for(int i=1;i<=m;++i){
        read(save[i].from);
        read(save[i].to);
        read(save[i].dis);
    }
    sort(save+1,save+m+1,cmp);
    for(int i=1;i<=n;++i) fath[i] = i;
    int u,v;
    for(int i=1;i<=m;++i){
        u = save[i].from;v = save[i].to;
        //printf("find edge from %d to %d with dis is %d \n",u,v,save[i].dis);
        if( find(u) != find(v) ){
            fath[find(u)] = fath[find(v)];
            //printf("add  edge from %d to %d with dis is %d \n",u,v,save[i].dis);
            add( u,v,save[i].dis );
            add( v,u,save[i].dis );
        }
    }
    for(int i=1;i<=n;++i){
        if( !deep[i] ){
            deep[i] = 1;
            dfs(i);
        }
    }
    //watch(deep,4);
    for(int j=1;(1<<j)<=n;++j){
        for(int i=1;i<=n;++i){
            fa[i][j] = fa[ fa[i][j-1] ][j-1];
            dis[i][j] = cat_min(dis[i][j-1],dis[fa[i][j-1]][j-1]);
        }
    }
    int q;read(q);
    for(int i=1;i<=q;++i){
		read(u),read(v);
		if(find(u)!=find(v)) printf("%d\n",-1);
		else printf("%d\n",LCA(u,v));
	}
    return 0;
}