Submission #19547739


Source Code Expand

Copy
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

Submission Time
Task J - Leveling
User yukuyon
Language PyPy3 (7.3.0)
Score 6
Code Size 940 Byte
Status AC
Exec Time 166 ms
Memory 71584 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 6 / 6
Status
AC × 2
AC × 37
Set Name Test Cases
Sample example_01.txt, example_02.txt
All example_01.txt, example_02.txt, subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_01_18.txt, subtask_01_19.txt, subtask_01_20.txt, subtask_01_21.txt, subtask_01_22.txt, subtask_01_23.txt, subtask_01_24.txt, subtask_01_25.txt, subtask_01_26.txt, subtask_01_27.txt, subtask_01_28.txt, subtask_01_29.txt, subtask_01_30.txt, subtask_01_31.txt, subtask_01_32.txt, subtask_01_33.txt, subtask_01_34.txt, subtask_01_35.txt
Case Name Status Exec Time Memory
example_01.txt AC 84 ms 62692 KB
example_02.txt AC 65 ms 68204 KB
subtask_01_01.txt AC 56 ms 62496 KB
subtask_01_02.txt AC 66 ms 68088 KB
subtask_01_03.txt AC 66 ms 67916 KB
subtask_01_04.txt AC 149 ms 70188 KB
subtask_01_05.txt AC 157 ms 71584 KB
subtask_01_06.txt AC 154 ms 70156 KB
subtask_01_07.txt AC 160 ms 70476 KB
subtask_01_08.txt AC 70 ms 68348 KB
subtask_01_09.txt AC 143 ms 71128 KB
subtask_01_10.txt AC 73 ms 68280 KB
subtask_01_11.txt AC 157 ms 70380 KB
subtask_01_12.txt AC 153 ms 70888 KB
subtask_01_13.txt AC 164 ms 70468 KB
subtask_01_14.txt AC 157 ms 70880 KB
subtask_01_15.txt AC 166 ms 70268 KB
subtask_01_16.txt AC 134 ms 70696 KB
subtask_01_17.txt AC 147 ms 71028 KB
subtask_01_18.txt AC 83 ms 68496 KB
subtask_01_19.txt AC 79 ms 68556 KB
subtask_01_20.txt AC 151 ms 70612 KB
subtask_01_21.txt AC 159 ms 71184 KB
subtask_01_22.txt AC 155 ms 70804 KB
subtask_01_23.txt AC 161 ms 71352 KB
subtask_01_24.txt AC 59 ms 63228 KB
subtask_01_25.txt AC 52 ms 62748 KB
subtask_01_26.txt AC 112 ms 69760 KB
subtask_01_27.txt AC 149 ms 71384 KB
subtask_01_28.txt AC 158 ms 70044 KB
subtask_01_29.txt AC 166 ms 71448 KB
subtask_01_30.txt AC 156 ms 70828 KB
subtask_01_31.txt AC 154 ms 71300 KB
subtask_01_32.txt AC 98 ms 69232 KB
subtask_01_33.txt AC 75 ms 68624 KB
subtask_01_34.txt AC 100 ms 69132 KB
subtask_01_35.txt AC 87 ms 68888 KB