プライオリティキューを用いたダイクストラ法 ~トレジャーハント編 ~
問題
D: トレジャーハント - AtCoder Beginner Contest 035 | AtCoder
解法
流れ
滞在する必要のある頂点は１つと考える。滞在する頂点を頂点iとすると、頂点0から最短で頂点iに到達し、できるだけ長く頂点iに滞在し、最短で頂点0に戻る事を考える。頂点iを全ての頂点の場合を列挙し得られる得点が最大の物を出力する。
ダイクストラ法
この問題はスタート地点から各頂点の最短経路を求めることで解が得られるので、最短経路問題である。よってダイクストラ法を用いて頂点0から各頂点までの最短経路を求める。今回の問題では頂点と頂点の間の重み付けは「時間」である。よってこの最短時間を求める事ができる。
また、頂点0から頂点iまでの最短経路は通常通りダイクストラ法を用いることでできるが、頂点iから頂点0までの最短経路(帰り道)は、頂点と頂点を結ぶ矢印を逆向きにして、ダイクストラを用いることで求める事ができる。
プライオリティキューを用いてダイクストラ歩の計算量を減らす
通常のダイクストラ法の計算量は、ノード(頂点)の数をVとするとO(V^2)になる。これをプライオリティキューを用いることで、O((E + V)logV)まで減らすことができる。
ダイクストラ法は繰り返し処理をする度に、全てのノードの中で最も最短距離のものを取得する必要がある。この処理は通常O(N)で取得できるが、プライオリティキューを用いることでO(1)で取得できる。これはプライオリティキューを使う事によって、O(logN)で取得することができる。また、挿入はO(logN)になる。これはプライオリティキューが二分ヒープを用いてるためである。
隣接行列を工夫する
ノードとノードの接続関係を表す時に隣接行列を用いる方法がある。これはノードの数とインデックスを対応させた２重配列を用いて実装する。
int[][] adj;
今回の問題の場合だとNが105(最大値)の場合、int[105][105]の２重配列のメモリーは確保できない。 よって、ノードが持つノード数に応じて可変にメモリーを確保できるように隣接行列を工夫する。今回ではリストを用いて表現する。
List<ToNode>[] adj;
このように、一次元配列にし、配列のインデックスに対応して、そのノードが持つノードをプロパティに持つクラスのリストを格納するようにする。これによって入力値で与えられた以上のメモリーは確保しないので、メモリーに優しい設計にできる。
その他の注意点
与えられるノードに全て対して、スタート地点から繋がっているとは限らない。今回作成されるグラフは有向グラフなので行き道は存在しても帰り道が存在しない場合がある。よってそれを考慮して条件を満たさない場合は、弾くことをしなければならない。
