AT_arc016_4 [ARC016D] 軍艦ゲーム

[problemUrl]: https://atcoder.jp/contests/arc016/tasks/arc016_4 高橋君は艦長である。 高橋艦長の任務は、鎮守府のある海域から最終目的地となる海域へ進軍することである。 高橋艦長は次の順序で行動する。 1. 航路選択 - 進軍する航路を選択する。現在の海域から異なる海域へ移動できる航路が $ 1 $ 本も存在しない場合、$ 4 $ の海域離脱を行う。 - また、現在の海域から異なる海域への航路が複数本存在する場合、何者かの陰謀によって等確率で航路が選択される。 - たとえば、鎮守府のある海域から、他の海域への航路が $ 4 $ 本存在する場合、それぞれ $ 25% $ の確率で選択されます。 4. 進軍 - 選択された航路によって、海域を移動する。 6. 戦闘 - 進軍先の海域 $ i $ には敵艦が待ち構えており、戦闘が発生する。 - 鎮守府から出港したとき、高橋艦長が率いる軍艦の体力は $ H $ であり、戦闘によって軍艦の体力は $ D_i $ だけ減少する。 - 軍艦の体力が $ 0 $ 以下になると、軍艦は沈没してしまう。 - 軍艦が沈没すると高橋艦長は失意のあまりこれ以上出撃することが出来なくなってしまうため、`絶対に沈没させてはいけない`。 - なお、鎮守府のある海域では戦闘は発生しないが、最終目的地である海域では必ず戦闘が発生する。 8. 海域離脱 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 $ です。 32. $ 2 $ 行目から $ M $ 行は、 $ i $ 番目の航路を表す。移動元の海域を表す整数 $ f_i\ (1≦f_i≦N) $、移動先の海域を表す整数 $ t_i\ (1≦t_i≦N) $ が、スペース区切りで与えられる。 - $ f_i\

N/A

N/A