← 返回题目

题库练习星际导航

← 上一题下一题 →

A2864 | $星际导航$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

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

输入格式

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

输出格式

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

输入输出样例

输入 #1

输出 #1

5
4
5

C++ 编辑器

输入

输出