← 返回题目列表

Codeforces · 113/D

D. 博物馆

中文机器翻译题面 查看原题

有一天,当 Petya 和他的朋友 Vasya 进行众多旅行之一时,他们决定参观一座博物馆城堡。博物馆有一个特定的形状:它由 n 个房间组成,每个房间与 m 个走廊相连,以便人们可以从任何其他房间进入任何房间。

两个朋友在博物馆里走了一会儿后,他们决定分开观看他们各自感兴趣的艺术品。他们同意下午六点在其中一间房间见面。然而,他们忘记了一件很重要的事情:他们没有指定见面地点,到了时间,他们就开始在博物馆里奔波寻找对方(他们无法互相打电话,因为漫游导致通话费用飙升)。

然而,尽管如此匆忙,他们还是无法获得足够的艺术品,这就是为什么他们每个人都有以下策略:每一分钟他都会决定去哪里 - 概率 pi 他在这一分钟内不会移动到任何其他地方(即他留在房间里)。他以 1 - pi 的概率等概率选择相邻的房间之一并沿着走廊前往那里。这里 i 是当前房间的序号。古代的建筑造价昂贵,所以每条走廊都连接着两个不同的房间,而任何两个房间之间最多只有一条走廊。

男孩们同时行动。由于走廊很暗,不可能在那里见面;然而,一个人可以沿着走廊向两个方向行走(此外,两个男孩可以同时穿过同一条走廊而不会相遇)。男孩们就这样行事,直到他们见面。更正式地说,这两个朋友在某个时刻决定出现在同一个房间时见面。

对于每个房间,考虑到下午 6 点,求男孩们在那里见面的概率。它们分别位于a室和b室。

输入

第一行包含四个整数:n(1≤n≤22),代表房间数; m $$( n - 1 \leq m \leq \frac { n ( n - 1 ) } { 2 } )$$,代表走廊数量; a,b(1≤a,b≤n),分别代表Petya和Vasya的起始房间号。

接下来的 m 行包含数字对——由走廊连接的房间的数量。接下来的 n 行包含概率 pi (0.01 ≤ pi ≤ 0.99),精确到小数点后四位数字 - 留在房间 i 的概率。

确保每个房间都可以通过走廊到达其他每个房间。

输出

在唯一一行打印 n 个空格分隔的数字中,第 i 个数字应该代表朋友在第 i 个房间相遇的概率,绝对或相对误差不超过 10 - 6。

示例

输入 #1

2 1 1 2
1 2
0.5
0.5

输出 #1

0.5000000000 0.5000000000

输入 #2

4 4 1 2
1 2
2 3
3 4
4 1
0.5
0.5
0.5
0.5

输出 #2

0.3333333333 0.3333333333 0.1666666667 0.1666666667

注意

在第一个示例中,博物馆是对称的。这意味着在 1 号房间和 2 号房间相遇的概率相等。它们的总和等于一。因此,每个概率等于 0.5。