#P3253. 改编

    ID: 2438 传统题 1000ms 512MiB 尝试: 21 已通过: 15 难度: 7 上传者: 标签>难度分类提高+/省选-概率与期望吸收链首次步分析动态规划期望方程构造与建模对称性分析线性代数与代数矩阵求逆Gauss–Jordan 消元主元选择CF2300

改编

改编

题目描述

大图书馆是一张有 nn 个顶点和 mm 条边的无向图。Marisa 和 Patchouli 最初分别位于顶点 XX、YY。每分钟,两人同时独立行动。处于顶点 ii 时,有 pip_i 的概率原地停留,有 1−pi1-p_i 的概率移动。移动时,从该顶点的所有邻点中等概率选择一个。

两人处于同一个顶点时立即停止。如果两人在同一条边上迎面经过,他们只会错过。若一开始就处于同一个顶点,走过的长度为 00。

图的连边和每个顶点的停留概率在所有询问中相同。每次询问单独给出各边长度及两人的起点,求他们在相遇前走过的路径长度之和的期望。

输入格式

第一行包含三个正整数 n,m,tn,m,t,表示顶点数、边数和询问数。

接下来 mm 行,每行两个顶点编号 a,ba,b,表示一条连接 aa 与 bb 的无向边。顶点从 11 到 nn 编号,边按给出顺序编号。

接下来一行包含 nn 个实数 p1,…,pnp_1,\ldots,p_n。

接下来 tt 行,每行先给出 mm 个整数,按顺序表示各条边在本次询问中的长度,再给出两个顶点编号 X,YX,Y。

输出格式

对每次询问输出一行实数,表示两人相遇前走过的路径长度之和的期望,保留两位小数。

样例

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

数据规模与约定

1≤n≤221\le n\le22,t≤500t\le500。对每个顶点,0.01≤pi≤0.990.01\le p_i\le0.99。边长在 [1,106][1,10^{6}] 内。图连通,且没有自环和重边。

BZOJ 归档题面