最短経路DAGを作って経路の数え上げをする(動的計画法)
問題
C: 正直者の高橋くん - AtCoder Beginner Contest 021 | AtCoder
ソースコード一部
ソースコードの全体は最後に添付。
解説
今回の問題では、スタートからゴールまでの最短経路が複数存在し、その経路数を求める問題である。 よって、初めに行うことは与えられたグラフから最短経路でゴールにたどり着かない道を削ることである。そうすることで、残った経路のどの経路を通ったとして最短経路でゴールに辿り着くことができる。
つまり、まとめると以下のステップを行う。
- スタート地点から各点までの最短距離を求める
- 最短距離でゴールに向かわない辺は取り除く
- 残った経路の中でゴールに辿り着く経路を数え上げる
ダイクストラ法を用いて最短距離を算出
グラフにおいて、ある地点から全てのノードまでの距離を効率よく算出するためにはダイクストラ法を用いる。今回はダイクストラ用のクラスを作成している。
詳しくは以下参照。
keita-matsushita.hatenablog.com
最短経路DAGを作成
最短距離でゴールに向かわない辺は取り除くと、最短経路DAGが作成される。DAGとは、閉路が無い有向グラフのことである。 最短経路DAGにおいて、スタート地点からゴール地点まで行く経路を全て数え上げれば今回の目的を果たせる。
最短経路DAGを作成するためのCreateDAGクラスを用いて生成している。
動的計画法を使い経路の数え上げ
最後に経路の数え上げを動的計画法のメモ化再帰で解く。今回の問題における動的計画法をするに当たってのポイントは以下の通り。
- 求めたいもの: 経路の数
- 再帰する度に変わるもの: 街(今どの街にいるか) → Node
- 再帰を抜ける条件:
１．今見ている街がゴールに着いたら
２．行き止まりの街に進んだら(出力辺を持たないノード) - 再帰の仕方: 今いる街から繋がっている街を次の街として再帰
- メモテーブル: dp[今見ている街] = そこに辿り着く経路の数
すると以下のようにメソッドを書ける
