NOIP模拟 星际导航 nav

星际导航 nav"/>

NOIP模拟 星际导航 nav

星际导航

(nav.pas/c/cpp/in/out,1s,64MB)

题目描述

sideman做好了回到Gliese 星球的硬件准备，但是sideman的导航系统还没有完全设计好。为了方便起见，我们可以认为宇宙是一张有N 个顶点和M 条边的带权无向图，顶点表示各个星系，两个星系之间有边就表示两个星系之间可以直航，而边权则是航行的危险程度。
sideman 现在想把危险程度降到最小，具体地来说，就是对于若干个询问(A, B)，sideman 想知道从顶点A 航行到顶点B 所经过的最危险的边的危险程度值最小可能是多少。作为sideman 的同学，你们要帮助sideman 返回家园，兼享受安全美妙的宇宙航行。所以这个任务就交给你了。

输入格式

第一行包含两个正整数N 和M，表示点数和边数。
之后 M 行，每行三个整数A，B 和L，表示顶点A 和B 之间有一条边长为L 的边。顶点从1 开始标号。
下面一行包含一个正整数 Q，表示询问的数目。
之后 Q 行，每行两个整数A 和B，表示询问A 和B 之间最危险的边危险程度的可能最小值。

输出格式

对于每个询问， 在单独的一行内输出结果。如果两个顶点之间不可达， 输出 impossible 。

样例

in:

4 5
1 2 5
1 3 2
2 3 11
2 4 6
3 4 4
3
2 3
1 4
1 2

out：

5
4
5

数据范围与约定

对于40% 的数据，满足N≤1000，M≤3000，Q≤1000。
对于 80% 的数据，满足N≤10000，M≤10 5 ，Q≤1000。
对于 100% 的数据，满足N≤10 5 ，M≤3×10 5 ，Q≤10 5 ，L≤10 9 。数据不保证没有重边和自环。

第一次写博客啊

    考试的时候有一点思路，无奈LCA写不出来。用暴力加二分结果第一个点要跑98秒。。。。正解是Kruskal+LCA求最大边权最小借助Kruskal，把森林中每一棵树的最小生成树求出来，然后就可以在最小生成树上搞。LCA这里采用倍增，在预处理的过程中把danger[i][k]与anc[i][k]一同处理，为i点到距i点2^k距离的最大边权与祖先节点求出，LCA倍增时不断更新ans(路上最大边权)即可。要判断是不是impossible十分简单，Kruskal中一棵树已经在一个集合内，看两个点在不在一个集合内就能看出来。另：和NOIP2013提高组DAY1几乎完全一样，本题是最大边权最小，那一题时最小边权最大。

下面上代码

#include<cstdio>
#include<cstring>
#include<cmath>