JC的小苹果
时间限制：15s 空间限制：256MB
题目描述
让我们继续JC和DZY的故事。
“你是我的小丫小苹果，怎么爱你都不嫌多！”
“点亮我生命的火，火火火火火！”
话说JC历经艰辛来到了城市B，但是由于他的疏忽DZY偷走了他的小苹果！没有小苹果怎么听歌！他发现邪恶的DZY把他的小苹果藏在了一个迷宫里。JC在经历了之前的战斗后他还剩下hp点血。开始JC在1号点，他的小苹果在N号点。DZY在一些点里放了怪兽。当JC每次遇到位置在i的怪兽时他会损失Ai点血。当JC的血小于等于0时他就会被自动弹出迷宫并且再也无法进入。
但是JC迷路了，他每次只能从当前所在点出发等概率的选择一条道路走。所有道路都是双向的，一共有m条，怪兽无法被杀死。现在JC想知道他找到他的小苹果的概率。
P.S.大家都知道这个系列是提高组模拟赛，所以这是一道送分题balabala
输入格式
第一行三个整数表示n，m，hp。接下来一行整数，第i个表示jc到第i个点要损失的血量。保证第1个和n个数为0。接下来m行每行两个整数a，b表示ab间有一条无向边。
输出格式
仅一行，表示JC找到他的小苹果的期望概率，保留八位小数。
样例输入
3 3 2
0 1 0
1 2
1 3
2 3
样例输出
0.87500000
提示
对于100%的数据 2<=n<=150，hp<=10000，m<=5000，保证图联通。
题目来源
By JRY