3253. 改编
#3253. 改编
题目描述
A:"大图书馆是一张n点m边的无向图，Marisa和Patchouli初始分别位于点X和点Y。每分钟，两人都有一次行动机
会：当某人位于点i时，有pi的概率停留在点i，有1-pi的概率等概率随机选择点i的相邻节点之一并前往。若两人
在某个点相遇，则行动停止。值得注意的是，两人在边上是不会相遇的，所以两人在某条边上迎面经过，只会错过
而不会相遇。两人同时行动，求两人在每个点相遇的概率。"
B："这不是CodeForces 113 D吗，还原度真高啊喂。"
A："那改一改……不求在每个点相遇的概率，改成求两人在相遇前走过的路径长度期望和。"
B："大同小异。"
A："大图书馆的m条边的长度是可以修改的，两人的初始位置也是。"
B："你不要让Patchouli太累了……"
输入格式
第一行三个正整数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
保证图是无重边和自环的连通图
输出格式
共t行，每行一个实数表示两人在相遇前走过的路径长度期望和（保留2位小数）
样例
样例输入
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