python - uVA 929 - 始终使用 Python 代码获取 TLE

Question

我使用队列 + Dijkstra 算法来解决问题，但我总是得到 TLE。另外，我真的不知道如何提高性能。请帮我解决这个问题。谢谢

下面是我的代码：

import collections

t = int(input())
for _ in range(t):
    n = int(input())
    m = int(input())
    maze = [ list(map(int, input().split())) for _ in range(n)]
    vals  = [ [-1 for _ in range(m)] for _ in range(n)]
    vis  = [ [0 for _ in range(m)] for _ in range(n)]
    vals[0][0] = maze[0][0]

    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    pq = collections.deque()
    pq.appendleft((maze[0][0], 0, 0))

    while pq:
        dis, r, c = pq.pop()
        vis[r][c] = 1
        for (mx, my) in directions:
            nx, ny = r+mx, c+my
            if 0<=nx<n and 0<=ny<m and vis[nx][ny]!=1:
                tmp = dis+maze[nx][ny]
                if vals[nx][ny]==-1 or vals[nx][ny]>tmp:
                    vals[nx][ny] = tmp
                    pq.appendleft((tmp, nx, ny))
                
    print(vals[n-1][m-1])