P13167 [GCJ 2017 #1B] Pony Express

现在是 1860 年，Pony Express 是连接美国东西海岸最快的邮件递送系统。该系统服务于 $N$ 个不同的城市。每个城市都有一匹马（正如“一马小镇”这个说法）；每匹马都有一个恒定的速度，并且有一个最大总行驶距离，超过这个距离马就会太累无法继续前进。 Pony Express 的骑手会骑上起始城市的马出发。每当骑手到达一个城市时，可以选择继续使用当前的马，或者换乘该城市的马；换马是瞬间完成的。马匹永远没有休息的机会，因此一旦马的最大总距离被“消耗”了一部分，这部分就永远无法恢复！当骑手到达目的地城市时，邮件就被送达。 城市之间的路线是通过公司老板、立法者、工会代表和表哥 Pete 的复杂协商建立的。这意味着城市之间的距离不一定符合常理：例如，它们不一定满足三角不等式，从城市 A 到城市 B 的距离可能与从城市 B 到城市 A 的距离不同！ 你是一位穿越时空的企业家，带来了一台来自未来的高速计算机。虽然一台计算机还不足以让你建立电子邮件服务从而让 Pony Express 过时，但你可以用它为 Pony Express 制定最优的路线规划。给定所有城市间路线和每个城市马匹的信息，以及一系列起点和终点城市对，你能否快速计算出每次递送所需的最短时间？（你应将所有递送视为独立事件；在一条路线中使用的城市/马匹不会影响其他路线的可用性。）

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据描述如下： - 一行包含两个整数：$N$，表示有马的城市数量，$Q$，表示需要查询的起止城市对数量。城市编号为 $1$ 到 $N$。 - 接下来 $N$ 行，每行包含两个整数 $E_i$ 和 $S_i$，分别表示第 $i$ 个城市的马的最大总行驶距离（单位：千米）和恒定速度（单位：千米/小时）。 - 接下来 $N$ 行，每行包含 $N$ 个整数。第 $i$ 行第 $j$ 个整数 $D_{ij}$，若 $D_{ij} = -1$，表示没有从第 $i$ 个城市到第 $j$ 个城市的直达路线，否则表示该路线的长度（单位：千米）。 - 接下来 $Q$ 行，每行包含两个整数 $U_k$ 和 $V_k$，分别表示第 $k$ 个需要查询的起点和终点城市。

对于每组测试数据，输出一行，格式为 `Case #x: y_1 y_2 ... y_Q`，其中 $x$ 表示测试用例编号（从 1 开始），$y_k$ 表示从城市 $U_k$ 到城市 $V_k$ 递送邮件所需的最短时间（单位：小时）。 每个 $y_k$ 的答案只要在绝对误差或相对误差 $10^{-6}$ 以内都视为正确。

**样例说明** 注意，最后一个样例不会出现在 Small 数据集中。 在 Case #1 中有两种选择：全程使用城市 1 的马，或者在城市 2 换马。两匹马的耐力都足够，因此两种方案都可行。由于城市 2 的马更快，所以换马更优，总时间为 $1/3 + 1/4$。 在 Case #2 中，有两个中间城市可以换马。如果你在城市 2 换马，虽然新马速度极快，但耐力不足，因此你必须在城市 3 再次换马。如果你不换马，则可以选择在城市 3 换马（或不换）。三种方案及其总时间如下： 1. 在城市 2 和 3 都换马（$1/10 + 1/1000 + 10/8 = 1.351$）。 2. 只在城市 3 换马（$2/10 + 10/8 = 1.45$）。 3. 全程不换马（$12/10 = 1.2$）。 在 Case #3 中，每次递送都有许多选择。对于第一次递送（城市 2 到城市 4），最优方案是先到城市 1，耗时 $10/1000$，换马后再依次到城市 2、3、4，使用城市 1 的马，总耗时为 $(10 + 10 + 10) / 60$。 对于 Case #3 的第二次递送（城市 3 到城市 2），你只能先到城市 4，耗时 $10/5$。你的马虽然速度快，但耐力不足以到其他地方，因此你需要换乘城市 4 的马。你可以直接骑它到城市 1，耗时 15，但骑到城市 2 只需 6，然后再用城市 2 的极速马到城市 1，仅需额外 $10/1000$ 时间。 对于 Case #3 的第三次递送（城市 3 到城市 1），最优方案是复用上一次的前两步，总耗时 $10/5 + 6 = 8$。 **数据范围** - $1 \leq T \leq 100$。 - $2 \leq N \leq 100$。 - $1 \leq E_i \leq 10^9$，对于所有 $i$。 - $1 \leq S_i \leq 1000$，对于所有 $i$。 - $-1 \leq D_{ij} \leq 10^9$，对于所有 $i, j$。 - $D_{ii} = -1$，对于所有 $i$。（不存在城市到自身的直达路线。） - $D_{ij} \neq 0$，对于所有 $i, j$。 - $U_k \neq V_k$，对于所有 $k$。 - 保证对于所有 $k$，从 $U_k$ 到 $V_k$ 的递送一定可以完成。 - 对于任意不同的 $l, m$，有 $U_l \neq U_m$ 和/或 $V_l \neq V_m$。（每组测试数据中不会有重复的城市对。） **Small 数据集（16 分，测试集 1 - 可见）** - 对于所有 $i, j$，若 $i + 1 \neq j$，则 $D_{ij} = -1$。（城市排成一条直线，每条路线只连接相邻城市。） - $Q = 1$。 - $U_1 = 1$。 - $V_1 = N$。（唯一需要计算的递送是从第一座城市到最后一座城市。） **Large 数据集（24 分，测试集 2 - 隐藏）** - $1 \leq Q \leq 100$。 - $1 \leq U_k \leq N$，对于所有 $k$。 - $1 \leq V_k \leq N$，对于所有 $k$。 由 ChatGPT 4.1 翻译