【AtCoder】「分野別　初中級者が解くべき過去問精選 100 問」解答例【最短経路問題：ダイクストラ法】

2021.01.02

この記事は 【AtCoder】初中級者が解くべき過去問精選 100 問を緑色コーダーが C++ で解いてみた の子記事です。お読みになる前に親記事をご確認ください。

ダイクストラ法については以下の文献が参考になります。

56. GRL_1_A – 単一始点最短経路

以下の文献にダイクストラ法の解説と実装例が記載されています。

これらを参考に実装すれば求解できます。

r から各点への距離は考えられる経路の最大値より大きな値で初期化します。d_i \leq 10000, |E| \leq 500000 であるため、例えば 10^{10} で初期化します。

ダイクストラ法を実施後、各点ごとに距離を確認し、初期値より小さい場合はその値を、初期値のままの場合は経路が無かったことを表す文字列 “INF” を出力します。

計算量は O(|E| \log |V|) = 10^7 程度です。

57. JOI 2008 予選 6 – 船旅

愚直に客の注文票ごとにダイスクトラ法でもっとも安価な運賃を計算した場合の計算量を見積もります。

最初の段階では，船舶は一隻も運航していないものとする．入力のうち，船舶の運航情報を表す行は 1000 行以下である．

と問題文にあるため、航路網の辺は高々 2000 本です。1 つの注文票に対する計算量は高々 2000 \times \log_{2} 2000 \leq 22 \times 10^3 程度です。注文票は最大 k (\leq 5000) 枚であるため、全体の計算量はおよそ 10^8 程度です。実行時間制限は 10 秒のため、間に合います。

ダイクストラ法は始点と終点が同じ辺が複数あっても機能するアルゴリズムです。以下の記述が問題文にありますが、特に気にせず、新たに運航を開始した船舶の運航情報を隣接リストで表現したグラフに追加します。

また，島と島の間に，複数の船舶が運航することがあることに注意せよ．

旅行することが不可能な場合は -1 を出力します。そのため、以下のようにダイクストラ法を行うと出力時の場合分けが不要になります。

  1. 実施時の始点から各点への運賃の合計は -1 で初期化します。
  2. 運賃の合計を更新する際、既存の運賃が -1 である場合は必ず新しい運賃の合計に更新します。

上記の解法はネットワークの更新や始点の変更のたびにダイクストラ法を実施しなければならず、非効率に思われます。
最短経路問題総特集！！！～BFSから拡張ダイクストラまで～ の「ワーシャル・フロイド法」に記載されている以下の性質に着目します。

また、あまり関係ないですが、途中で2頂点間の辺の長さが変わるクエリがあっても、O(V^2) で対応できます。

ワーシャル・フロイド法では一番外側のループの変数が経由する頂点に対応し、経由する場合、経由しない場合でコスト (本問題では運賃の合計) を比較しています。同様に、辺 (c, d) の長さの更新があった場合は辺 (c, d) を経由する場合と経由しない場合で比較すれば、全ての島と島の間の運賃の合計の最小値を計算量 O(n^2) で更新できます。

そこで、ワーシャル・フロイド法を使う以下の手順で求解します。

  1. すべての島と島の間の運賃の合計を -1 で初期化します。(同じ島の間は 0 で初期化します)
  2. 客の注文票を受け取った場合は計算済みの島 a から島 b への運品の合計の最小値を出力します。
  3. 新たな運航情報を受け取った場合は全ての島と島の間の運賃の合計の最小値を更新します。

計算量はそれぞれ O(n^2), O(1), O(n^2) です。船舶の運航情報は高々 1000 であるため、全体の計算量は 1000 \times O(n^2) = 10^7 程度です。

58. JOI 2016 予選 5 – ゾンビ島

この問題は以下の 2 つの問題に分解できます。

  1. すべての町を危険な町か危険でない町か判定し、各町の JOI 君の宿泊費を計算しなさい。
  2. すべての町の宿泊費の情報を与えられます。町 1 から町 N まで移動するときの宿泊費の合計の最小値を求めなさい。

1 はゾンビに支配された町を始点とする幅優先探索で判定できます。2 はダイクストラ法で計算できます。1 の結果を 2 に渡して計算すれば本問題の解答になります。

幅優先探索は始点が複数あっても機能するため、1 の計算量は O(M) です。2 の計算量は O(M \log N) です。そのため、全体の計算量は O(M \log N) = 10^7 程度です。

59. JOI 2014 予選 5 – タクシー

問題を以下の 2 つの問題に分解します。

  1. 町 i から R_i 本以内の道路を使って到達できる町を列挙しなさい。
  2. 町から町への移動のタクシーの運賃が与えられます。町 1 から町 N への移動の運賃の合計の最小値を求めなさい。

1 は町 i を始点とする幅優先探索を行えば列挙できます。2 はダイクストラ法で計算できます。1 の結果をもとに町 i からタクシー会社 i のタクシーに乗って移動できる町への運賃 C_i の辺をもつグラフを作成し、ダイクストラ法で運賃の合計の最小値を計算すれば答えを得られます。

2 の入力である運賃のグラフは最大 N^2 本の辺を持つ可能性があるため、O(N^2) の計算量のダイクストラ法を用います。プログラミングコンテストチャレンジブック (通称 蟻本) の「2-5 あれもこれも実は “グラフ”」に実装例があります。

町 i ごとに幅優先探索を行うため、1 の計算量は O(KN) です。2 の計算量は O(N^2) です。全体の計算量は O(KN + N^2) = 10^8 程度です。