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

AOJ0212 Highway Express Bus

解法
ただ拡張ダイクストラするだけ。到達したノードとコストと残り回数をpriority_queueに突っ込む。コスト小さい -> 残り回数大きい の順にキューから取り出す。
初めに持っている回数券が経路をたどる回数より多い場合も有ると思う(未確認)ので、回数券を使いきった場合だけでなく回数券が残っている場合も考えて、ダイクストラ後はメモしたコスト行列から目的地における任意の回数券の使用回数のうちの最小コストを取り出すようにする。

反省
何故か自分の提出したコードが他のACコードより実行速度が遅め。他コードのElogVのダイクストラよりはもちろん、V^2よりも遅い。理由はわからない。
作ったバグは、キューから取り出すとき pairの中の残り回数をマイナスして取り出した(大きい値から取り出すため)にも関わらず、入れるときにマイナスにして入れなかったというところ。意識されやすいミスなので割とすぐ気がついた。あとは何も考えずに書くだけだった。