問題文
高桥队长的任务是从基地所在海域向最终目的地海域推进。
高桥队长将按以下顺序行动。
- 航路選択
- 选择行军路线。有一条海路可以让你从当前海域移动到不同的海域。 1 如果这本书也不存在,4 离开该区域。
- 进一步地,如果从当前海域到不同海域存在多条航线,则由于有人阴谋而以等概率选择一条航线。
- 例如,有一条从基地所在海域到其他海域的海路。 4 如果存在,每个 它被选择的概率为 25% 。
- 進軍
- 根据选择的路线穿过海域。
- 戦闘
- 前进海域 i 一艘敌舰正在等待,一场战斗随之而来。
- 离开基地时,高桥舰长率领的战舰体力为 H ,并且战舰的体力通过战斗而增加。 减少 D_i 。
- 战舰体力强度 0 如果低于,战舰就会沉没。
- 当军舰沉没时,高桥舰长变得非常失望,无法再出击。
絶対に沈没させてはいけない。 - 虽然基地所在海域不会发生战斗,但最终目的地所在海域肯定会发生战斗。
- 返回地区出发或路线选择
- 离开海域意味着返回基地所在海域。
- 离开该区域时,战舰剩余生命值为 C ,H-C 体力恢复需要时间。
1,2,3,4每个周期的时间
仅使用 1 。关于海域及航线
- 现在,N 海域和 有 M 路线。
- 这些 所有 M 路线都是单向的。
你是高桥队长的参谋,你的工作是找出高桥队长在战斗中存活下来的预期时间,如果他采取行动尽量减少消耗的时间。
如果高桥队长无论如何都无法完成他的任务,
-1。但是,要输出的预期值为 未给出大于 10^6 的输入。
入力
N M H f_1 t_1 f_2 t_2 : f_M t_M D_1 D_2 : D_N
- 1 行是一个整数,代表海域数量 N (2≦N≦100),表示路由数量的整数 M (0≦M≦N * (N - 1) / 2),一个整数,表示出发时车队的健康状况。 H (1≦H≦100) 由半角空格分隔。
- 军事基地所在海域为 1 ,最终目的地是海域。 N 。
- 2 在 M 行是 代表第 i 条路线。代表要移动的海洋区域的整数 f_i (1≦f_i≦N),一个整数,表示要移动到的海洋区域 t_i (1≦t_i≦N) 用空格分隔。
- f_i<t_i 有保证。
- 2+M 在 N 行是 代表第i 代表海域战斗中受到伤害的整数。 D_i (0≦D_i≦100) 在一行中给出。
- D_1 的值始终为 0 (这是军事基地所在海域)。
- 要输出的预期值为 请注意,没有给出大于 10^6 的输入。
出力
输出至少具有绝对误差和相对误差之一。 10^{-6} 如果以下,允许。
另外,如果高桥队长无论如何都无法完成他的任务,
-1。请在输出末尾添加换行符。
入力例 1
6 6 8 1 2 1 3 2 4 3 5 4 6 5 6 0 1 1 2 3 4
出力例 1
5.0
- 有一个军事基地 1 是最终目的地。 直到 6 直到,2 有一条路线。
- 1 -> 2 -> 4 -> 6
- 选择该路线的概率为 50% 。
- 战舰在此航线上受到的伤害为 0+1+2+4=7 。
- 该路线消耗的时间为 由于只有 3 次,3 。
- 1 -> 3 -> 5 -> 6
- 选择该路线的概率为 50% 。
- 战舰在此航线上受到的伤害为 0+1+3+4=8 。
- 出发时战舰体力为 8 因此,这条路线会让你沉沦。
- 高桥船长,为了避免沉没, 选择在 3 战斗结束时离开该区域。
- 该路线消耗的时间为 由于只有 1 次 + 体力恢复所需时间 = 1+1=2 。
- 50% 和时间 使用 2 返回基地。
- 然后, 1 -> 2 -> 4 -> 6 的选择概率为 50% 和时间 使用 3 到达您的最终目的地。
- 换句话说, 概率为25% 的时间 使用 5 到达最终目的地。
- 12.5% 的时间 使用 7 到达最终目的地。
- 6.25% 的时间 使用 9 到达最终目的地。
- 由上可知,要查找的期望值是 来自 3*0.5+5*0.25+7*0.125+...=5 。
1 撤退后1->2->4->6
1 -> 3 -> 5 -> 6 的选择概率为
2 撤退后1->2->4->6
1 -> 3 -> 5 -> 6 的选择概率为
3 撤退后1->2->4->6
1 -> 3 -> 5 -> 6 的选择概率为
入力例 2
3 2 5 1 2 1 3 0 5 1
出力例 2
-1
- 有一个军事基地 1 ,2 有一条路线。
- 1 -> 2
- 选择该路线的概率为 50% 。
- 战舰在此航线上受到的伤害为 0+5=5 。
- 出发时战舰体力为 5 因此,这条路线会让你沉沦。
- 1 -> 3
- 选择该路线的概率为 50% 。
- 战舰在此航线上受到的伤害为 0+1=1 。
- 该路线消耗的时间为 由于只有 1 次,1 。
- 这样,如果选择路线1 -> 3,您将能够到达最终目的地,但仍有可能选择路线1 -> 2,您将无法从基地前进。
- 因此,
输出
-1。 与
入力例 3
3 2 6 1 2 1 3 0 5 1
出力例 3
7
- 入力例 2 是同一张地图,但以体力为例输入。 与 2 相比增加了 1。
- 为此,部队从军事基地进军,侵入海域。 即使移动到 2 ,伤害也会 收到 5后即可离开该区域。
- 因此,高桥队长一定能够到达他的最终目的地。
入力例 4
9 13 4 1 2 1 3 2 4 2 5 2 7 3 5 3 6 4 7 5 8 6 8 7 8 7 9 8 9 0 1 1 1 1 1 1 1 1
出力例 4
36.9999999999999
- 只能通过路线 1 -> 2 -> 7 -> 9 到达最终目的地。
- 如果进入其他区域,最好立即撤退。
- 期望值为 37不过,由于输出中允许有错误,所以如上所示的输出没有问题。