D - 軍艦ゲーム Editorial /

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

高橋君は艦長である。
高橋艦長の任務は、鎮守府のある海域から最終目的地となる海域へ進軍することである。
高橋艦長は次の順序で行動する。
  1. 航路選択
    • 進軍する航路を選択する。現在の海域から異なる海域へ移動できる航路が 1 本も存在しない場合、4 の海域離脱を行う。
    • また、現在の海域から異なる海域への航路が複数本存在する場合、何者かの陰謀によって等確率で航路が選択される。
      • たとえば、鎮守府のある海域から、他の海域への航路が 4 本存在する場合、それぞれ 25% の確率で選択されます。
  2. 進軍
    • 選択された航路によって、海域を移動する。
  3. 戦闘
    • 進軍先の海域 i には敵艦が待ち構えており、戦闘が発生する。
    • 鎮守府から出港したとき、高橋艦長が率いる軍艦の体力は H であり、戦闘によって軍艦の体力は D_i だけ減少する。
    • 軍艦の体力が 0 以下になると、軍艦は沈没してしまう。
    • 軍艦が沈没すると高橋艦長は失意のあまりこれ以上出撃することが出来なくなってしまうため、絶対に沈没させてはいけない。
    • なお、鎮守府のある海域では戦闘は発生しないが、最終目的地である海域では必ず戦闘が発生する。
  4. 海域離脱 or 航路選択に戻る
    • 海域離脱とは、鎮守府のある海域へ戻ることを意味する。
    • 海域離脱した際に、軍艦の残り体力が C であった場合、H-C だけ体力回復のために時間を消費する。
上記1,2,3,4のサイクル1回につき時間を 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
    • 50% の確率で 1 -> 3 -> 5 -> 6 が選択され、時間 2 を使って鎮守府に戻る。
    • その後、 50% の確率で 1 -> 2 -> 4 -> 6 が選択され、時間 3 を使って最終目的地に到達する。
    • つまり、25% の確率で時間 5 を使って最終目的地に到達。
    1 -> 3 -> 5 -> 6 で 2 度撤退してから 1-> 2-> 4 -> 6
    • 12.5% の確率で時間 7 を使って最終目的地に到達。
    1 -> 3 -> 5 -> 6 で 3 度撤退してから 1-> 2-> 4 -> 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ですが、出力に誤差が許容されているので、上記のような出力でも問題ありません。