prithivMLmods/Coder-Stat

1 2 3 4<h1>ヘビの JOI 君 (Snake JOI)</h1>5 6<h2>問題</h2>7 8<p>9ヘビの JOI 君は，ある大きな屋敷に迷い込んでしまった．屋敷の住人に見つかる前に，屋敷を脱出しなければならない．10</p>11 12<p>13この屋敷には部屋が N 個あり，1, 2, ..., N の番号が付けられている．また，廊下が M 本あり，i 本目の廊下 (1 ≦ i ≦ M) は部屋 A<sub>i</sub> と部屋 B<sub>i</sub> を結んでいる．JOI 君はこれらの廊下をどちらの向きにも通ることができ，廊下 i を通るのには D<sub>i</sub> 分かかる．部屋と部屋の間を廊下を通る以外の手段で移動する方法はない．14</p>15 16<p>17この屋敷の部屋の温度はそれぞれ一定に調節されており，JOI 君にとって寒すぎるか，快適であるか，暑すぎるかである．JOI 君は，急な温度変化に対応できないため，最後に寒すぎる部屋を出てから X 分未満のうちに暑すぎる部屋に入ることはできない．同様に，最後に暑すぎる部屋を出てから X 分未満のうちに寒すぎる部屋に入ることもできない．18</p>19 20<p>21JOI 君は，移動中に部屋に入るとすぐに部屋から出なければならない．また，廊下の途中で引き返したり，廊下 i を D<sub>i</sub> 分より長い時間かけて通ることもできない．ただし，一度訪れた部屋にもう一度入ることや，一度使った廊下をもう一度使うことは許される．22</p>23 24<p>25JOI 君は現在部屋 1 にいる．この部屋は JOI 君にとって寒すぎる．JOI 君は屋敷の出口のある部屋 N に入ると，屋敷から脱出できる．26</p>27 28<p>29JOI 君が屋敷から脱出するのにかかる最短の時間を求めよ．30</p>31 32<h2>入力</h2>33 34<p>35入力は 1 + N + M 行からなる．36</p>37 38<p>391 行目には，3 個の整数 N, M, X (2 ≦ N ≦ 10000, 1 ≦ M ≦ 20000, 1 ≦ X ≦ 200) が空白を区切りとして書かれている．これは，屋敷に N 個の部屋と M 本の廊下があり，JOI 君が温度変化に対応するのに X 分かかることを表す．40</p>41 42<p>43続く N 行のうちの i 行目 (1 ≦ i ≦ N) には，部屋 i の温度を表す整数 T<sub>i</sub> (0 ≦ T<sub>i</sub> ≦ 2) が書かれている．JOI 君にとって部屋 i は，T<sub>i</sub> = 0 のとき寒すぎ，T<sub>i</sub> = 1 のとき快適であり，T<sub>i</sub> = 2 のとき暑すぎる．T<sub>1</sub> = 0 であることが保証されている．44</p>45 46<p>47続く M 行のうちの j 行目 (1 ≦ j ≦ M) には，3 個の整数 A<sub>j</sub>, B<sub>j</sub>, D<sub>j</sub> (1 ≦ A<sub>j</sub> < B<sub>j</sub> ≦ N, 1 ≦ D<sub>j</sub> ≦ 200) が空白を区切りとして書かれている．これは，廊下 j が部屋 A<sub>j</sub> と部屋 B<sub>j</sub> を結んでおり，通るのに D<sub>j</sub> 分かかることを表す．同じ部屋の組を結ぶ廊下が複数ある可能性があることに注意せよ．48</p>49 50<p>51与えられる入力データでは，JOI 君が屋敷から脱出できることは保証されている．52</p>53 54<h2>出力</h2>55 56<p>57JOI 君が屋敷から脱出するのに最短で何分かかるかを表す整数を 1 行で出力せよ．58</p>59 60<h2>入出力例</h2>61<h3>入力例 1</h3>62 63<pre>648 10 4650661671682691701712720731 2 1741 3 1752 3 3762 4 5773 4 1784 5 1795 6 1805 8 1811 7 2827 8 283</pre>84 85<h3>出力例 1</h3>86<pre>87988</pre>89 90<br/>91 92<h3>入力例 2</h3>93 94<pre>9515 25 4960971981990100210111020103110411052106010701081109011011118 11 11127 10 111312 14 11143 8 11151 5 11163 9 11173 8 11181 5 11196 15 112011 12 11212 14 11227 10 112311 12 11245 13 11252 8 11261 4 11272 11 11285 6 11291 13 11306 12 11315 10 11329 13 11334 10 11343 12 11357 13 1136</pre>137 138<h3>出力例 2</h3>139<pre>1406141</pre>142<br/>143 144<p>145入力例 1 では，部屋を 1 → 2 → 3 → 4 → 5 → 6 → 5 → 8 の順に移動するのが最短となる．146</p>147 148<p>149入力例 2 では，いくつかの部屋の組 (たとえば部屋 1 と部屋 5) を結ぶ廊下が複数ある．150</p>151 152 153<br/>154<div class="source">155<p class="source">156<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>157</p>158<p class="source">159<a href="https://www.ioi-jp.org/joi/2016/2017-yo/index.html">情報オリンピック日本委員会作 『第 16 回日本情報オリンピック JOI 2016/2017 予選競技課題』</a>160</p>161</div>162