Problem p03608 (python)

Fixed submission:
from collections import defaultdict
from itertools import permutations
import heapq

INF = float('inf')
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
memo = [[INF for _ in range(N)] for _ in range(N)]

Adj_list = defaultdict(set)

for i in range(M):
    a, b, c = map(int, input().split())
    if memo[a-1][b-1]:
        memo[a-1][b-1] = min(memo[a-1][b-1], c)
        
    Adj_list[a-1].add((b-1, memo[a-1][b-1]))
    Adj_list[b-1].add((a-1, memo[a-1][b-1]))


def dijkstra(x, vertex):
    d = [INF] * x
    d[vertex] = 0
    hq = [(0, vertex)]
    
    while hq:
        u = heapq.heappop(hq)[1]
        for (v, c) in Adj_list[u]:
            if d[v] > d[u] + c:
                d[v] = d[u] + c
                heapq.heappush(hq, (d[u]+c, v))

    return d

ans = INF
t_dis = 0

table = {}
for i in r:
    table[i-1] = dijkstra(N, i-1)

for each in permutations(r):
    t_dis = 0
    for i in range(R-1):
        t_dis += table[each[i]-1][each[i+1]-1]
    #print(each, t_dis)
    ans = min(ans, t_dis)

print(ans)

Buggy submission (verdict: Runtime Error):
import itertools
import sys
 
def readline():
    return sys.stdin.readline()
 
def read_int_list():
    return list(map(int, readline().split()))
 
def read_int():
    return int(readline())
 
def main():
    N, M, R = read_int_list()
 
    r = [a-1 for a in read_int_list()]
 
    d = [[float('inf')]*N for _ in range(N)]
 
    for _ in range(M):
        a, b, c = read_int_list()
        d[a-1][b-1] = c
        d[b-1][a-1] = c
 
    for a in range(N):
        d[a][a] = 0
 
    res = float('inf')
 
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if d[i][k]+d[k][j] < d[i][j]:
                    d[i][j] = dd
 
    for perm in itertools.permutations(r):
        a = 0
        for i in range(len(perm)-1):
            a += d[perm[i]][perm[i+1]]
        res = min(a, res)
 
    print(res)
 
if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
4 6 3
2 3 4
1 2 4
2 3 3
4 3 1
1 4 1
4 2 2
3 1 6

Buggy submission (verdict: Runtime Error):
from collections import defaultdict
from itertools import permutations
import heapq

INF = float('inf')
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
memo = [[INF for _ in range(N)] for _ in range(N)]

Adj_list = defaultdict(set)

for i in range(M):
    a, b, c = map(int, input().split())
    if memo[a-1][b-1]:
        memo[a-1][b-1] = min(memo[a-1][b-1], c)
        
    Adj_list[a-1].add((b-1, memo[a-1][b-1]))
    Adj_list[b-1].add((a-1, memo[a-1][b-1]))


def dijkstra(x, vertex):
    d = [INF] * x
    d[vertex] = 0
    hq = [(0, vertex)]
    
    while hq:
        u = heapq.heappop(hq)[1]
        for (v, c) in Adj_list[u]:
            if d[v] > d[u] + c:
                d[v] = d[u] + c
                heapq.heappush(hq, (d[u]+c, v))

    return d

ans = INF

table = []
for i in range(N):
    d = dijkstra(N, i)
    min_d = min(d)
    min_d_ind = d.index(min_d)
    table[i][min_d_ind] = min_d 

for each in permutations(r):
    t_dis = 0
    for i in range(R-1):
        if table[each[i]-1][each[i+1]-1] == INF:
            continue
        t_dis += table[each[i]-1][each[i+1]-1]
    ans = min(ans, t_dis)

print(ans)