AOJ 2151 - 勇敢なお姫様またも現る

問題
提出コード

解法

頂点を増やします。
都市に着いた段階で予算のうちだけ消費するような経路の中で、襲われる人数の最小値
とすると、今いる都市、消費した予算、襲われる人数を一緒に持った状態でダイクストラ法を適用すれば良いです。
次の都市に遷移する際に、予算を消費するか、消費せずに襲われる人数を増やすかの2択が発生するので、それぞれについての遷移を考えていけばいいことになります。

感想

最初、無条件で予算を消費しつつ襲われる人数をカウントしていく問題だと誤読したので、サンプルが全く合わずに混乱していました…
頂点を増やしてダイクストラを行う問題、やはり多いですね。