← 返回题目列表

Codeforces · 446/D

D. DZY 爱游戏

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

今天DZY开始玩一个老游戏。在这个游戏中,他处于一个大迷宫中,有n个房间,由m条走廊连接(每个走廊允许双向移动)。您可以假设所有房间都直接或间接与走廊相连。

DZY 在迷宫中迷路了。目前他在第一个房间并且有 k 条命。他的行为如下:

- 首先他会随机选择一条从他当前房间出发的走廊。每个外出走廊都有相同的概率被选中。
- 然后他将穿过走廊,然后重复该过程。

有些房间里有陷阱。第一个房间肯定没有陷阱,第n个房间肯定有陷阱。 DZY 每次进入这些房间之一,就会失去一条生命。现在,DZY 知道,如果他进入第 n 个房间时正好有 2 条生命,首先他会失去一条生命,但随后他会打开一个奖励回合。他想知道他开启奖金回合的概率。请帮助他。

输入

第一行包含三个整数 n、m、k(2 ≤ n ≤ 500;1 ≤ m ≤ 105;2 ≤ k ≤ 109)。

第二行包含n个整数,每个整数要么是0,要么是1。如果第i个数字是1,则第i个房间有陷阱,否则没有陷阱。请注意,有陷阱的房间数量不超过101个。保证第一个房间没有陷阱,第n个房间有陷阱。

接下来是 m 行。它们每个都包含两个整数 ui, vi (1 ≤ ui, vi ≤ n; ui ≠ vi),表示当前走廊连接两个房间 ui 和 vi。保证了走廊系统的连通性。

输出

打印唯一的实数——DZY 开启奖金回合的概率。如果答案的相对误差或绝对误差不超过 10 - 4,则认为答案是正确的。

示例

输入 #1

5 5 3
0 0 1 0 1
1 2
2 3
3 4
4 5
1 2

输出 #1

0.25000000

输入 #2

3 2 2
0 1 1
1 2
2 3

输出 #2

-0.00000000

输入 #3

2 1 3
0 1
1 2

输出 #3

1.00000000