Submission #19547739

---

Source Code Expand

import heapq
H,W = map(int,input().split())
grid = [list(map(int,input().split())) for i in range(H)]
INF = float("inf")
ans = INF
l=[(0,1),(0,-1),(1,0),(-1,0)]
def di(i,j):
    heap = [(grid[i][j],i,j)]
    heapq.heapify(heap)
    dist = [[INF for j in range(W)] for i in range(H)]
    dist[i][j] = grid[i][j]

    while heap:
        cost,x,y = heapq.heappop(heap)
        if dist[x][y] < cost:
            continue
        for ii,jj in l:
            nx = x+ii
            ny = y+jj
            if not (0<=nx<H and 0<=ny<W):
                continue
            if dist[x][y] + grid[nx][ny] < dist[nx][ny]:
                dist[nx][ny] = dist[x][y] + grid[nx][ny]
                heapq.heappush(heap,(dist[nx][ny],nx,ny))
    return dist

D1 = di(H-1,0)
D2 = di(H-1,W-1)
D3 = di(0,W-1)

for i in range(H):
    for j in range(W):
        ans = min(ans,D1[i][j]+D2[i][j]+D3[i][j]-2*grid[i][j])

print(ans)

Submission Info

Judge Result