Problem p03608 (python)

Fixed submission:
from itertools import permutations

def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, m, r = read_line(int, int, int)

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

costs = {}
for i in range(n + 1):
    costs[i] = {}
    for j in range(n + 1):
        costs[i][j] = float('inf')

for _ in range(m):
    a, b, c = read_line(int, int, int)

    costs[a][b] = costs[b][a] = c

for k in range(n + 1):
    for i in range(n + 1):
        for j in range(n + 1):
            c = costs[i][k] + costs[k][j]
            if costs[i][j] > c:
                costs[i][j] = c

def cost(selected):
    c = 0
    for i in range(len(selected) - 1):
        a = selected[i]
        b = selected[i + 1]
        c += costs[a][b]
    return c

smallest = float('inf')

for p in permutations(rs):
    c = cost(p)
    if smallest > c:
        smallest = c

print(smallest)

Buggy submission (verdict: Runtime Error):
from collections import Counter

def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, m, r = read_line(int, int, int)

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

cities = Counter()

routes = {}
costs = {}
for _ in range(m):
    a, b, c = read_line(int, int, int)

    cities[a] = 1
    cities[b] = 1

    if a in routes:
        routes[a][b] = c
    else:
        routes[a] = { b : c }

    if b in routes:
        routes[b][a] = c
    else:
        routes[b] = { a : c }

for a in cities.keys():
    for b in cities.keys():
        if a not in costs:
            costs[a] = {}
        if b not in costs[a]:
            if a in routes and b in routes[a]:
                costs[a][b] = routes[a][b]
            else:
                costs[a][b] = 100000 + 1

# print('*')

keys = list(cities.keys())

for l in range(len(keys)):
    for i in range(len(keys)):
        for j in range(len(keys)):
            k = keys[l]
            a = keys[a]
            b = keys[b]

            c = costs[a][k] + costs[k][b]
            if a != b and costs[a][b] > c:
                costs[a][b] = c

# print('*')

def cost(selected):
    c = 0
    for i in range(len(selected) - 1):
        a = selected[i]
        b = selected[i + 1]
        c += costs[a][b]
    return c

smallest = 100000 + 1

def f(selected, rest):
    global smallest
    if len(rest) == 0:
        c = cost(selected)
        if smallest > c:
            smallest = c
    else:
        for i in range(len(rest)):
            r = rest[i]
            rest_copy = rest[:]
            del rest_copy[i]
            if len(selected) == 1 or cost(selected + [r]) < smallest:
                f(selected + [r], rest_copy)

f([], rs)
print(smallest)

Buggy submission (verdict: Runtime Error):
from collections import Counter
def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, m, r = read_line(int, int, int)

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

cities = Counter()

routes = {}
for _ in range(m):
    a, b, c = read_line(int, int, int)

    cities[a] = 1
    cities[b] = 1

    if a in routes:
        routes[a][b] = c
    else:
        routes[a] = { b : c }

    if b in routes:
        routes[b][a] = c
    else:
        routes[b] = { a : c }

def cost(selected):
    c = 0
    for i in range(len(selected) - 1):
        c += routes[selected[i]][selected[i + 1]]
    return c

def passing_all_cities(selected):
    for r in rs:
        if r not in selected:
            return False
    return True

x = []

def f(selected, rest):
    if passing_all_cities(selected):
        x.append(cost(selected))
    else:
        for i in range(len(rest)):
            r = rest[i]
            rest_copy = rest[:]
            del rest_copy[i]
            f(selected + [r], rest_copy)

f([], list(cities.keys()))
print(min(x))