敗れた戦闘は常に軍隊を弱め、解体する。当面の課題は再び集結し、その集結の中で秩序と勇気と信頼を取り戻すことだ。
- カール・フォン・クラウゼヴィッツ『戦争論』第4篇第13章
問題を開いた途端にこんな知らせで申し訳ありませんが、あなたは重要な戦闘に敗れたばかりです。あなたの指揮していた部隊は一部しか生き残らず、ばらばらになって自分の命を守るために逃げています。
自分の命まで敗戦の代償として差し出したくなければ、敗走する部隊をまとめて隊列を立て直し、戦線の崩壊を防がなければなりません。
敵の侵入やさらなる進撃を防ぎ、重要な通路や拠点を維持するためには、敗戦で散り散りになった部隊を後方の指定された集結地点へ、予備部隊を重要な防御地点へ速やかに移動させる必要があります。あなたは敵にできるだけ少ない機会しか与えずに状況を立て直せるよう、各部隊の移動にかかる時間を最小にしようとしています。
この地域には移動の出発地や目的地となる地点が 個あり、各地点には 番から 番までの番号が付いています。異なる 2 地点の間には直接移動できる双方向の道があり、地点 から地点 へ直接移動するのにかかる時間は次の通りです。
ここで、 は非負整数で、 は を で割った余りを表します。
移動中に他の地点を経由してもかまいません。経路に沿って移動するのにかかる時間は、その経路に含まれる各道の移動時間の総和です。
あなたは部隊を再配置するため、 個の移動計画を検討しようとしています。各計画には、部隊が現在いる地点 と目的地 が与えられます。各計画について、地点 から地点 まで移動するのにかかる最小時間を求めてください。
最初の行に整数 、、 が空白区切りで与えられます。
続く 行に、各移動計画の出発地点と目的地の番号 、 が空白区切りで与えられます。
各移動計画の最小移動時間を、与えられた順に 1 行ずつ出力してください。
例 1 の最初の計画では、地点 から地点 へ直接移動すると の時間がかかり、これが最小です。
例 1 の 2 番目の計画では、地点 から地点 へ直接移動すると の時間がかかり、これが最小です。
補足 この問題は BCD 13 Ex の原型です。
この問題を解けた方は、BCD 13 Ex にも挑戦してみてください。
例 2 の最初の計画では、地点 から地点 へ直接移動すると の時間がかかります。経路 を移動すると の時間がかかり、これが最小です。
