SP27099 FN16ROAD - Road Times

Ubol Narongdid 是一家名为 Special D-Liver-E 的新创公司的创始人。她计划在普吉岛地区的医院之间垄断器官的夜间配送市场。为了进行有效的调度，准确地估计配送时间至关重要。目前，已完成了一些医院间的配送，因此这些路径上的配送时间是已知的。公司虽然拥有软件来估算其他尚未进行的配送时间，但不幸的是，这些估算一直不太准确。 你需要提出一种方法来改进这些估计。你可以利用以下信息：1）普吉岛地区城市之间连接道路的长度（以公里为单位），以及 2）之前已执行的配送时间（以分钟为单位）。 已知道路是单行道，并且每条道路都有一个速度限制，范围在 30 到 60 公里/小时之间。速度限制是实数，并不要求是整数。同时，配送卡车总是选择最短的路线，并在每条道路上以该道路的速度限制行驶。因此，例如，如果某次配送全程为 50 公里，那么在没有任何其他信息的情况下，这次配送需要的时间在 50 到 100 分钟之内。不过，你还拥有其他信息，即之前的配送时间。现在由你来利用这些信息，给出最优的时间估算。

输入包含多个测试用例，直到文件结束为止。对于每个测试用例： - 第一行包含一个整数 $n$（$1 \le n \leq 30$），表示城市的数量，编号从 $0$ 到 $n-1$。 - 接下来的 $n$ 行，每行有 $n$ 个整数，表示城市间的距离（以公里为单位）。第 $i$ 行的第 $j^{\text{th}}$ 个数表示城市 $i$ 到城市 $j$ 的直接距离。如果为 $-1$，则表示这两座城市之间没有直接道路。任一城市到自身的距离为 $0$；其他距离为正数且不超过 $1,000$。最多有 $100$ 条道路。 然后： - 之后是一行整数 $r$（$1 \le r \leq 100$），表示此前已执行的路线数。 - 接下来的 $r$ 行中，每行包含三个整数 $s$、$d$ 和 $t$，表示从城市 $s$ 到城市 $d$ 的配送时间 $t$（以分钟为单位）。 最后： - 还有一行，包含一个整数 $q$（$1 \le q \leq 100$），表示未来需要估算的配送查询数量。 - 接下来的 $q$ 行，每行包含两个整数 $s$ 和 $d$，表示需要为从城市 $s$ 到城市 $d$ 的配送进行时间估算。 假设输入中每个 $r+q$ 个源/目标城市对都有唯一的最短路径。

对每个测试用例，对于每个查询输出一行，包含查询的源城市和目标城市，以及有关配送时间的最佳下界和上界。 **评测过程会忽略至小数点后两位的浮点误差。** **本翻译由 AI 自动生成**