← 返回题目列表

AtCoder · arc016_4

D. 战舰游戏

中文机器翻译题面 查看原题

問題文

高桥是队长。
高桥队长的任务是从基地所在海域向最终目的地海域推进。
高桥队长将按以下顺序行动。
  1. 航路選択
    • 选择行军路线。有一条海路可以让你从当前海域移动到不同的海域。 1 如果这本书也不存在,4 离开该区域。
    • 进一步地,如果从当前海域到不同海域存在多条航线,则由于有人阴谋而以等概率选择一条航线。
      • 例如,有一条从基地所在海域到其他海域的海路。 4 如果存在,每个 它被选择的概率为 25% 。
  2. 進軍
    • 根据选择的路线穿过海域。
  3. 戦闘
    • 前进海域 i 一艘敌舰正在等待,一场战斗随之而来。
    • 离开基地时,高桥舰长率领的战舰体力为 H ,并且战舰的体力通过战斗而增加。 减少 D_i 。
    • 战舰体力强度 0 如果低于,战舰就会沉没。
    • 当军舰沉没时,高桥舰长变得非常失望,无法再出击。絶対に沈没させてはいけない。
    • 虽然基地所在海域不会发生战斗,但最终目的地所在海域肯定会发生战斗。
  4. 返回地区出发或路线选择
    • 离开海域意味着返回基地所在海域。
    • 离开该区域时,战舰剩余生命值为 C ,H-C 体力恢复需要时间。
上記1,2,3,4每个周期的时间 仅使用 1 。

关于海域及航线
  • 现在,N 海域和 有 M 路线。
  • 这些 所有 M 路线都是单向的。
因此,任何不同海域 在 A,B 中,有 1 利用这条路线探索海域。 来自 A 的海域 前往 B ,开放海域。 您无法移动到 B 的海域 前往 A 。

你是高桥队长的参谋,你的工作是找出高桥队长在战斗中存活下来的预期时间,如果他采取行动尽量减少消耗的时间。
如果高桥队长无论如何都无法完成他的任务,-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. 1 行是一个整数,代表海域数量 N (2≦N≦100),表示路由数量的整数 M (0≦M≦N * (N - 1) / 2),一个整数,表示出发时车队的健康状况。 H (1≦H≦100) 由半角空格分隔。
    • 军事基地所在海域为 1 ,最终目的地是海域。 N 。
  2. 2 在 M 行是 代表第 i 条路线。代表要移动的海洋区域的整数 f_i (1≦f_i≦N),一个整数,表示要移动到的海洋区域 t_i (1≦t_i≦N) 用空格分隔。
    • f_i<t_i 有保证。
  3. 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. 1 -> 2 -> 4 -> 6
      • 选择该路线的概率为 50% 。
      • 战舰在此航线上受到的伤害为 0+1+2+4=7 。
      • 该路线消耗的时间为 由于只有 3 次,3 。
    2. 1 -> 3 -> 5 -> 6
      • 选择该路线的概率为 50% 。
      • 战舰在此航线上受到的伤害为 0+1+3+4=8 。
      • 出发时战舰体力为 8 因此,这条路线会让你沉沦。
      • 高桥船长,为了避免沉没, 选择在 3 战斗结束时离开该区域。
      • 该路线消耗的时间为 由于只有 1 次 + 体力恢复所需时间 = 1+1=2 。
    1 -> 3 -> 5 -> 6 1 撤退后1->2->4->6 1 -> 3 -> 5 -> 6 的选择概率为
    • 50% 和时间 使用 2 返回基地。
    • 然后, 1 -> 2 -> 4 -> 6 的选择概率为 50% 和时间 使用 3 到达您的最终目的地。
    • 换句话说, 概率为25% 的时间 使用 5 到达最终目的地。
    1 -> 3 -> 5 -> 6 2 撤退后1->2->4->6 1 -> 3 -> 5 -> 6 的选择概率为
    • 12.5% 的时间 使用 7 到达最终目的地。
    1 -> 3 -> 5 -> 6 3 撤退后1->2->4->6 1 -> 3 -> 5 -> 6 的选择概率为
    • 6.25% 的时间 使用 9 到达最终目的地。
  • 由上可知,要查找的期望值是 来自 3*0.5+5*0.25+7*0.125+...=5 。

入力例 2

3 2 5
1 2
1 3
0
5
1

出力例 2

-1
  • 有一个军事基地 1 ,2 有一条路线。
    1. 1 -> 2
      • 选择该路线的概率为 50% 。
      • 战舰在此航线上受到的伤害为 0+5=5 。
      • 出发时战舰体力为 5 因此,这条路线会让你沉沦。
    2. 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不过,由于输出中允许有错误,所以如上所示的输出没有问题。