DZY Loves Games

题意翻译

## 题目描述: DZY开始玩一种古老的游戏。 在这个游戏中,他将处于一个巨大的迷宫中,迷宫中有n个房间,由m条走廊相连接(每个走廊允许向两个方向移动)。你可以假设所有房间都直接或间接与走廊相连。 DZY迷失在迷宫中。 目前他在第一个房间,有k条命。 他的行为如下: - 首先,他将随机挑选一条能走出当前所在房间的走廊。 每个走廊被挑选的概率相同。 - 然后,他会穿过走廊,然后重复这个过程。 有些房间里面有陷阱。 第一个房间肯定没有陷阱,但第n个房间肯定有一个陷阱。 每当DZY进入其中一个房间时,他就会失去一条命。 如果他进入第n个房间,只有2条命的话,首先他将失去一条生命,但随后他将进入奖金回合。 他想知道他进入奖金回合的可能性有多大。 ## 输入输出: ### 输入格式: 第一行包含三个整数 n,m,k(2<=n<=500;1<=m<=10^5;2<=k<=10^9)。 第二行包含 n个整数,都是 0 或 1 ,第i个数为 1 则代表第 i 个房间有陷阱,是 0 则没有。(有陷阱的房间的总数不超过 101 个)输入保证第 1 个房间无陷阱,第 n 个房间有陷阱 然后是m行,每行有两个整数 u[i] 与 v[i] (1<=u[i],v[i]<=n ; u[i]≠v[i]) 表示第i条走廊连接了房间 u[i] 与 v[i] 。保证整个走廊系统是连通的。 ### 输出格式: 只输出一个实数,即DZY进入奖金回合的概率,误差不超过 10^-4

题目描述

Today DZY begins to play an old game. In this game, he is in a big maze with $ n $ rooms connected by $ m $ corridors (each corridor allows to move in both directions). You can assume that all the rooms are connected with corridors directly or indirectly. DZY has got lost in the maze. Currently he is in the first room and has $ k $ lives. He will act like the follows: - Firstly he will randomly pick one of the corridors going from his current room. Each outgoing corridor has the same probability to be picked. - Then he will go through the corridor and then the process repeats. There are some rooms which have traps in them. The first room definitely has no trap, the $ n $ -th room definitely has a trap. Each time DZY enters one of these rooms, he will lost one life. Now, DZY knows that if he enters the $ n $ -th room with exactly 2 lives, firstly he will lost one live, but then he will open a bonus round. He wants to know the probability for him to open the bonus round. Please, help him.

输入输出格式

输入格式


The first line contains three integers $ n,m,k (2<=n<=500; 1<=m<=10^{5}; 2<=k<=10^{9}) $ . The second line contains $ n $ integers, each of them is either $ 0 $ or $ 1 $ . If the $ i $ -th number is $ 1 $ , then the $ i $ -th room has a trap, otherwise it has not a trap. Please note, that the number of rooms with a trap is no more than $ 101 $ . It is guaranteed that the first room has no trap, and the $ n $ -th room has a trap. Then $ m $ lines follows. Each of them contains two integers $ u_{i},v_{i} (1<=u_{i},v_{i}<=n; u_{i}≠v_{i}) $ , meaning that current corridor connects two rooms $ u_{i} $ and $ v_{i} $ . It is guaranteed that the corridor system is connected.

输出格式


Print the only real number — the probability for DZY to open the bonus round. The answer will be considered correct if its relative or absolute error doesn't exceed $ 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