![]() |
|
2007年12月16日
情報オリンピック日本委員会
|
JOI国には,n 島の島があり, 各島には 1 から n までの番号が付けられている. 現在,JOI国では各島の間を結ぶ航路網の整備が進んでいる.
あなたは,船舶の切符を扱っているチケットセンターに勤務している.JOI国には船舶を使って,できる限り安価に,
島と島の間を旅行したいと考えている人が沢山おり,
彼らは,出発地と目的地を注文票に記入して,あなたのところに送ってくる.
あなたの仕事は,客から注文票を受け取ったらすぐに,
いくつかの船舶を乗り継いで,
出発地と目的地を結ぶ航路の中で,
もっとも安価な運賃を計算し,客に伝えることである.
ただし,旅程によっては,船舶を使って旅行することが出来ない場合もある.
そのときは『船舶を使って旅行することが出来ない』と客に伝える必要がある.
また,JOI国では,島と島の間を結ぶ新しい船舶が,次々と運航を開始しており,
あなたには,その情報が随時伝えられる.
客に返事をする際には,最新の情報に留意しなければならない.
入力として,客の注文票や新たに運航を開始した船舶の運航情報が与えられたときに, 客への返事を求めるプログラムを作成せよ.
なお,入力例1と出力例1に対する実行状況を,図1として図示している.
入力の 1 行目には2つの整数 n, k (1 ≦ n ≦ 100, 1 ≦ k ≦ 5000) が書かれている.
これは,島の数が n 島で,入力が k + 1 行からなることを表す.
i + 1 行目 (1 ≦ i ≦ k) には,
3 個または 4 個の整数が空白を区切りとして書かれている.
最初の段階では,船舶は一隻も運航していないものとする. 入力のうち,船舶の運航情報を表す行は 1000 行以下である. また,島と島の間に,複数の船舶が運航することがあることに注意せよ.
入力のうち,注文票を表す行の数を m とおく.
提出する出力ファイルは m 行からなり,
i 行目(1 ≦ i ≦ m)には,
i 番目の注文票に対する返事を表す整数を書く.
すなわち,
i 番目の注文票の出発地と目的地の間を,いくつかの船舶を乗り継いで旅行することが可能ならば,
その運賃の合計の最小値を書く.
旅行することが不可能ならば,-1 を書く.
入力例1 | 入力例2 |
---|---|
3 8 1 3 1 10 0 2 3 1 2 3 20 1 1 2 5 0 3 2 1 1 3 7 1 2 1 9 0 2 3 |
5 16 1 1 2 343750 1 1 3 3343 1 1 4 347392 1 1 5 5497 1 2 3 123394 1 2 4 545492 1 2 5 458 1 3 4 343983 1 3 5 843468 1 4 5 15934 0 2 1 0 4 1 0 3 2 0 4 2 0 4 3 0 5 3 |
出力例1 | 出力例2 |
-1 15 12 |
5955 21431 9298 16392 24774 8840 |
なお,入力例1と出力例1の船舶が運航を開始していく模様と客からの注文票に対する返答を,図1として以下に図示している.
![]() |
![]() |
![]() |
![]() |
![]() |
|
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
図1. 入力例1と出力例1に対するアニメーションと分解写真
※各入出力例のデータは, 右クリック等によりファイルに保存して利用可能です.