UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3253. 改编

统计 下载数据

Description

A:“大图书馆是一张n点m边的无向图,Marisa和Patchouli初始分别位于点X和点Y。每分钟,两人都有一次行动机
会:当某人位于点i时,有pi的概率停留在点i,有1-pi的概率等概率随机选择点i的相邻节点之一并前往。若两人
在某个点相遇,则行动停止。值得注意的是,两人在边上是不会相遇的,所以两人在某条边上迎面经过,只会错过
而不会相遇。两人同时行动,求两人在每个点相遇的概率。”
B:“这不是CodeForces 113 D吗,还原度真高啊喂。”
A:“那改一改……不求在每个点相遇的概率,改成求两人在相遇前走过的路径长度期望和。”
B:“大同小异。”
A:“大图书馆的m条边的长度是可以修改的,两人的初始位置也是。”
B:“你不要让Patchouli太累了……”

Input

第一行三个正整数n、m、t,表示点数、边数和数据组数
以下m行,每行2个整数a,b,表示点a和点b之间有一条无向边
接下来一行n个实数表示pi,保证0.01<=pi<=0.99
以下t行,每行前m个整数表示每条边的长度,最后2个整数表示初始位置点X和点Y
1<=n<=22,t<=500,1<=边权<=1000000
保证图是无重边和自环的连通图

Output

共t行,每行一个实数表示两人在相遇前走过的路径长度期望和(保留2位小数)

Sample Input

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

Sample Output

4.67
10.67

Hint

Source