Problem p03608 (python)

Fixed submission:
from itertools import permutations
INFTY = 10**8
N,M,R = map(int,input().split())
A = list(map(int,input().split()))
G = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b,c = map(int,input().split())
    G[a].append((b,c))
    G[b].append((a,c))
d = {i:[INFTY for _ in range(N+1)] for i in range(N+1)}
for i in G:
    d[i][i] = 0
    for x in G[i]:
        d[i][x[0]] = x[1] 
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            d[i][j] = min(d[i][j],d[i][k]+d[k][j])
dmin = INFTY
for x in permutations(range(R),R):
    cnt = 0
    for i in range(R-1):
        cnt += d[A[x[i]]][A[x[i+1]]]
    dmin = min(dmin,cnt)
print(dmin)

Buggy submission (verdict: Runtime Error):
from itertools import permutations
INFTY = 10**8
N,M,R = map(int,input().split())
r = list(map(int,input().split()))
G = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b,c = map(int,input().split())
    G[a].append((b,c))
    G[b].append((a,c))
dist = [[INFTY for _ in range(N+1)] for _ in range(N+1)]
for i in range(1,N+1):
    dist[i][i] = 0
for i in range(1,N+1):
    for j,d in G[i]:
        dist[i][j] = d
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j])
dmin = 10**8
for i in range(R):
    for j in range(R):
        if i!=j:
            A = list(range(R))
            A.remove(i)
            A.remove(j)
            if len(A)>0:
                for x in permutations(A,R-2):
                    d = dist[r[i]][r[x[0]]]
                    for k in range(1,R-2):
                        d += dist[r[x[i]]][r[x[i-1]]]
                    d += dist[r[x[R-3]]][r[j]]
            else:
                d = dist[r[i]][r[j]]
            dmin = min(dmin,d)
print(dmin)

Buggy submission (verdict: Runtime Error):
from itertools import permutations
INFTY = 10**8
N,M,R = map(int,input().split())
r = list(map(int,input().split()))
G = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b,c = map(int,input().split())
    G[a].append((b,c))
    G[b].append((a,c))
dist = [[INFTY for _ in range(N+1)] for _ in range(N+1)]
for i in range(1,N+1):
    dist[i][i] = 0
for i in range(1,N+1):
    for j,d in G[i]:
        dist[i][j] = d
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j])
dmin = 10**8
for i in range(R):
    for j in range(R):
        if i!=j:
            A = list(range(R))
            A.remove(i)
            A.remove(j)
            for x in permutations(A,R-2):
                d = dist[r[i]][r[x[0]]]
                for k in range(1,R-2):
                    d += dist[r[x[i]]][r[x[i-1]]]
                d += dist[r[x[R-3]]][r[j]]
            dmin = min(dmin,d)
print(dmin)

Buggy submission (verdict: Runtime Error):
 itertools,heapq
INFTY = 10**8
N,M,R = map(int,input().split())
R = list(map(int,input().split()))
G = {}
for _ in range(M):
    A,B,C = map(int,input().split())
    if A not in G:
        G[A] = []
    G[A].append((B,C))
    if B not in G:
        G[B] = []
    G[B].append((A,C))
D = [[INFTY for j in range(N+1)] for i in range(N+1)]
for i in range(1,N+1):
    hist = [0 for _ in range(N+1)]
    heap = [(0,i)]
    while heap:
        cur = heapq.heappop(heap)
        if hist[cur[1]]==0:
            hist[cur[1]] = 1
            for x in G[cur[1]]:
                if hist[x[0]]==0:
                    if D[i][x[0]]>cur[0]+x[1]:
                        D[i][x[0]] = cur[0]+x[1]
                        heapq.heappush(heap,(D[i][x[0]],x[0]))
dmin = INFTY
for r in itertools.permutations(R,len(R)):
    d = 0
    for i in range(1,len(r)):
        d += D[r[i]][r[i-1]]
    dmin = min(dmin,d)
print(dmin)