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

AOJ2021 Princess in Danger

解法
拡張ダイクストラ。施設で冷凍する時間を決めるときに、その場にとどまって最大Mまで回復する場合を全て priority_queue につっこむ。ここで、その場にとどまることがポイントでエッジの移動と冷凍を同時にやろうとしないこと。同時にやろうとすると、回復量の決め打ちでfor文を回す必要が生じてしまう。

反省
初めは pair > の { cost, -m, node } を priority_queue につっこんでキューのすべての処理を終えた後、目的地に到達した中で最小コストのものを導くようにしたが、よくわからないが TLE(20sec) だった。とりあえず struct State { int cost, m, node; ... }; を作成し、これをキューに突っ込んだら解決したが、結局 TLE の原因は不明のままになってしまった。