この問題は、 \((H,W)\) までの到達時間から \((1,1)\) から \((H,W)\) までの最短距離を引いた値を最小化せよと言い換えることができます。

ここで、現在位置 \((i,j)\) と、 \((i,j)\) から \((1,1)\) までの最短距離を管理する拡張ダイクストラを考えます。 \(f(i,j,d)\) を \((1,1)\) から \((i,j)\) の最短距離が \(j\) となるように \((i,j)\) まで移動した際の最短時間とします。このとき、 \((i,j)\) と隣接しているマス \((i',j')\) について、 \((i,j)\) から \((i',j')\) に移動するとき、その時点での経過時間は \(f(i,j,d)+(2d+1) \times A_{i',j'} + 1\) となります。

\(d\) としてありえるのは \(O(HW)\) 通りなので、 \(f\) は拡張ダイクストラの要領で実装することで \(O((HW)^2 \log (HW)^4)\) で求めることができます。