prithivMLmods/Coder-Stat

1 2 3 4<H1>パケット転送</H1>5 6<p>7インターネットでは、データはパケットに分割され、パケットごとにルータと呼ばれる中継機器を介して宛先に転送されます。各ルータはパケットに記載された宛先から次に転送すべきルータを判断します。さらに、無限にルータ間を転送され続けることを防ぐため、パケットには TTL（Time To Live） という値が付加されています。ルータは受け取ったパケットの TTL を 1 減算し、その結果が 0 ならそのパケットを破棄し、それ以外なら次のルータに転送します。8</p>9 10<p>11そこで、ネットワークの設計を手助けするプログラムを作ることになりました。ネットワークの接続情報と送信パケットの情報を入力として、各パケットが宛先ルータに到着するまでに経由するルータの数のうち最小の値を表示するプログラムを作成してください。12</p>13 14<p>15ネットワークは図のように複数のルータとそれらを結ぶケーブルで構成されています。ただし、各接続（ケーブル）は単方向であることに注意してください。各ルータが直接つながっているルータの番号の配列がネットワークの接続の情報として与えられます。ルータの数を <var>n</var> とすれば、各ルータは 1 から <var>n</var> までの整数で識別されます。送信元から宛先ルータまでの経路が複数ある場合は、経由するルータの数が少ない方の値を出力してください。また、パケットが宛先に到達しない場合は NA と出力してください。16</p>17 18<p>19例えば、以下の図のようなネットワークで、送信元ルータが 6、宛先ルータが 5 の場合を考えます。最短経路は 6→1→5 であり経由するルータは 3 個です。この場合、TTL はルータ 6、1 でそれぞれ減算されるので、送信時の TTL が 3 以上であればパケットは到達できます。宛先ルータでは TTL を減算する必要はありません。また、送信元と宛先が同じルータになるようなパケットは無いものとします。20</p>21 22<center>23<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_network">24</center>25<br/>26 27 28<H2>Input</H2>29<p>30入力は以下の形式で与えられます。31</p>32 33<pre>34<var>n</var>35<var>r<sub>1</sub></var> <var>k<sub>1</sub></var> <var>t<sub>11</sub></var> <var>t<sub>12</sub></var> ... <var>t<sub>1k<sub>1</sub></sub></var>36<var>r<sub>2</sub></var> <var>k<sub>2</sub></var> <var>t<sub>21</sub></var> <var>t<sub>22</sub></var> ... <var>t<sub>2k<sub>2</sub></sub></var>37:38<var>r<sub>n</sub></var> <var>k<sub>n</sub></var> <var>t<sub>n1</sub></var> <var>t<sub>n2</sub></var> ... <var>t<sub>nk<sub>n</sub></sub></var>39<var>p</var>40<var>s<sub>1</sub></var> <var>d<sub>1</sub></var> <var>v<sub>1</sub></var>41<var>s<sub>2</sub></var> <var>d<sub>2</sub></var> <var>v<sub>2</sub></var>42:43<var>s<sub>p</sub></var> <var>d<sub>p</sub></var> <var>v<sub>p</sub></var>44</pre>45 46<p>471 行目にルータの総数 <var>n</var>（<var>n</var> &le; 100）、続く <var>n</var> 行に <var>i</var> 番目のルータの接続情報が与えられます。接続情報として、<var>i</var> 番目のルータの番号 <var>r<sub>i</sub></var>、<var>i</var> 番目のルータと直接接続しているルータの個数 <var>k<sub>i</sub></var>、<var>i</var> 番目のルータから送信できるルータの番号 <var>t<sub>i1</sub></var>, <var>t<sub>i2</sub></var>, ... <var>t<sub>ik<sub>i</sub></sub></var>が与えられます。48</p>49 50<p>51続く行にパケットの個数 <var>p</var>（<var>p</var> &le; 1000）、続く <var>p</var> 行に <var>i</var> 番目のパケットの情報が与えられます。パケットの情報として、 送信元ルータの番号 <var>s<sub>i</sub></var>, 宛先ルータの番号 <var>d<sub>i</sub></var>, TTL の値 <var>v<sub>i</sub></var> (0 &le; <var>v<sub>i</sub></var> &le; 10000) が与えられます。52</p>53 54 55<H2>Output</H2>56 57<p>58各パケットごとに、経由するルータの個数または NA を１行に出力してください。59</p>60 61<H2>Sample Input</H2>62 63<pre>647651 4 2 5 4 3662 1 5673 1 6684 1 7695 2 7 6706 1 1717 0726731 2 2741 5 3751 2 1765 1 3776 3 3781 7 479</pre>80 81<H2>Output for the Sample Input</H2>82 83<pre>84285286NA87388389390</pre>91 92 93 94