Problem:


Score : 400 points

Problem Statement

There are N towns in the State of Atcoder, connected by M bidirectional roads.

The i-th road connects Town A_i and B_i and has a length of C_i.

Joisino is visiting R towns in the state, r_1,r_2,..,r_R (not necessarily in this order).

She will fly to the first town she visits, and fly back from the last town she visits, but for the rest of the trip she will have to travel by road.

If she visits the towns in the order that minimizes the distance traveled by road, what will that distance be?

Constraints

2≤N≤200

1≤M≤N×(N-1)/2

2≤R≤min(8,N) (min(8,N) is the smaller of 8 and N.)

r_i≠r_j (i≠j)

1≤A_i,B_i≤N, A_i≠B_i

(A_i,B_i)≠(A_j,B_j),(A_i,B_i)≠(B_j,A_j) (i≠j)

1≤C_i≤100000

Every town can be reached from every town by road.

All input values are integers.

Input

Input is given from Standard Input in the following format:

N M R
r_1 ... r_R
A_1 B_1 C_1
:
A_M B_M C_M

Output

Print the distance traveled by road if Joisino visits the towns in the order that minimizes it.

Sample Input 1

3 3 3
1 2 3
1 2 1
2 3 1
3 1 4

Sample Output 1

2

For example, if she visits the towns in the order of 1, 2, 3, the distance traveled will be 2, which is the minimum possible.

Sample Input 2

3 3 2
1 3
2 3 2
1 3 6
1 2 2

Sample Output 2

4

The shortest distance between Towns 1 and 3 is 4. Thus, whether she visits Town 1 or 3 first, the distance traveled will be 4.

Sample Input 3

4 6 3
2 3 4
1 2 4
2 3 3
4 3 1
1 4 1
4 2 2
3 1 6

Sample Output 3

3



Sample input:
3 3 3
1 2 3
1 2 1
2 3 1
3 1 4


Sample output:
2

Submission status: Runtime Error

Solution code:
import itertools

N, M, R = map(int, input().split())
r = map(int, input().split())
inf = float('inf')
d = [[inf for j in range(N)] for i in range(N)]

for i in range(N):
    d[i][i] = 0

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

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

ans = inf
for i in list(itertools.permutations(r)):
    temp = 0
    for j in range(len(i)):
        temp += d[i[j]-1][i[j+1]]
        if temp > ans:
            break
    ans = min(ans, temp)

print(ans)

Submission status: Runtime Error

Solution code:
import itertools

N, M, R = map(int, input().split())
r = map(int, input().split())
inf = float('inf')
d = [[inf for j in range(N)] for i in range(N)]

for i in range(N):
    d[i][i] = 0

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

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

ans = inf
for i in list(itertools.permutations(r)):
    temp = 0
    for j in range(len(i)):
        temp += d[i[j]-1][i[j+1]]
    ans = min(ans, temp)

print(ans)

Submission status: Runtime Error

Solution code:
def someone_ans():
    N, M, R = map(int, input().split())
    r = list(map(int, input().split()))
    graph = [[MAX for _ in range(N+1)] for _ in range(N+1)]
    for i in range(M):
        a, b, c = map(int, input().split())
        graph[a][b] = c
        graph[b][a] = c

    def dijkstra(d, index):
        q = queue.PriorityQueue()
        checked = []
        q.put((0, index))
        while not q.empty():
            # qの中の最小値だす
            cost, i = q.get()
            if i in checked: continue
            if cost == MAX: continue
            checked.append(i)
            d[index][i] = cost
            for j,v in enumerate(graph[i]):
                if v == MAX: continue
                if (j in checked) == False:
                    q.put((cost + graph[i][j], j))

        return d[index]
    ds = [[MAX for _ in range(N+1)] for _ in range(N+1)]

    # 自分から自分までの距離は0
    for i in range(1,N+1):
        ds[i][i] = 0

    for i in range(1,N+1):
        # 各地点からその他の地点までの最短距離を求める
        ds[i] = dijkstra(ds, i)
        for k in range(1,N+1):
            # k->iまでの距離はi->kと一緒
            ds[k][i] = ds[i][k]

    ans = MAX
    for l in itertools.permutations(r):
        cost = 0
        for i in range(1,R):
            cost += ds[l[i-1]][l[i]]
        ans = min(cost, ans)
    return ans

print(someone_ans())

Submission status: Runtime Error

Solution code:
import itertools


MAX = 999999999
def m():
    N, M, R = map(int, input().split())
    r = list(map(int, input().split()))
    graph = [[MAX for _ in range(N+1)] for _ in range(N+1)]
    for i in range(N):
        a, b, c = map(int, input().split())
        graph[a][b] = c
        graph[b][a] = c

    def dfs(start, end):

        pass

    def solve(d):
        for k in range(1,N+1):
            for j in range(1,N+1):
                for n in range(1,N+1):
                    d[j][n] = min(d[j][n], d[j][k] + d[k][n])
        return d

    for i in range(N): graph[i][i] = 0

    e = solve(graph)
    ans = MAX
    for l in itertools.permutations(r):
        cost = 0
        for i in range(1,R):
            cost += e[l[i-1]][l[i]]
        ans = min(cost, ans)
    return ans
print(m())

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# ワーシャルフロイド+全探索

import numpy as np
import itertools

def main():
    N, M, R = map(int, input().split())
    rs = [int(a)-1 for a in input().split())]
    inf = float('inf')
    cost = [[inf]*N for _ in range(N)]

    # グラフ作る
    for i in range(N):
        cost[i][i] = 0

    for _ in range(M):
        a, b, c = map(int, input().split())
        cost[a][b] = c
        cost[b][a] = c
    
    # ワーシャルフロイドで全頂点間距離算出
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if cost[i][k]+cost[k][j] < cost[i][j]:
                    cost[i][j] = cost[i][k] + cost[k][j]

    # 組み合わせ全探索
    ans = inf
    for route in itertools.permutations(rs):
        d = 0
        for i in range(R-1):
            d += cost[route[i]][route[i+1]]
            if d > ans:
                break
        ans = min(ans, d)
    
    print(int(ans))


if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
from itertools import permutations

N, M, R = map(int, raw_input().split())
r = [i - 1 for i in map(int, raw_input().split())]

G = [[float('inf')] * N for _ in range(N)]

for i in range(N):
    G[i][i] = 0

for i in range(M):
    A, B, C = map(int, raw_input().split())
    G[A-1][B-1] =  G[B-1][A-1] = C

# Warshall–Floyd Algorithm
for k in range(N):
    for i in range(N):
        for j in range(N):
            G[i][j] = min(G[i][j], G[i][k] + G[k][j]); 

ans = float('inf')

for i in permutations(r):
    t = 0
    for j in range(R-1):
        t += G[i[j]][i[j+1]]

    ans = min(ans, t)

print ans

Submission status: Runtime Error

Solution code:
def permutations(L):
    if L == []:
        return [[]]
    else:
        return [[h]+t for i,h in enumerate(L)
                      for t   in permutations(L[:i]+L[i+1:])]

inputs = input().split()
N = int(inputs[0])
M = int(inputs[1])
R = int(inputs[2])

inputs = input()
cities = [ x+1 for x in range(N)]

dist = [[0 for y in range(M + 1)] for x in range(M + 1)]

for i in range(M):
    inputs = input().split()
    dist[int(inputs[0])][int(inputs[1])] = int(inputs[2])
    dist[int(inputs[1])][int(inputs[0])] = int(inputs[2])

ans = 100000000000
for rl in permutations(cities):
    now = 0
    for i in range(len(rl) - 1):
        now += dist[rl[i]][rl[i+1]]
    if ans > now and now != 0:
        ans = now

print(ans)

Submission status: Runtime Error

Solution code:
def permutations(L):
    if L == []:
        return [[]]
    else:
        return [[h]+t for i,h in enumerate(L)
                      for t   in permutations(L[:i]+L[i+1:])]

inputs = input().split()
N = int(inputs[0])
M = int(inputs[1])
R = int(inputs[2])

cities = []
inputs = input().split()

for i in inputs:
    cities.append(int(i))

dist = [[0 for y in range(M + 1)] for x in range(M + 1)]

for i in range(M):
    inputs = input().split()
    dist[int(inputs[0])][int(inputs[1])] = int(inputs[2])
    dist[int(inputs[1])][int(inputs[0])] = int(inputs[2])

ans = 100000000000
for rl in permutations(cities):
    now = 0
    for i in range(len(rl) -1 ):
        now += dist[rl[i]][rl[i+1]]
    if ans > now and now != 0:
        ans = now

print(ans)

Submission status: Runtime Error

Solution code:
from itertools import permutations
import sys

N, M, R = map(int, sys.stdin.readline().split())
r = [int(i) - 1 for i in sys.stdin.readline().split()]
d = [[float('inf')] * N for j in range(N)]
for i in range(M):
    A, B, C = map(int, sys.stdin.readline().split())
    d[A-1][B-1] = min(d[A-1][B-1], C)
    d[B-1][A-1] = min(d[B-1][A-1], C)
for k in range(N):
    for s in range(N):
        for e in range(N):
            d[s][e] = min(d[s][e], d[s][k] + d[k][e])
l = float('inf')
for o in permutations(r):
    tmp_l = 0
    for i in range(len(o[:-1]))
        tmp_l = tmp_l + d[i][i+1]
    l = min(l, tmp_l)
print(l)

Submission status: Runtime Error

Solution code:
import math
def nextPermutation(order):
	if len(order) == 1:
		yield order
	elif len(order) == 2:
		yield order
		yield [order[1],order[0]]
	else:
		for i in range(len(order)):
			for _order in nextPermutation(order[:i]+order[(i+1):]):
				yield [order[i]]+_order


def solution():
	n,m,r = [int(x) for x in input().split(' ')]
	R = [int(x) for x in input().split(' ')]
	matrix = []
	for i in range(n):
		matrix.append([math.inf]*n)

	for i in range(m):
		arc = [int(x) for x in input().split(' ')]
		matrix[arc[0]-1][arc[1]-1] = arc[2]
		matrix[arc[1]-1][arc[0]-1] = arc[2]

	for k in range(n):
		for j in range(n):
			for i in range(n):
				matrix[i][j] = min(matrix[i][j],matrix[i][k]+matrix[k][j])
	_min = math.inf
	for order in nextPermutation(R):
		val = 0
		for i in range(1,r):
			val += matrix[order[i-1]-1][order[i]-1]
		if val < _min:
			_min = val

	return _min

print(solution())

Submission status: Runtime Error

Solution code:
n,m,r = map(int,input().split())
r_l = [int(i)-1 for i in input().split()]
dist=dict()
for i in range(m):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    dist[(a,b)]=c  
    dist[(b,a)]=c

res=[]
for s in r_l:
    F=[[s]]

    while True:
        c=0
        i=F.pop(0)
        now=i[-1]
        for k in range(n):
            if (now,k) in dist:
                if k not in i and i+[k] not in res and i+[k] not in F:
                    F.append(i+[k])
                    c+=1
            else:
                pass
        res.append(i)
        if c==0:
            break
    res.extend(F)

F=[]
for r in res:
    for s in r_l:
        if s not in r:
            break
    else:
        F.append(sum(dist[(r[i],r[i+1])] for i in range(len(r)-1)))#:
            
print(min(F))

Submission status: Runtime Error

Solution code:
N, M, R = map(int, input().split())
r = list(map(lambda x: int(x) - 1, input().split()))

import numpy as np

array = np.full((N, N), np.inf)
for _ in range(M):
    a, b, c = map(int, input().split())
    array[a - 1, b - 1] = c


# this is destructive
def warshal_floyd(d, n, inf):
  d[d == 0] = inf
  for k in range(n):
    d = np.minimum(d, d[:,k,None]+d[None,k,:])
  return d


def it2():
    from itertools import permutations
    for p in permutations(r):
        pp = iter(p)
        next(pp)
        yield sum(array[a, b] for a, b in zip(p, pp))

array = warshal_floyd(array, N, np.inf)
print(int(min(it2())))

Submission status: Runtime Error

Solution code:
N, M, R = map(int, input().split())
r = list(map(lambda x: int(x) - 1, input().split()))

import numpy as np

array = np.full((N, N), np.inf)
for _ in range(M):
    a, b, c = map(int, input().split())
    array[a - 1, b - 1] = c


# this is destructive
def warshal_floyd(d, n, inf):
  d[d == 0] = inf
  for k in range(n):
    d = np.minimum(d, d[:,k,None]+d[None,k,:])
  return d


def it2():
    from itertools import permutations
    for p in permutations(r):
        pp = iter(p)
        next(pp)
        yield sum(array[a, b] for a, b in zip(p, pp))


print(int(min(it2())))

Submission status: Runtime Error

Solution code:
from itertools import permutations

def input_list() :
    return list(map(int, input().split()))

n, m ,r = input_list()
road = input_list()
road = [x-1 for x in road]
d = [[float('inf')] * n for i in range(n)]
for i in range(n) :
    d[i][i] = 0
for i in range(m) :
    a, b, c = input_list()
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = c

for k in range(n) :
    for i in range(n) :
        for j in range(n) :
            dist = d[i][k]+d[k][j]
            if d[i][j] > dist :
            d[i][j] = dist

ans = float('inf')
for p in permutations(road) :
    dist = 0
    for i in range(r-1) :
        dist += d[p[i]][p[i+1]]
    if ans > dist :
        ans = dist

print(ans)

Submission status: Runtime Error

Solution code:
from itertools import permutations

def input_list() :
    return list(map(int, input().split()))

n, m ,r = input_list()
road = input_list()
road = [x-1 for x in road]
d = [[float('inf')] * n for i in range(n)]
for i in range(n) :
    d[i][i] = 0
for i in range(m) :
    a, b, c = input_list()
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = c

for k in range(n) :
    for i in range(n) :
        for j in range(n) :
            dist = d[i][k]+d[k][j]
            if d[i][j] > dist
            d[i][j] = dist

ans = float('inf')
for p in permutations(road) :
    dist = 0
    for i in range(r-1) :
        dist += d[p[i]][p[i+1]]
    if ans > dist :
        ans = dist

print(ans)

Submission status: Runtime Error

Solution code:
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()

Submission status: Runtime Error

Solution code:
n,m,r=map(int,input().split())
r=list(map(int,input().split()))
cost=[[999999999999 if i!=j else 0 for j in range(n)] for i in range(n)]
for _ in range(m):
    a,b,c=map(int,input().split())
    cost[a-1][b-1]=cost[b-1][a-1]=c
for k in range(n):
    for i in range(n):
        for j in range(n): 
            cost=min(cost[i][j],cost[i][k]+cost[k][j])            
d=[[cost[y-1][x-1] for x in r] for y in r]
print(max(map(max,d)))

Submission status: Runtime Error

Solution code:
#coding:utf-8

from collections import defaultdict
import itertools

inf = 10 ** 9

N, M, R = map(int, input().split(" "))
r_list = map(int, input().split(" "))

cost = defaultdict(dict)
for i in range(1, N + 1):
    for j in range(i, N + 1):
        if i == j:
            cost[i][j] = 0
        else:
            cost[i][j] = inf
for i in range(M):
    A, B, C = map(int, input().split(" "))
    cost[A][B] = cost[B][A] = C

#get shortest path for each node pair
for k in range(1, N + 1):
    for i in range(1, N + 1):
        for j in range(i, N + 1):
            cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])

min_dist = inf
for route in itertools.permutations(r_list):
    dist = 0
    for i in range(len(route) - 1):
        min_arg = min(route[i], route[i + 1])
        max_arg = max(route[i], route[i + 1])
        dist += cost[min_arg][max_arg]
    min_dist = min(dist, min_dist)
print(min_dist)

Submission status: Runtime Error

Solution code:
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()

Submission status: Runtime Error

Solution code:
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()

Submission status: Runtime Error

Solution code:
import itertools
import math

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

adj = [[math.inf]*(N+1) for _ in range(N+1)]

for _ in range(M):
    A, B, C = map(int, input().split())
    adj[A][B] = min(adj[A][B], C)
    adj[B][A] = min(adj[B][A], C)

res = math.inf

for k in range(1, N+1):
    for i in range(1, N+1):
        for j in range(1, N+1):
            adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j])

for perm in itertools.permutations(r):
    best = 0
    for x, y in zip(perm, perm[1:]):
        best += adj[x][y]
    res = min(res, best)

print(res)

Submission status: Runtime Error

Solution code:
from scipy.sparse import*;f=lambda:list(map(int,input().split()));N,M,R=f();r=f();a,b,c=zip(*map(f,[0]*M));a=csgraph.dijkstra(csr_matrix((c,(a,b)),[N+1]*2),0,r);print(int(min(sum(a[e[i]][r[e[i+1]]]for i in range(R-1))for e in __import__('itertools').permutations(range(R)))))

Submission status: Runtime Error

Solution code:
from scipy.sparse import*;f=lambda:map(int,raw_input().split());N,M,R=f();r=f();a,b,c=zip(*map(f,[0]*M));a=csgraph.dijkstra(csr_matrix((c,(a,b)),[N+1]*2),0,r);print int(min(sum(a[e[i]][r[e[i+1]]]for i in range(R-1))for e in __import__('itertools').permutations(range(R))))

Submission status: Runtime Error

Solution code:
4 6 3
2 3 4
1 2 4
2 3 3
4 3 1
1 4 1
4 2 2
3 1 6

Submission status: Runtime Error

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n,m,r=na()
rs = na()
for i in range(r):
    rs[i] -= 1

g = [[99999999999]*n for _ in range(n)]
for i in range(n):
    g[i][i] = 0
for i in range(m):
    a, b, c = na()
    a -= 1
    b -= 1
    g[a][b] = g[b][a] = c

from heapq import *
def dijkstra(g, start):
    n = len(g)
    ds = [1e18] * n
    ds[start] = 0
    h = []
    heappush(h, (0, start))
    while len(h) > 0:
        d, cur = heappop(h)
        if d != ds[cur]: continue
        for e, ew in g[cur]:
            if d + ew < ds[e]:
                ds[e] = d + ew
                heappush(h, (ds[e], e))
    return ds

def dijkstra_dense(g, start):
    n = len(g)
    ds = [1e18] * n
    ds[start] = 0

    done = [0] * n
    while True:
        lmin = 1e19
        arg = -1
        for i in range(n):
            if not done[i] and ds[i] < lmin:
                lmin = ds[i]
                arg = i
        if arg == -1: break
        done[arg] = 1
        for i in range(n):
            ds[i] = min(ds[i], lmin + g[arg][i])
    return ds


dss = [None] * n
for r in rs:
    dss[r] = dijkstra_dense(g, r)

from itertools import *

ans = 9999999999999999999
for ord in permutations(rs):
    w = 0
    for i in range(1, r):
        w += dss[ord[i-1]][ord[i]]
    ans = min(ans, w)
print(ans)

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
#coding=UTF-8

def search(jun):
    global ans
    global R
    global rrCost
    tmpans=0
    if len(jun)==R:
        mae=jun[0]
        for idx in range(1,R,1):
            ba=jun[idx]
            tmpans += rrCost[mae][ba]
            mae=ba

        if ans==None or tmpans<ans:
            ans=tmpans
    else:
        for me in range(0,R,1):
            if not (me in jun):
                search(jun+[me])

mozir=input()
hyo=mozir.split(' ')
N=int(hyo[0])
M=int(hyo[1])
R=int(hyo[2])

mozir=input()
hyo=mozir.split(' ')
r=[(int(mono)-1) for mono in hyo]

michi=[]
for idx in range(0,M,1):
    mozir=input()
    hyo=mozir.split(' ')
    A=int(hyo[0])-1
    B=int(hyo[1])-1
    C=int(hyo[2])

    michi.append((A,B,C))
    michi.append((B,A,C))

rrCost=[]
for idx in range(0,R,1):
    rrCost.append([None]*R)

for idx in range(0,R,1):
    rrCost[idx][idx]=0

for idr in range(0,R,1):
    deCost=[None]*N
    deCost[r[idr]]=0
    
    miru=[]
    for mono in michi:
        if mono[0] == r[idr]:
            deCost[mono[1]]=mono[2]
            miru.append(mono[1])

    while miru:
        nextmiru=[]

        for me in miru:
            preCost=deCost[me]
            for mono in michi:
                if mono[0] == me:
                    tmpCost=preCost+mono[2]
                    if deCost[mono[1]]==None or deCost[mono[1]]>tmpCost:
                        deCost[mono[1]]=tmpCost
                        nextmiru.append(mono[2])

        miru=list(set(nextmiru))

    for idx in range(0,R,1):
        rrCost[idr][idx]=deCost[r[idx]]
        rrCost[idx][idr]=deCost[r[idx]]


ans=None
search([])
print(ans)

Submission status: Runtime Error

Solution code:
N,M,R = map(int,input().split())
r = list(map(int,input().split()))
from itertools import permutations
t = [[float('inf') for i in range(M)] for j in range(M)]

for i in range(M):
    a,b,c = map(int, input().split())
    t[a-1][b-1] = c
    t[b-1][a-1] = c

for i in range(M):
    for j in range(M):
        for k in range(M):
            if t[i][j] > t[j][k] + t[k][j]:
                t[i][j] = t[j][k] + t[k][j]

def c(l):
    last = len(l) - 1
    ret = 0
    for i,j in enumerate(l):
        if i == last:
            return ret
        ret += t[j-1][l[i+1]-1]

print(min([c(i) for i in permutations(r)]))

Submission status: Runtime Error

Solution code:
N,M,R = map(int,input().split())
r = list(map(int,input().split()))
from itertools import permutations
t = [[float('inf') for i in range(M)] for j in range(M)]

g = {}
for i in range(M):
    a,b,c = map(int, input().split())
    t[a-1][b-1] = c
    t[b-1][a-1] = c
    v = g.get(a,[])
    v.append((b,c))
    g[a] = v
    v = g.get(b,[])
    v.append((a,c))
    g[b] = v

for i in range(M):
    for j in range(M):
        for k in range(M):
            if t[i][j] > t[j][k] + t[k][j]:
                t[i][j] = t[j][k] + t[k][j]

def c(l):
    last = len(l) - 1
    ret = 0
    for i,j in enumerate(l):
        if i == last:
            return ret
        ret += t[j-1][l[i+1]-1]

print(min([c(i) for i in permutations(r)]))

Submission status: Runtime Error

Solution code:
import math
def solution():
	n,m,r = [int(x) for x in input().split(' ')]
	v = input().split(' ')
	w = []
	graph = {}
	for i in range(m):
		a,b,c =input().split(' ')
		c = int(c)
		if a not in graph:
			graph[a] = []
		if b not in graph:
			graph[b] = []
		graph[a].append((b,c))
		graph[b].append((a,c))
		w.append((a,b,c))
	w = sorted(w,key=lambda x:x[2])

	ans,visited = visit('',[],0,graph,w)


	print(ans)

def visit(current, visited,w,graph,roads):

	if current == '':
		w1,visited1 = visit(roads[0][0],visited,w,graph,roads)
		w2,visited2 = visit(roads[0][1],visited,w,graph,roads)
		return (w1,visited1) if w1>w2 else (w2,visited2)
	mini = math.inf
	vis = [] 
	for  _to,_w in graph[current]:
		if _to in visited:
			continue
		__w,__visited = visit(_to,visited+[current],w+_w,graph,roads)
		if __w< mini:
			mini = __w
			vis = __visited

	return mini,visited




solution()

Submission status: Runtime Error

Solution code:
import itertools

N, M, R = [int(i) for i in input().split()]
must_visit = [int(i) for i in input().split()]
max_city = max(must_visit)
cities = [i+1 for i in range(max_city)]
min_cost = 999999999
dic = {}

for _ in range(M):
	dept, dest, dist = [int(i) for i in input().split()]
	if dest < dept:
		dest, dept = dept, dest
	key1, key2 = "{}->{}".format(dept, dest),"{}->{}".format(dest, dept)
	if key1 in dic:
		dic[key1] = dist if dist < dic[key1] else dic[key1]
		dic[key2] = dist if dist < dic[key2] else dic[key2]
	else:
		dic[key1], dic[key2] = dist, dist

for c in list(itertools.permutations(cities)):
	visited = set()
	cost = 0
	if c[0] != must_visit[0]:
		continue
	for i,k in enumerate(c):
		visited.add(k)
		if set(must_visit) - set(visited) == set() or min_cost < cost:
			break
		cost += dic["{}->{}".format(k,c[i+1])]
	min_cost = cost if min_cost > cost else min_cost

print(min_cost)

Submission status: Runtime Error

Solution code:
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))

Submission status: Runtime Error

Solution code:
import itertools

N, M, R = [int(i) for i in input().split()]
must_visit = [int(i) for i in input().split()]
max_city = max(must_visit)
cities = [i+1 for i in range(max_city)]
min_cost = 999999999
dic = {}

for _ in range(M):
	dept, dest, dist = [int(i) for i in input().split()]
	if dest < dept:
		dest, dept = dept, dest
	key1, key2 = "{}->{}".format(dept, dest),"{}->{}".format(dest, dept)
	if key1 in dic:
		dic[key1] = dist if dist < dic[key1] else dic[key1]
		dic[key2] = dist if dist < dic[key2] else dic[key2]
	else:
		dic[key1], dic[key2] = dist, dist

for c in list(itertools.permutations(cities)):
	visited = set()
	cost = 0
	for i,k in enumerate(c):
		visited.add(k)
		if set(must_visit) - set(visited) == set():
			break
		cost += dic["{}->{}".format(k,c[i+1])]
		if min_cost < cost: break
	min_cost = cost if min_cost > cost else min_cost

print(min_cost)

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:

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()