题目描述

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

输出格式

共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

提示

对于100%的数据，1<=n<=22,t<=500，1<=边权<=1000000 保证图是无重边和自环的连通图

题目来源

高斯消元法