prithivMLmods/Coder-Stat

1 2 3 4<h1>ゾンビ島 (Zombie Island)</h1>5 6<h2>  問題</h2>7<p>8JOI 君が住んでいる島がゾンビに侵略されてしまった．JOI 君は島で一番安全な避難場所として設定されているシェルターに逃げ込むことにした．9</p>10 11<p>12JOI 君が住んでいる島は町 1 から町 N までの N 個の町からなり，町と町とは道路で結ばれている．島には M 本の道路があり，すべての道路は異なる 2 つの町を結んでいる．JOI 君は道路を双方向に自由に移動できるが，道路以外を通って町から別の町に行くことはできない．13</p>14 15<p>16いくつかの町はゾンビに支配されており，訪れることが出来ない．ゾンビに支配されている町から S 本以下の道路を使って到達できる町を<b>危険な町</b>という．それ以外の町を<b>危険でない町</b>という．17</p>18 19<p>20JOI 君の家は町 1 にあり，避難先のシェルターは町 N にある．町 1，町 N はゾンビに支配されていない．島の道路は移動するのに時間がかかるので，JOI 君は町を移動するたびに，移動先の町で一晩宿泊しなければならない．JOI 君は，危険でない町で宿泊する場合は宿泊費が P 円の安い宿に泊まるが，危険な町で宿泊する場合はセキュリティのサービスが優良な宿泊費が Q 円の高級宿に泊まる．JOI 君はできるだけ宿泊費が安くなるように移動して，町 N まで避難したい．町 1 や町 N では宿泊する必要はない．21</p>22 23<p>24JOI 君が 町 1 から町 N まで移動するときに必要な宿泊費の合計の最小値を求めよ．25</p>26 27 28<h2>  入力</h2>29<p>30入力は 2 + K + M 行からなる．31</p>32 33<p>341 行目には，4 つの整数 N, M, K,  S (2 ≦ N ≦ 100000, 1 ≦ M ≦ 200000, 0 ≦ K ≦ N - 2, 0 ≦ S ≦ 100000) が空白を区切りとして書かれている．これは，島が N 個の町と M 本の道路からなり，N 個の町のうち K 個の町がゾンビに支配されており，ゾンビに支配されている町から S 本以下の道路を使って到達できる町を危険な町と呼ぶことを表す．35</p>36 37<p>382 行目には，2 つの整数 P, Q (1 ≦ P ＜ Q ≦ 100000) が空白を区切りとして書かれている．これは，JOI 君が危険でない町では宿泊費が P 円の宿に泊まり，危険な町では宿泊費が Q 円の宿に泊まることを表す．39</p>40 41 42<p>43続く K 行のうちの i 行目 (1 ≦ i ≦ K) には，整数 C<sub>i</sub> (2 ≦ C<sub>i</sub> ≦ N - 1) が書かれている．これは，町 C<sub>i</sub> がゾンビに支配されていることを表す．C<sub>1</sub>, ..., C<sub>K</sub> は全て異なる．44</p>45 46<p>47続く M 行のうちの j 行目 (1 ≦ j ≦ M) には，2 つの整数 A<sub>j</sub>, B<sub>j</sub> (1 ≦ A<sub>j</sub> ＜ B<sub>j</sub> ≦ N) が空白を区切りとして書かれている．これは，町 A<sub>j</sub> と町 B<sub>j</sub> との間に道路が存在することを表す．同じ (A<sub>j</sub>, B<sub>j</sub>) の組が 2 回以上書かれていることはない．48</p>49 50<p>51与えられる入力データにおいては，町 1 から町 N までゾンビに支配されていない町のみを通って移動できることが保証されている．52</p>53 54 55<h2>  出力</h2>56<p>57JOI 君が町 1 から町 N まで移動するときに必要な宿泊費の合計の最小値を 1 行で出力せよ．58</p>59 60<p>61出力が 32 ビット符号付き整数の範囲に収まるとは限らないことに注意せよ．62</p>63 64<h2>  入出力例</h2>65 66  <h3>入力例 1</h3>  67 68 69  <pre>7013 21 1 1711000 6000727731 2743 7752 4765 8778 9782 5793 4804 7819 108210 11835 9847 12853 6864 5871 38811 12896 7908 11916 13927 89312 1394</pre>95 96<h3>出力例 1</h3>97 98 99<pre>10011000101</pre>102 103  <h3>入力例 2</h3>  104 105  <pre>10621 26 2 21071000 20001085109161101 21111 31121 101132 51143 41154 61165 81176 71187 91198 101209 101219 1112211 1312312 1312412 1512513 1412613 1612714 1712815 1612915 1813016 1713116 1913217 2013318 1913419 2013519 21136</pre>137 138 139 140<h3>出力例 2</h3>141 142  <pre>14315000144</pre>145 146 147<p>148入出力例 1 は，以下の図に対応している．円は町を，線は道路を表す．149</p>150 151<p>152<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_JOI2015_2016-yo-t5-fig01" alt="sample1" width="350" height="350"></a>153</p>154 155<p>156この場合，町 3，町 4，町 6，町 8，町 12 が危険な町である．157</p>158 159<p>160以下のような順番で町を移動すると，宿泊費の合計を最小にできる．161</p>162 163<ul>164<li>町 1 から町 2 に行く．町 2 で宿泊費が 1000 円の安い宿に宿泊する．</li>165<li>町 2 から町 5 に行く．町 5 で宿泊費が 1000 円の安い宿に宿泊する．</li>166<li>町 5 から町 9 に行く．町 9 で宿泊費が 1000 円の安い宿に宿泊する．</li>167<li>町 9 から町 10 に行く．町 10 で宿泊費が 1000 円の安い宿に宿泊する．</li>168<li>町 10 から町 11 に行く．町 11 で宿泊費が 1000 円の安い宿に宿泊する．</li>169<li>町 11 から町 12 に行く．町 12 で宿泊費が 6000 円の高級宿に宿泊する．</li>170<li>町 12 から町 13 に行く．町 13 では宿泊しない．</li>171</ul>172 173 174 175<p>176JOI 君がこのような経路で移動したとき，宿泊費の合計は 11000 円になるので，11000 を出力する．177</p>178 179 180 181 182 183<div class="source">184<p class="source">185<a rel="license" href="http://creativecommons.org/licenses/by-sa/4.0/"><img alt="クリエイティブ・コモンズ・ライセンス" style="border-width:0" src="https://i.creativecommons.org/l/by-sa/4.0/80x15.png"/></a>186</p>187<p class="source">188<a href="https://www.ioi-jp.org/joi/2015/2016-yo/index.html">情報オリンピック日本委員会作 『第 15 回日本情報オリンピック JOI 2015/2016 予選競技課題』</a>189 190</p>191</div>192