A22576.星际导航
提高+/省选-
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
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。
输入输出样例
输入#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≤1000,M≤3000,Q≤1000。
对于 80% 的数据,满足 N≤10000,M≤105,Q≤1000。
对于 100% 的数据,满足 N≤105,M≤3×105,Q≤105,L≤109。数据不保证没有重边和自环。