AOJ 0215 （Pachimon Creature : パチモンクリーチャー）
【問題】
https://onlinejudge.u-aizu.ac.jp/problems/0215
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0215
【解説】
グリッド上を各属性のクリーチャーを捕まえながらゴールまで移動する問題。
グリッド上の移動ではあるが、障害物や経路に制限がないため、スタート、ゴール、各クリーチャーをノード、各ノード間のマンハッタン距離をコストとしたグラフに置き換えて考えることができる。
グラフに置き換えて考えることができれば、ダイクストラ法を利用してスタートからゴールまでの最短距離を、最初に選ぶ各種類のクリーチャーの種類ごとに求め、最短コストを出せばよい。
仮に初めに選ぶクリーチャーの種類を「１」とすると「S」⇒「２」のいずれか⇒「３」のいずれか⇒「４」のいずれか⇒「５」のいずれか⇒「G」の経路をたどることになる。そのため、初めにクリーチャーの種類ごとの配列に位置情報を格納し、ダイクストラ法実施時には、現在取り出した辺が何本目の辺の当たるかを保持しておき、その値に応じて次に接続しうるクリーチャーの位置までの距離をコストとして順次PriorityQueueに格納する。
また、ゴールまでの最短経路だけが分かればよいので、PriorityQueueから取り出したノードがゴールのノードである場合は、そこで処理を打ち切ることで、処理時間を短くすることができる。
・・・とここまで書いたが、ノードの最大辺数が1000、ゴールまでの辺の数が高々5なので、dpを用いて計算しても十分間に合う。（というか、solutionを見ると、こっちの解法が多い気がする。あと、C#はPriorityQueueが標準ライブラリに無いのが辛い。
