엔터프라이즈호 탈출(백준9505)

그래프에서 길을 찾아 나서는데 heapq를 이용해서 경로들의 값을 저장하고 큐에서 꺼낼 때마다 확인한다. 

import heapq 
import sys
input = sys.stdin.readline
testcase = int(input())
inf = int(1e9)
dx =[1,-1,0,0]
dy = [0,0,1,-1]

for _ in range(testcase):
    k,w,h = map(int, input().split())
    ships ={}
    ships['E'] = 0 
    gra = []
    sx,sy =0,0 
    dist = [[inf for _ in range(w)]for _ in range(h)]
    for i in range(k):
        a,b = map(str, input().split())
        b =int(b)
        ships[a] = b 
    for i in range(h):
        oneline = str(input().rstrip())
        gra.append(oneline)
        for j in range(len(oneline)):
            if oneline[j] =='E':
                sx,sy= i,j 
                dist[i][j] =  0 
                
    q = []
    q.append((0,sx,sy))
    heapq.heapify(q)
    while q :
        wei, x,y = heapq.heappop(q)
        if x ==0 or y==0 or x== h-1 or y== w-1:
            print(wei)
            break  
        if dist[x][y] < wei :
            continue 
        
        for i in range(4):
            nx,ny = x+dx[i],y+dy[i] 
            if (0<=nx<h and 0<=ny< w):
                if dist[nx][ny]  > wei + ships[gra[nx][ny]]:
                    dist[nx][ny] = wei + ships[gra[nx][ny]]
                    heapq.heappush(q, (dist[nx][ny],nx,ny))