第13回日本情報オリンピック　予選５

2013年12月15日
情報オリンピック日本委員会

解説

この問題のように，「いくつかの頂点 (町) があり，頂点と頂点との間が辺 (道路) で結ばれている」ようなデータ構造は， グラフ と呼ばれる．この問題は，グラフの操作に習熟しているかを問う問題であった．

まずこの問題で重要なことは，町 i から町 j までタクシーを途中で乗り換えることなく行けるかどうかを判定することである．判定方法のひとつに， Warshall-Floyd 法 というものがある．これは一般のグラフについて，全頂点間の最短路を O(N³) で求めるものである．ただし，この問題においては，Nの最大値が 5000 と大きいため， O(N³) の解法では十分高速に解答を求めることができない．

そこで，より単純に 幅優先探索 を全ての頂点について行うことを考える．一回の幅優先探索は O(K) で行うことができ，N 個の頂点についてこれを行うため全体で O(NK) で行うことができる．この問題では K の最大値が 10000 とやや小さいため，この方法を用いることで十分高速に求めることができる．

さて，これで町 i から町 j までタクシーを途中で乗り換えることなく行けるかどうかを全ての町 i, j 間について判定することができた．次に，これをもとに，町 1 から町 N まで行く場合の運賃の合計の最小値を求める．

それを行うために，町を頂点として， 「町 i から町 j までタクシーを途中で乗り換えることなく行ける場合，町 i から町 j にコスト C_iの辺がある」 ような，新たな有向グラフ G を作成する．グラフ G 上でコスト C の辺を通ることは，運賃 C のタクシーに乗って町間を移動することに相当する．このグラフ G 上での町 1 から町 N までの最短経路 (コストの合計が最小の経路) が，JOI 君が町 1 から町 N までタクシーで移動する際に運賃の合計が最小となるような経路となる．よって，グラフ G 上で町 1 から町 N までの最短経路を Dijkstra 法 などで求めれば，コストの合計がこの問題に対する答えとなる．

解説中に登場した 3 つのアルゴリズム： Warshall-Floyd 法 ・ 幅優先探索 ・ Dijkstra 法 は，グラフを扱う上で重要なアルゴリズムであるので，各自習得しておくのが望ましい．