다익스트라 알고리즘 - 배열에 cost가 주어질 시 탬플릿 코드

import heapq
import sys

input = sys.stdin.readline

cnt = 1
INF = int(1e9)

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def dijkstra():
    q = []
    heapq.heappush(q, (graph[0][0], 0, 0))
    distance[0][0] = 0

    while q:
        cost, x, y = heapq.heappop(q)

        if x == n - 1 and y == n - 1:
            print(f'Problem {cnt}: {distance[x][y]}')
            break

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < n:
                newCost = cost + graph[nx][ny]

                if newCost < distance[nx][ny]:
                    distance[nx][ny] = newCost
                    heapq.heappush(q, (newCost, nx, ny))

while True:
    n = int(input())
    if n == 0:
        break

    graph = [list(map(int, input().split())) for _ in range(n)]
    distance = [[INF] * n for _ in range(n)]

    dijkstra()
    cnt += 1