#P3640. JC的小苹果
JC的小苹果
JC 的小苹果
题目背景
JC 来到城市 B 后,一不留神被 DZY 偷走了小苹果。他得把小苹果找回来才能继续听歌。
题目描述
DZY 把 JC 的小苹果藏进了迷宫。JC 带着 点生命值,从 号地点出发。小苹果在 号地点。
迷宫中有 条双向道路。JC 在每一步都从当前地点相连的道路中等概率选一条,沿它到达下一处地点。部分地点有怪兽。每次进入第 个地点时,JC 会损失 点生命值。怪兽不会被消灭,重复进入仍会扣除生命值。若生命值降到 或以下,JC 会被弹出迷宫,无法再次进入。
求 JC 在被弹出前到达 号地点的概率。
输入格式
第一行三个整数 ,分别表示地点数、道路条数与初始生命值。
第二行 个非负整数 ,其中 是进入第 个地点损失的生命值,。
接下来 行,每行两个整数 ,表示一条连接两处地点的双向道路。任意两条道路即使端点相同也分别参与随机选择。一条两端在同一地点的道路被选中后,会再次进入该地点。
输出格式
输出一行一个数,表示成功找到小苹果的概率,保留八位小数。
3 3 2
0 1 0
1 2
1 3
2 3
0.87500000
数据范围
,,,迷宫的图连通。
| 数据比例 | 限制 |
|---|---|
| , | |
| , | |
| , | |
| 另有 | 除起点和终点之外,各地点的 均为正 |