prithivMLmods/Coder-Stat

1 2 3 4<h1>Problem E: Doragoso Ball</h1>5<h2>Problem</h2>6 7<p>8<var> L </var>個集めるとドラゴソが現れどんな願いでも一つだけ叶えてくれるというドラゴソボールがとある迷宮に散らばっている。入口からスタートし、途中で立ち止まることなくすべてのボールを回収し、それらを迷宮内にある祭壇に奉納し、そのまま呪文を唱えるとドラゴソが現れ願いを叶えてくれるという。ただし、呪文を唱え始める時間は入口からボールを奉納するまでのルートのうち、移動時間が<var> K </var>番目に短いルートで移動したときの時間でなければならない。9</p>10 11<p>12この迷宮は部屋とわたり通路からなり、部屋と部屋はわたり通路を通る事によって行き来できる。ドラゴソボールはそれらの数ある部屋のどこかに落ちている。<!--だが、科学の進歩により、迷宮の部屋と部屋の位置関係の解析が進み、ドラゴソレーダーの開発によってどの部屋にボールが落ちているかも把握できる予定である。文研究所に部屋の位置関係とボールの位置のデータが送られる予定である。とある研究所で最も優秀なプログラマーであるあなたは、呪文を唱え始めるべき時間を求めるという重要な任務が与えられた。-->なお、迷宮は入り口から祭壇へたどりつく道が存在しない可能性もあるようだ。また、移動時間はわたり通路の移動だけを考慮し、部屋の中を移動する時間、ボールを拾うときにかかる時間、祭壇に奉納する時間は考慮しなくてよい。<!--また、同じ部屋に何度も訪れてもよいが、ドラゴソボールがある部屋に初めて入った場合は、そのボールを拾うことにする。-->また、同じ通路や同じ部屋に何度も訪れてもよいが、ドラゴソボールがある部屋に初めて入った場合は、そのボールを拾うことにする。祭壇に到達したとき、必ずしもボールを納めなければならないわけではない。13</p>14 15<p>16迷宮の内部構造の情報と迷宮の入り口、祭壇の場所とボールの数<var> L </var>とボールの配置場所と求められている最短な経路の順位<var> K </var>が与えられるので、呪文を唱え始めるべき時間を求めよ。17</p>18 19 20<p>21また、異なる移動ルートでも、移動時間が同じである場合はそれらのルートは同じ順位として扱う。22<br/>23例えば、24<br/>25 26<pre>27ルートA 時間 228ルートB 時間 529ルートC 時間 530ルートD 時間 531ルートE 時間 532ルートF 時間 733</pre>34 35<p>36 37このようなとき、ルートB,C,D,Eは2位かつ3位かつ4位かつ5位として扱う。ルートFは6位として扱う。38</p>39 40<h2>Input</h2>41<p>42 43入力は複数のデータセットからなる。</br>44各データセットは以下のフォーマットで表される。45</p>46 47<pre>48<var>N</var> <var>M</var> <var>L</var> <var>K</var>49<var>u<sub>1</sub></var> <var>v<sub>1</sub></var> <var>c<sub>1</sub></var>50…51<var>u<sub>M</sub></var> <var>v<sub>M</sub></var> <var>c<sub>M</sub></var>52<var>S</var> <var>G</var>53<var>B<sub>1</sub></var>54<var>B<sub>2</sub></var>55…56<var>B<sub>L</sub></var>57</pre>58 59<p>60最初に<var> N </var>,<var> M </var>,<var> L </var>,<var> K </var>が与えられる。</br>61それぞれ、部屋の数、わたり通路の数、ボールの数、求められている最短な経路の順位を表す。それぞれの部屋は1〜<var> N </var>で番号付けされる。</br>62次に<var> M </var>行にわたり通路の情報、<var> u<sub>i</sub> </var>,<var> v<sub>i</sub> </var>,<var> c<sub>i</sub> </var>が与えられる。</br>63部屋<var> u<sub>i</sub> </var>,<var> v<sub>i</sub> </var>間にわたり通路が存在し、通過するのに時間<var> c<sub>i</sub> </var>がかかることを表す。</br>64次に<var> S </var>,<var> G </var>が与えられる。</br>65それぞれ、迷宮の入り口と祭壇がある部屋番号を表す。</br>66次に<var> L </var>行にわたってドラゴソボールが落ちている部屋の番号<var> B<sub>i</sub> </var>( 1 &le;<var> i </var>&le;<var> L </var>)が与えられる。</br>67</p>68 69<p>70入力の終わりは4つのゼロからなる。</br>71</p>72 73<h2>Constraints</h2>74<p>入力は以下の条件を満たす。</p>75<ul>76<li>入力に含まれる値はすべて整数</li>77<li>2 &le;<var> N </var>&le; 50</li>78<li>0 &le;<var> M </var>&le; 1225</li>79<li>1 &le;<var> L </var>&le; 7</li>80<li>1 &le;<var> K </var>&le; 10</li>81<li>1 &le;<var> S </var>,<var> G </var>&le; <var>N</var></li>82<li>1 &le;<var> B<sub>i</sub> </var>&le; <var>N </var>( 1 &le;<var> i </var>&le; <var> L </var>)</li>83<li><var> B<sub>i</sub> </var>&ne;<var> B<sub>j</sub> </var> ( 1 &le;<var> i </var>&lt;<var> j </var>&le;<var> L </var>)</li>84<li>1 &le;<var> u<sub>i</sub> </var>,<var> v<sub>i</sub> </var>&le;<var> N </var>( 1 &le;<var> i </var>&le; <var> M </var>)</li>85<li>1 &le;<var> c<sub>i</sub> </var>&le; 1000 ( 1 &le;<var> i </var>&le; <var> M </var>)</li>86<li>データセットは最大10個である</li>87</ul>88 89<h2>Output</h2>90<p>各データセットに対し、呪文を唱え始めるべき時間を1行に出力せよ。<var> K </var>番目に短い経路が存在しない場合は"NA"を1行に出力せよ。</p>91 92<h2>Sample Input</h2>93<pre>949 14 5 10951 2 1961 4 5972 4 4982 3 3992 6 21003 6 31013 7 21024 6 51034 5 61045 8 81056 7 31067 8 11077 9 91088 9 21091 9110111121125113711491154 5 1 31161 2 11171 3 21182 3 21192 4 91203 4 11211 412221234 5 1 101241 2 11251 3 21262 3 21272 4 91283 4 11291 413021314 3 1 11321 2 11332 3 11343 4 11351 413611374 3 1 21381 2 11392 3 11403 4 11411 414211434 3 1 101441 2 11452 3 11463 4 11471 414811492 1 1 11501 2 11511 215211532 1 1 101541 2 11551 215611574 2 1 41581 2 11593 4 11601 416121620 0 0 0163</pre>164 165 166<h2>Sample Output</h2>167<pre>1682716961708171317251737174117519176NA177</pre>