题目描述
( ext{sideman}) 做好了回到 ( ext{Gliese}) 星球的硬件准备，但是 ( ext{sideman}) 的导航系统还没有完全设计好。为了方便起见，我们可以认为宇宙是一张有 (N) 个顶点和 (M)条边的带权无向图，顶点表示各个星系，两个星系之间有边就表示两个星系之间可以直航，而边权则是航行的危险程度。
( ext{sideman}) 现在想把危险程度降到最小，具体地来说，就是对于若干个询问 ((A, B))，( ext{sideman}) 想知道从顶点 (A) 航行到顶点 (B) 所经过的最危险的边的危险程度值最小可能是多少。作为 ( ext{sideman}) 的同学，你们要帮助 ( ext{sideman}) 返回家园，兼享受安全美妙的宇宙航行。所以这个任务就交给你了。
输入输出格式
输入格式：
第一行包含两个正整数 (N) 和 (M)，表示点数和边数。
之后 (M) 行，每行三个整数 (A)，(B) 和 (L)，表示顶点 (A) 和 (B) 之间有一条边长为 (L) 的边。顶点从 (1) 开始标号。
下面一行包含一个正整数 (Q)，表示询问的数目。
之后 (Q) 行，每行两个整数 (A) 和 (B)，表示询问 (A) 和 (B) 之间最危险的边危险程度的可能最小值。
输出格式：
对于每个询问， 在单独的一行内输出结果。如果两个顶点之间不可达， 输出 $ ext{impossible}$。
输入输出样例
输入样例#1：
4 5
1 2 5
1 3 2
2 3 11
2 4 6
3 4 4
3
2 3
1 4
1 2
输出样例#1：
5
4
5
说明
对于 (40\%) 的数据，满足 (N leq 1000, M leq 3000, Q leq 1000)。
对于 (80\%) 的数据，满足 (N leq 10000, M leq 10^5, Q leq 1000)。
对于 (100\%) 的数据，满足 (N leq 10^5, M leq 3 imes 10^5, Q leq 10^5, L leq 10^9)。数据不保证没有重边和自环。
题解
最小瓶颈路模板题。。。
当模板放着吧。。。
code：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#define R register
#define N 300005
using namespace std;
template<typename T>inline void read(T &a){
char c=getchar();T x=0,f=1;
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
a=f*x;
}
int n,m,tot,num,q,fat[N],mx[N][21],fa[N][21];
int dep[N],h[N];
struct MST{
int u,v,w;
friend bool operator < (const MST &a,const MST &b){
return a.w<b.w;
}
}t[N];
inline void ins(R int u,R int v,R int w){
t[++num].u=u;
t[num].v=v;
t[num].w=w;
}
struct node{
int nex,to,dis;
}edge[N<<1];
inline void add(R int u,R int v,R int w){
edge[++tot].nex=h[u];
edge[tot].to=v;
edge[tot].dis=w;
h[u]=tot;
}
inline int find(R int x){return fat[x]==x?fat[x]:fat[x]=find(fat[x]);}
inline void dfs(R int x,R int f,R int g){
dep[x]=dep[f]+1;
fa[x][0]=f;
mx[x][0]=g;
for(R int i=1;(1<<i)<=dep[x];i++)
fa[x][i]=fa[fa[x][i-1]][i-1],
mx[x][i]=max(mx[x][i-1],mx[fa[x][i-1]][i-1]);
for(R int i=h[x];i;i=edge[i].nex){
R int xx=edge[i].to;
if(xx==f)continue;
dfs(xx,x,edge[i].dis);
}
}
inline int get_ans(R int x,R int y){
R int res=0;
if(dep[x]>dep[y])swap(x,y);
for(R int i=20;i>=0;i--)
if(dep[x]<=dep[y]-(1<<i))
res=max(res,mx[y][i]),y=fa[y][i];
if(x==y)return res;
for(R int i=20;i>=0;i--)
if(fa[x][i]!=fa[y][i])
res=max(res,max(mx[x][i],mx[y][i])),
x=fa[x][i],y=fa[y][i];
res=max(res,max(mx[x][0],mx[y][0]));
return res;
}
int main(){
read(n);read(m);
for(R int i=1;i<=n;i++)fat[i]=i;
for(R int i=1,u,v,w;i<=m;i++)
read(u),read(v),read(w),ins(u,v,w);
sort(t+1,t+1+m);
for(R int i=1;i<=m;i++){
R int x=find(t[i].u);
R int y=find(t[i].v);
if(x!=y){
fat[x]=y;
add(x,y,t[i].w);
add(y,x,t[i].w);
}
}
dfs(1,0,0);
read(q);
while(q--){
R int x,y;
read(x);read(y);
if(find(x)!=find(y))puts("impossible");
else printf("%d
",get_ans(x,y));
}
return 0;
}