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

ctyl's problem solving

競技プログラミングが主な話題です。

yukicoder No.20

ダイクストラ法(?)★3.この手の問題は初めてだったので,解説を少し読んで,priority_queueの仕様を理解してから実装.正味2時間くらいかかったのでは・・

 

解説通りスタートからオアシスまで・オアシスからゴールまで・スタートからゴールまでの3ルートに分けて判定.体力がオアシス以外で増加することがないのがこの探索法を使うときの肝?

かなり試行錯誤したので,またqueueについて少しわかった気がします.便利便利

 

オアシスがない場合でも同じ計算式が使えるようにオアシスなしのときのオアシス経由のコストを体力よりも大きな値(1000)にしてあります.

 

yukicoder No.20