#P3253. 改编
改编
改编
题目描述
大图书馆是一张有 个顶点和 条边的无向图。Marisa 和 Patchouli 最初分别位于顶点 、。每分钟,两人同时独立行动。处于顶点 时,有 的概率原地停留,有 的概率移动。移动时,从该顶点的所有邻点中等概率选择一个。
两人处于同一个顶点时立即停止。如果两人在同一条边上迎面经过,他们只会错过。若一开始就处于同一个顶点,走过的长度为 。
图的连边和每个顶点的停留概率在所有询问中相同。每次询问单独给出各边长度及两人的起点,求他们在相遇前走过的路径长度之和的期望。
输入格式
第一行包含三个正整数 ,表示顶点数、边数和询问数。
接下来 行,每行两个顶点编号 ,表示一条连接 与 的无向边。顶点从 到 编号,边按给出顺序编号。
接下来一行包含 个实数 。
接下来 行,每行先给出 个整数,按顺序表示各条边在本次询问中的长度,再给出两个顶点编号 。
输出格式
对每次询问输出一行实数,表示两人相遇前走过的路径长度之和的期望,保留两位小数。
样例
4 4 2
1 2
2 3
3 4
1 4
0.5 0.5 0.5 0.5
1 1 1 1 1 2
2 2 2 2 1 3
4.67
10.67
数据规模与约定
,。对每个顶点,。边长在 内。图连通,且没有自环和重边。