单点时限: 1.0 sec
内存限制: 256 MB
如果你参加过去年同期的选拔赛的话,你一定还记得某一道地铁题。某出题人为了增大选手的代码量不惜一切代价,搞了一大堆复杂的条件。最后大家纷纷卡在了地铁题的前一道题上,地铁题根本没人做。。。
然而天梯赛考了一道公交车(意想不到的押中)。。。
于是某出题人决定再考一次地铁。为了鼓励大家做这个题,出题人对题目进行了简化。
众所周知,从一个地铁站到另一个地铁站的流程是这样的:进站 —— 等待 —— 坐车 —— 换乘 —— 等待 —— 坐车 —— 换乘 —— …… —— 坐车 —— 出站。我们省去进站和出站的时间,剩下的时间总共由三部分组成:
现在给定一张地铁线路图(上海的地铁线路图),询问从起点到终点的最佳线路的期望时间(期望的最小值)。
第一行一个整数 $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}$。
上海地铁是连通的。保证可达。
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
7.000000000 14.000000000 7.000000000 9.000000000 14.000000000 9.000000000
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
13.500000000 2.500000000 10.000000000