潜入(ZONeエナジープログラミングコンテスト “HELLO SPACE” E) 別解

f:id:kort0n:20210505183927p:plain

最も思いつきやすい解法は、 $O(RC)$ 頂点 $O(R^2C)$ 辺のグラフ上でのDijkstra法を実行するものだが、これは $O(R^2C)\log(RC)$ timeで、実行時間制限に間に合わせるのは非常に難しい。

想定解は上手くグラフを作って辺の数を $O(RC)$ 本へと減らしたグラフ上でDijkstra法を実行するものだが、ここではグラフの作成は工夫せず、最短路の計算を工夫することにする。

$(1, 1)$ から $(R, C)$ までの経路長を $ans$ とおく。

$ans$ として考えられる最大値に等しい数のvectorを用意し、それらにDijkstra法におけるheapの役割を担わせることにより、Dijkstra法と同様の動的計画法を行うことが出来る。ただし、本問題ではコストが $0$ の辺が存在することに注意が必要である。

この手法は $O(R^2C+ans)$ timeである。ここで、 $ans = O(RB_{\max} + CA_{\max})$ であるから、この解法は実行時間制限に十分間に合う。

関連アルゴリズム:Dial's algorithm

dic.kimiyuki.netこのアルゴリズムを用いることも出来る。本記事の手法もこのアルゴリズムも、辺のコストが大きくない点を活用している。