AOJ 0234 （Aizu Buried Treasure : 会津の埋蔵金）

【問題】

https://onlinejudge.u-aizu.ac.jp/problems/0234

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0234

【解説】

費用の最小値にて最良優先探索を行う。（経路を全探索すると当然TLE。）

仮に酸素の考え方がないとすれば、一度訪問したセルに再度訪問することはないため、単純にダイクストラ法を用いて、最下層のセルまでに最大コスト値以下で到達できるかを求めればよい。

ただし、制約として酸素の残量の考え方があるため、最小コストの経路をとると、酸素の残量が足りない場合は、一度訪問したセルに再度訪問する経路が答えの経路となる場合がある。

そのため、priorityQueueに突っ込むノードに今まで訪問済のセルとそのセルを訪れた時の残酸素量を記録しておき、すでに訪問済みのノードを訪れようとする場合、以前訪問した際の残酸素量より残酸素が大きい場合は、再度訪問するようにした。（費用の最小値にて最良優先探索をしているため、以前訪問した際の残酸素量以下で訪れる場合はそれが最小コストの経路となることはない。）

注意点として、セルを訪問したタイミングで残酸素量が0となる場合、酸素を補給する行動もとれないため、訪問する前に残酸素量から1を引き、0となる場合は処理を打ち切る必要がある。

【コード】