洛谷P2245 星际导航

传送门

题目描述

\text{sideman}sideman 做好了回到 \text{Gliese}Gliese 星球的硬件准备，但是 \text{sideman}sideman 的导航系统还没有完全设计好。为了方便起见，我们可以认为宇宙是一张有 NN 个顶点和 MM 条边的带权无向图，顶点表示各个星系，两个星系之间有边就表示两个星系之间可以直航，而边权则是航行的危险程度。

\text{sideman}sideman 现在想把危险程度降到最小，具体地来说，就是对于若干个询问 (A, B)(A,B)，\text{sideman}sideman 想知道从顶点 AA 航行到顶点 BB 所经过的最危险的边的危险程度值最小可能是多少。作为 \text{sideman}sideman 的同学，你们要帮助 \text{sideman}sideman 返回家园，兼享受安全美妙的宇宙航行。所以这个任务就交给你了。

输入格式

第一行包含两个正整数 NN 和 MM，表示点数和边数。

之后 MM 行，每行三个整数 AA，BB 和 LL，表示顶点 AA 和 BB 之间有一条边长为 LL 的边。顶点从 11 开始标号。

下面一行包含一个正整数 QQ，表示询问的数目。

之后 QQ 行，每行两个整数 AA 和 BB，表示询问 AA 和 BB 之间最危险的边危险程度的可能最小值。

输出格式

对于每个询问， 在单独的一行内输出结果。如果两个顶点之间不可达， 输出 \text{impossible}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%40% 的数据，满足 N \leq 1000, M \leq 3000, Q \leq 1000N≤1000,M≤3000,Q≤1000。

对于 80%80% 的数据，满足 N \leq 10000, M \leq 10^5, Q \leq 1000N≤10000,M≤10
5
,Q≤1000。

对于 100%100% 的数据，满足 N \leq 10^5, M \leq 3 \times 10^5, Q \leq 10^5, L \leq 10^9N≤10
5
,M≤3×10
5
,Q≤10
5
,L≤10
9
。数据不保证没有重边和自环。

上代码：

#include<bits/stdc++.h>
using namespace std;
const int N=100005,M=300005;
int n,m,q,b[N],ai,fa[N],aj,deep[N],up[N][18],da[N][18],flag[N],ans;
struct node{
    
    int to,next/*from*/,danger;
    bool operator<(node &x){
    
    	return danger<x.danger;
    }
}aa[M]/*Graph*/,a[N<<1];//SMT
void in(){
    
    scanf("%d%d",&n,&m);
    for(int i=0,x,y,z;i<m;i++)
    {
    
        scanf("%d%d%d",&x,&y,&z);
        aa[++ai]=(node){
    x,y,z};
    }
}
int find(int i){
    
    if(fa[i]!=i)fa[i]=find(fa[i]);
    return fa[i];
}
void _dfs(int u){
    
    for(int i=b[u],v;i;i=a[i].next)
    if(!deep[v=a[i].to])
    {
    
        deep[v]=deep[u]+1;
        up[v][0]=u;
        da[v][0]=a[i].danger;
        _dfs(v);
    }
}
int lca(int x,int y){
    
    int i,ans=0;
    if(deep[y]>deep[x])swap(x,y);
    for(i=17;~i;--i)//走到同一个高度
    if(deep[up[x][i]]>=deep[y])
    ans=max(ans,da[x][i]),x=up[x][i];//倍增
    for(i=17;~i;--i)//找最早的共同父亲，同时求出最小值
    if(up[x][i]!=up[y][i])
    ans=max(ans,max(da[x][i],da[y][i])),x=up[x][i],y=up[y][i];//倍增
    return x==y?ans:max(ans,max(da[x][0],da[y][0]));//最后检验
}
void work(){
    
    for(int i=1;i<=n;i++)fa[i]=i;
    sort(aa+1,aa+ai+1);
    for(int i=1;i<=ai;i++)
    {
    
        int ii=aa[i].to,jj=aa[i].next,kk=aa[i].danger;
        if(find(ii)!=find(jj)){
    
            fa[find(ii)]=find(jj);
            a[++aj]=(node){
    ii,b[jj],kk};b[jj]=aj;
            a[++aj]=(node){
    jj,b[ii],kk};b[ii]=aj;
        }
    }
}
void pre(){
    
    for(int i=1;i<=n;++i)
    if(!deep[i])
    {
    
        deep[i]=1;
        _dfs(i);
        up[i][0]=i;//self-father防越位
        da[i][0]=0;
    }
    for(int i=1;i<18;++i)
    for(int j=1;j<=n;++j)
    {
    
        up[j][i]=up[up[j][i-1]][i-1];
        da[j][i]=max(da[j][i-1],da[up[j][i-1]][i-1]);
    }
}
void out(){
    
    pre();
    int ii,jj;
    for(scanf("%d",&q);q;q--)
    {
    
        scanf("%d%d",&ii,&jj);
        if(find(ii)!=find(jj))printf("impossible\n");
        else printf("%d\n",lca(ii,jj));
    }
}
int main(){
    
    in();
    work();
    out();
}