読者です 読者をやめる 読者になる 読者になる

つらねの日記

プログラムの進捗やゲームをプレイした感想などを書き連ねる日記。

AOJ 2151 - Brave Princess Revisited

Brave Princess Revisited | Aizu Online Judge

問題

御姫様が街を移動する。道中ではダメージを受ける可能性があり、予算から道ごとに定められた料金を支払うことでダメージを無効化できる。目的地に到達した時の最小被害値を求める。経路問題。





注意した点

ダイクストラを使って解く。
参考:ダイクストラ法 - Wikipedia


各街毎に在る道を配列として保有する。

vector<edge> E[town_n+1]);

無向グラフなので双方向に接続する。
素数を town_n + 1 確保しているのは街番号が 1 -> town_n のため、1引いたり足したりする場所を考える手間を省くため。

その街毎、所持金ごとにそれぞれ最小の被害であった時を保管する配列を作る。

int G[town_n + 1][money + 1];

街と残金が同値の時にすでに今より少ない被害で到達していたならその探索を取りやめるために必要。
INT_MAXをINFとdefineしておいた方が良かったかもしれない。

被害毎に自動でソートするキュー。

priority_queue<P, vector<P>, greater<P>> que;

JavaでいうところのTreeListみたいな。これに現在いる街、被害、残金を追加していく。

街についたら街に隣接するすべての道を見る。

 for(edge e:E[p.p]){

そのうえで以前より低い被害で行くことができるのならキューに挿入する。
この際に、金を払い被害を無効化したときと、金をケチり被害を被ったときの両方を挿入しておく。

ルールでは必ず街に到達することができるので到達できなかった場合にassertするようにすると間違いに早く気付けることがある。

 if(result == -1)
     assert(result);