Description

5 秒，1024 MB

Ubol Narongdid 是一家名为 Special D-Liver-E 的新兴初创公司的创始人。她想要垄断普吉岛地区医院之间的器官隔夜递送市场。为了安排计划，准确估计执行这些递送所需的时间非常重要。已经在一些医院之间进行了多次递送，因此这些医院对之间的递送时间是已知的。公司目前有软件来估计其他（尚未旅行过的）行程的时间，但到目前为止，所有的估计都非常不准确。

你被要求提出一种方法来改善这些估计。你可以使用以下信息：1）普吉岛地区每对城市之间连接道路的长度（以公里为单位），以及 2）一组先前执行的各种递送的时间（以分钟为单位）。

你知道道路是单向的，每条道路都有一个固定的速度限制，介于 $30$ 到 $60$ 公里每小时之间。速度限制是实数，不必是整数。你还知道递送卡车总是选择最小化行驶距离的路线，并且在每条道路上总是以等于该道路速度限制的恒定速度行驶。因此，例如，如果某次旅行是 $50$ 公里，所需时间在 $50$ 到 $100$ 分钟之间（包括边界），在没有其他信息的情况下。但你确实有其他信息，即先前递送的时间。你需要利用这些信息来产生尽可能好的估计。

Input Format

输入以一行包含一个整数 $n$ ($1 \le n \leq 30$) 开始，表示城市的数量，编号为 $0$ 到 $n-1$。之后是 $n$ 行，每行包含 $n$ 个整数，指定城市之间的距离（以公里为单位）：第 $i$ 行的第 $j$ 个值表示从城市 $i$ 直接到城市 $j$ 的距离。当两个城市之间没有直接连接的道路时，值为 $-1$，从任何城市到自身的距离总是 $0$；所有其他距离为正数且最多为 $1\, 000$。最多有 $100$ 条道路。

接下来是一行包含一个整数 $r$ ($1 \le r \leq 100$)，表示先前执行的路线数量。接下来的 $r$ 行每行包含三个整数 $s$、$d$ 和 $t$，其中 $s$ 和 $d$ 是起始和目的城市，$t$ 是从 $s$ 到 $d$ 的递送所花费的时间，以分钟为单位。

最后是一行包含一个整数 $q$ ($1 \le q \leq 100$)，表示未来递送查询的数量。接下来的 $q$ 行每行包含两个整数 $s$ 和 $d$，给出查询的起始和目的城市。

你可以假设输入中的每对 $r+q$ 起始/目的地对都有唯一的最小距离路线。

Output Format

对于每个查询，显示一行，包含该查询的起始和目的城市，后跟对旅行时间估计的最佳低和高界限，精确到绝对或相对误差为 $10^{-6}$。

3
0 50 -1
55 0 40
-1 40 0
1
0 2 120
3
0 1
1 2
1 0

0 1 50.0 80.0
1 2 40.0 70.0
1 0 55.0 110.0

Hint

时间限制：5000 毫秒，内存限制：1048576 kB。

国际大学生程序设计竞赛（ACM-ICPC）世界总决赛 2016。

题面翻译由 ChatGPT-4o 提供。