题目描述

有一些城市，你知道连接每一对城市之间的路的长度，而且路都是单向的。每条路都有固定的30码至60码的限速（ 可以是小数）。运输货车一定会沿着最短路行进，而且在每条路上会始终以最高限速行驶。因此，在不知道其余信 息的情况下，如果一次行程长度为50km，则它需要花的时间在50至100分钟之间。但是你有其余的信息--例如之前 的行程所花的时间。请使用这些信息给出最准确的估算。

输入格式

第一行一个数n(1 ≤ n ≤ 30)，表示城市数量。城市从0标号到n-1。 之后n行，每行n个数，表示城市之间的路程长度：第i行第j个数表示从城市i到城市j的直接距离（km），-1表示没 有道路直接连接这两个城市。城市到自己的距离一定是0；其它的距离都为正数且不超过1000。最多只会有100条路 。 接下来一行一个数r(1 ≤ r ≤ 100)表示已经运送过的路线数量。 接下来r行，每行三个整数s、d、t，表示从城市s到城市d花了t分钟。 最后一行一个数q(1 ≤ q ≤ 100)表示询问数量。 接下来q行每行2个数s和d表示运送的起始地点和目的地。 你可以认为这r+q对起始地点和目的地之间都有一条唯一的最短路径。

输出格式

对于每个询问输出一行，先输出该询问的起始地点和目的地 然后输出估计行程时间的最小值和最大值，绝对或相对误差在1e-6以内算作正确。

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

0 1 50.000000000 50.000000000
1 2 40.000000000 40.000000000
1 0 55.000000000 110.000000000

提示

没有写明提示

题目来源

鸣谢Shimakaze提供译文