[洛谷P2245]星际导航

题目大意：有一张n点m边的带权无向图，和一些问题，每次询问两个点之间的路径的最大边权最小是多少。

解题思路：同NOIP2013货车运输，只是数据增大，大变成小，小变成大了而已。所以具体思路见货车运输。可见两份代码仅有略微差别。

C++ Code：

#include<cstdio>

#include<algorithm>

#include<cctype>

#include<cstring>

#include<cstdio>

using std::sort;

using std::swap;

struct edge{

    int u,v,t;

    bool operator < (const edge& rhs)const{return t<rhs.t;}

}e[500005];

struct tree_edge{

    int to,dist,nxt;

}E[1200005];

int n,m,fa[100005],head[100005]={0},cnt=0,ans,deep[100005],p[100005][19],sml[100005][19];

inline int min(int a,int b){return(a>b)?(a):(b);}

inline int readint(){

    char c=getchar();

    int p=0;

    for(;!isdigit(c);c=getchar());

    for(;isdigit(c);c=getchar())p=(p<<3)+(p<<1)+(c^'0');

    return p;

}

int dad(int x){return(fa[x]==x)?(x):(fa[x]=dad(fa[x]));}

inline int addedge(int from,int to,int dist){

    E[++cnt]=(tree_edge){to,dist,head[from]};

    head[from]=cnt;

    E[++cnt]=(tree_edge){from,dist,head[to]};

    head[to]=cnt;

}

void dfs(int u){

    for(int i=head[u];i;i=E[i].nxt)

    if(!deep[E[i].to]){

        deep[E[i].to]=deep[u]+1;

        p[E[i].to][0]=u;

        sml[E[i].to][0]=E[i].dist;

        dfs(E[i].to);

    }

}

void init(){

    for(int j=1;(1<<j)<=n;++j)

    for(int i=1;i<=n;++i)

    if(p[i][j-1]!=-1)

    p[i][j]=p[p[i][j-1]][j-1],sml[i][j]=min(sml[i][j-1],sml[p[i][j-1]][j-1]);

}

int lca(int x,int y,int& ans){

    ans=-2000000000;

    int i;

    if(deep[x]<deep[y])swap(x,y);

    for(i=0;(1<<i)<=n;++i);--i;

    for(int j=i;j>=0;--j)

    if(deep[p[x][j]]>=deep[y]){

        ans=min(ans,sml[x][j]),x=p[x][j];

    }

    if(x==y)return x;

    for(int j=i;j>=0;--j)

    if(p[x][j]!=p[y][j]&&p[x][j]!=-1){

        ans=min(ans,min(sml[x][j],sml[y][j]));

        x=p[x][j];

        y=p[y][j];

    }

    ans=min(ans,min(sml[x][0],sml[y][0]));

    return p[x][0];

}

int main(){

    n=readint(),m=readint();

    for(int i=1;i<=m;++i)e[i].u=readint(),e[i].v=readint(),e[i].t=readint();

    sort(e+1,e+m+1);

    for(int i=1;i<=n;++i)fa[i]=i;

    for(int okE=1,now=1;now<=m;++now){

        int a=dad(e[now].u),b=dad(e[now].v);

        if(a!=b){

            fa[b]=a;

            addedge(e[now].u,e[now].v,e[now].t);

            ++okE;

        }

        if(okE==n)break;

    }

    int Q=readint();

    memset(deep,0,sizeof deep);

    memset(p,-1,sizeof p);

    memset(sml,0x3f,sizeof sml);

    for(int i=1;i<=n;++i)

    if(!deep[i]){

        deep[i]=1;

        dfs(i);

    }

    init();

    while(Q--){

        int x=readint(),y=readint();

        int a=dad(x),b=dad(y);

        if(a!=b){

            puts("impossible");

            continue;

        }

        lca(x,y,ans);

        printf("%d\n",ans);

    }

}