AOJ 2151 - Brave Princess Revisited

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

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

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);

つらねの日記