AtCoder Regular Contest #003 C. 暗闇帰り道

問題

NxMの格子状の区画とスタート地点、ゴール地点、各区画の明るさが与えられる。
各隣り合う区画は1秒で移動できる。
区画の明るさはスタートした時刻からt秒立つと、「元の明るさ*0.99^t」になってしまう。
なるべく、スタートからゴールまでの経路中、暗い区画を通りたくない。
「経路の明るさ」を経路中一番暗い区画の明るさ、と定義したとき、一番「経路の明るさ」が明るい経路の一番暗い区画の明るさの値を返す。

考え方

最低の明るさvを決めたとき、スタートからゴールまで行けるかどうかをチェックすることができるので、2分探索する。
スタートからゴールまでいけるかはBFSで、(位置,時間)を状態にする。すでに通った位置は、前に通った時の方が時間が少ないので、再び通る必要がない。(visitedかどうかだけ保持すればいい)

あと、できるだけ無駄が少なくなるように枝狩りする。