2018 团体程序设计天梯赛分组赛暨 3 月内部选拔

C2. 又是地铁

单点时限: 1.0 sec

内存限制: 256 MB

如果你参加过去年同期的选拔赛的话,你一定还记得某一道地铁题。某出题人为了增大选手的代码量不惜一切代价,搞了一大堆复杂的条件。最后大家纷纷卡在了地铁题的前一道题上,地铁题根本没人做。。。

然而天梯赛考了一道公交车(意想不到的押中)。。。

于是某出题人决定再考一次地铁。为了鼓励大家做这个题,出题人对题目进行了简化。

众所周知,从一个地铁站到另一个地铁站的流程是这样的:进站 —— 等待 —— 坐车 —— 换乘 —— 等待 —— 坐车 —— 换乘 —— …… —— 坐车 —— 出站。我们省去进站和出站的时间,剩下的时间总共由三部分组成:

  • 等待时间:显然和发车间隔有关。
  • 换乘时间:为了方便起见,我们假设在同一个换乘车站,任意两条线路换乘所需要的时间是服从某一固定 $\mu$ 的正态分布;在计算期望时,你可以认为换乘时间就是常数 $\mu$(该常数仅与车站有关)。
  • 在地铁上的时间。

现在给定一张地铁线路图(上海的地铁线路图),询问从起点到终点的最佳线路的期望时间(期望的最小值)。

输入格式

第一行一个整数 $n,p,q$ 分别表示地铁线路数量,地铁站总数,询问数 ($n \approx 15, p \approx 300, 1 \le q \le 10^5$)。地铁站用从 $1$ 开始的自然数编号。

接下来一行 $p$ 个整数 $\mu_1, \mu_2, \ldots, \mu_p$。$\mu_i$ ($1 \le \mu_i \le 5$) 表示第 $i$ 个车站换乘需要的时间服从 $N(\mu_i, \sigma^2)$。由于不需要算方差,所以 $\sigma$ 不会出现在输入中。所有车站都有一个换乘时间,即使它根本不是换乘车站。

接下来 $n$ 行,每行一条地铁线路,以如下的格式输入:

$m \ interval \ stop_1 \ time_{1,2} \ stop_2 \cdots stop_{m-1} \ time_{m-1,m} \ stop_m$

$m$ ($2 \le m \le 100$) 表示经停站数,$interval$ ($1 \le interval \le 20$) 是一个正整数,表示该条线路的发车间隔。地铁线路是双向的。$time_{i,i+1}$ ($1 \le time_{i,i+1} \le 20$) 也是正整数,表示 $stop_i,stop_{i+1}$ 之间所需要的时间(来回时间相等)。$stop_i$ ($1 \le stop_i \le p$) 是车站的唯一编号。两条线路中如果出现编号相同的车站就视为同一车站,可以换乘。同一个车站最多有 $4$ 条线换乘。

接下来 $q$ 行,每行一个询问 $s,t$ ($1 \le s, t \le p, s \ne t$),表示从 $s$ 到 $t$ 所需要的时间,$s$ 和 $t$ 是地铁站的编号,保证在上面出现过。并保证可达。

题目数据是真实的,去掉了环线和支线的情况。不会出现边界情况来恶心你。

输出格式

输出 $q$ 行,每行一个时间,要求与答案的相对误差不超过 $10^{-6}$。

上海地铁是连通的。保证可达。

样例

Input
1 3 6
2 3 3
3 4 1 5 2 7 3
1 2
1 3
2 1
2 3
3 1
3 2
Output
7.000000000
14.000000000
7.000000000
9.000000000
14.000000000
9.000000000
Input
3 4 3
2 1 1 1
3 4 1 9 2 5 3
2 2 2 1 4
2 3 1 1 4
1 3
1 4
4 3
Output
13.500000000
2.500000000
10.000000000