いわゆる「最短経路」を求める問題ですから、 dijkstra を考えましょう。

ふつうの最短経路と異なる点として、頂点に重みがありますが、これは「移動した時に移動先の \(A_{r, c}\) がかかる」とすれば、帰着できます。（問題文もそういう書き方に近いですね）

ということで、 \(O(HW \log (HW))\) で解けました。

実装例

from heapq import heappop, heappush

h, w = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]

inf = 1 << 60
dis = [[inf] * w for i in range(h)]
dis[0][0] = 0
que = [(0, 0, 0)]

while que:
    d, i, j = heappop(que)
    if dis[i][j] != d: continue
    for di, dj in [(0,1),(0,-1),(1,0),(-1,0)]:
        ni, nj = i + di, j + dj
        if 0 <= ni < h and 0 <= nj < w:
            nd = dis[i][j] + a[ni][nj]
            if dis[ni][nj] > nd:
                dis[ni][nj] = nd
                heappush(que, (nd, ni, nj))
print(dis[h-1][w-1])