#P3640. JC的小苹果

    ID: 589 传统题 3000ms 256MiB 尝试: 745 已通过: 203 难度: 7 上传者: 标签>难度分类提高+/省选-动态规划概率 DP概率与期望随机游走线性代数与代数Gauss–Jordan 消元矩阵求逆矩阵乘法CF2300ByJRY

JC的小苹果

JC 的小苹果

题目背景

JC 来到城市 B 后,一不留神被 DZY 偷走了小苹果。他得把小苹果找回来才能继续听歌。

题目描述

DZY 把 JC 的小苹果藏进了迷宫。JC 带着 hphp 点生命值,从 11 号地点出发。小苹果在 nn 号地点。

迷宫中有 mm 条双向道路。JC 在每一步都从当前地点相连的道路中等概率选一条,沿它到达下一处地点。部分地点有怪兽。每次进入第 ii 个地点时,JC 会损失 aia_i 点生命值。怪兽不会被消灭,重复进入仍会扣除生命值。若生命值降到 00 或以下,JC 会被弹出迷宫,无法再次进入。

求 JC 在被弹出前到达 nn 号地点的概率。

输入格式

第一行三个整数 n,m,hpn,m,hp,分别表示地点数、道路条数与初始生命值。

第二行 nn 个非负整数 a1,…,ana_1,\ldots,a_n,其中 aia_i 是进入第 ii 个地点损失的生命值,a1=an=0a_1=a_n=0。

接下来 mm 行,每行两个整数 u,vu,v,表示一条连接两处地点的双向道路。任意两条道路即使端点相同也分别参与随机选择。一条两端在同一地点的道路被选中后,会再次进入该地点。

输出格式

输出一行一个数,表示成功找到小苹果的概率,保留八位小数。

3 3 2
0 1 0
1 2
1 3
2 3
0.87500000

数据范围

2≤n≤1502\le n\le 150,hp≤10000hp\le 10000,m≤5000m\le 5000,迷宫的图连通。

数据比例 限制
10%10\% n=5n=5,hp=1hp=1
30%30\% n≤20n\le 20,hp≤5hp\le 5
60%60\% n≤50n\le 50,hp≤10000hp\le 10000
另有 10%10\% 除起点和终点之外,各地点的 aia_i 均为正