P13706 [NWERC 2023] Galaxy Quest

你正在驾驶你的宇宙飞船穿越银河系。 银河系中有 $n$ 个行星，编号从 $1$ 到 $n$，每个行星在三维空间中被建模为一个点。 你可以通过 $m$ 条太空高速公路在这些行星之间旅行，每条高速公路连接两个行星，并沿它们之间的直线延伸。 你的引擎可以以 $1\,\text{m}/\text{s}^2$ 的加速度（或减速度）加速或减速，同时以每秒 $1$ 升的速率消耗燃料。 你的飞船没有速度上限，但每当你到达高速公路终点的行星时，必须完全停下来。 一条高速公路可能会穿过除其连接的两个行星以外的其他行星。 然而，由于你的飞船配备了特殊的超空间技术，它可以直接穿越这些障碍而无需停下。 使用该技术的另一个后果是：你无法在途中从一条高速公路跳到另一条高速公路，必须始终完整地走完一条高速公路。  :::align{center} 图 G.1：样例输入 1 的示意图，蓝色为高速公路，展示了从行星 $1$ 到行星 $3$ 的一条路线。绿色为高速公路起点（加速），红色为终点（减速）。 ::: 你需要执行若干次任务，每次任务都从你的家园行星（编号 $1$）出发，需要在给定的时间限制内到达指定目标行星。 对于每个任务，判断能否完成，如果可以，求出所需的最少燃料量。 例如，图 G.1 展示了第一个样例中第二个任务的最优路线。

输入包括： - 一行，包含三个整数 $n$、$m$ 和 $q$（$1 \le n,m,q \le 10^5$，$n \ge 2$），分别表示行星数、高速公路数和任务数。 - 接下来 $n$ 行，每行三个整数 $x_i$、$y_i$、$z_i$（$\left|x_i\right|,\left|y_i\right|,\left|z_i\right| \le 10^3$，$1 \le i \le n$），表示第 $i$ 个行星的坐标。 - 接下来 $m$ 行，每行两个整数 $a$ 和 $b$（$1 \le a,b \le n$，$a \neq b$），表示一条连接行星 $a$ 和 $b$ 的高速公路。高速公路可以双向通行。 - 接下来 $q$ 行，每行两个整数 $c$ 和 $t$（$2 \le c \le n$，$1 \le t \le 10^3$），分别表示每个任务的目标行星和时间限制。 所有 $n$ 个行星的位置互不相同。坐标单位为米，任务的时间限制单位为秒。没有两条高速公路连接同一对行星。对于每个任务，给定的时间限制与最短可能完成时间之间的绝对和相对误差都至少为 $10^{-6}$。

对于每个任务，输出在时间限制内到达目标行星所需的最少燃料（升）。如果无法在时间限制内到达目标行星，输出“$\texttt{impossible}$”。 你的答案的绝对或相对误差不超过 $10^{-6}$。

由 ChatGPT 4.1 翻译