星际导航
(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。
样例输入
4 5
1 2 5
1 3 2
2 3 11
2 4 6
3 4 4
3
2 3
1 4
1 2
样例输出
5
4
5
数据范围与约定
对于40% 的数据,满足N≤1000,M≤3000,Q≤1000。
对于 80% 的数据,满足N≤10000,M≤105,Q≤1000。
对于 100% 的数据,满足N≤105,M≤3×105,Q≤105,L≤109。数据不保证没有重边和自环。
这种题的模型很常见,先最小生成树,再深搜处理出fat[],next[],d[]数组,分别表示生成树后每个节点的父亲,到父亲的路径权值,和此节点的深度,然后就可以一步一步先上搜,或者LCA更新答案。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 using namespace std; 11 inline int read(){ 12 int x=0,f=1;char ch=getchar(); 13 while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} 14 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 15 return x*f; 16 } 17 int N,M,Q; 18 struct node{ 19 int x,y,w; 20 }e[300005]; 21 struct node1{ 22 int x,y; 23 }q[100005]; 24 int cmp(const node&a,const node&b){ 25 if(a.w