Problem p03608 (python)

Fixed submission:
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 = map(int, input().split())
    r = map(int, input().split())

    inf = float("inf")
    d = [[inf] * (N + 1) for _ in range(N + 1)]
    for n in range(1, N + 1):
        d[n][n] = 0

    for _ in range(M):
        a, b, c = map(int, input().split())
        d[a][b] = c
        d[b][a] = c

    for k in range(1, N + 1):
        for i in range(1, N + 1):
            for j in range(1, N + 1):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]

    min_cost = inf
    for p in itertools.permutations(r):
        cost = 0
        for i in range(len(p) - 1):
            src, dst = p[i:i + 2]
            cost += d[src][dst]
        min_cost = min(min_cost, cost)

    print(min_cost)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import itertools


def main():
    length = {}
    v = set()
    d = {}

    N, M, R = list(map(int, input().split(' ')))

    r = [int(a) for a in input().split()]

    for _ in range(M):
        a, b, c = list(map(int, input().split(' ')))
        length[(a, b)] = c
        length[(b, a)] = c
        v.add(a)
        v.add(b)
    for a in v:
        length[(a, a)] = 0

    res = float('inf')

    v = list(v)

    for a in v:
        for b in v:
            for c in v:
                length[(b, c)] = min([length[(b, c)], length[(b, a)]+length[(a, c)]])

    # print(length)

    for perm in itertools.permutations(r):
        a = 0
        for i in range(len(perm)-1):
            a += length[(perm[i], perm[i+1])]
        if a < res:
            # print(perm, a)
            res = a

    print(res)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import itertools


def main():
    length = {}
    v = set()
    d = {}

    N, M, R = list(map(int, input().split(' ')))

    r = [int(a) for a in input().split()]

    for _ in range(M):
        a, b, c = list(map(int, input().split(' ')))
        length[(a, b)] = c
        length[(b, a)] = c
        v.add(a)
        v.add(b)
        length[(a, a)] = 0
        length[(b, b)] = 0

    res = float('inf')

    v = list(v)

    for a in v:
        for b in v:
            for c in v:
                length[(b, c)] = min([length[(b, c)], length[(b, a)]+length[(a, c)]])

    # print(length)

    for perm in itertools.permutations(r):
        a = 0
        for i in range(len(perm)-1):
            a += length[(perm[i], perm[i+1])]
        if a < res:
            # print(perm, a)
            res = a

    print(res)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):

from heapq import *

def search(s, length, N, M, R):

    d = [100000+1]*N
    d[s-1] = 0

    prev = [None]*N

    pq = [(100000+1, i+1) for i in range(N)]
    heapify(pq)
    heapreplace(pq, (0, s))

    while len(pq) > 0:
        u = heappop(pq)
        for v, c in length.get(u[1], []):
            alt = d[u[1]-1] + c
            if d[v-1] > alt:
                d[v-1] = alt
                prev[v-1] = u
                heapreplace(pq, (alt, v))
    return d

def main():
    length = {}

    N, M, R = list(map(int, input().split(' ')))

    r = [int(a) for a in input().split()]

    for _ in range(M):
        a, b, c = list(map(int, input().split(' ')))
        length[a] = length.get(a, []) + [(b, c)]
        length[b] = length.get(b, []) + [(a, c)]

    res = 0
    for i in range(R):
        d = search(r[i], length, N, M, R)
        if i+1 < R:
            res += d[r[i+1]-1]

    print(res)

if __name__ == '__main__':
    main()