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

Solution (Python):
from itertools import permutations
from scipy.sparse.csgraph import floyd_warshall
n,m,r=map(int,input().split())
vis=list(map(int,input().split()))
INF=10**18
path=[[INF]*n for i in range(n)]
for i in range(m):
  a,b,c=map(int,input().split())
  path[a-1][b-1]=c
  path[b-1][a-1]=c
path=floyd_warshall(path)
ans=10**18
for root in permutations(vis):
  cnt=0
  for j in range(1,r):
    cnt+=path[root[j-1]-1][root[j]-1]
  ans=min(ans,cnt)
print(int(ans))

Solution (Python):
from itertools import permutations
from scipy.sparse.csgraph import floyd_warshall

INF = 10 ** 18
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
dp = [[INF for _ in range(N)] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j:
            dp[i][j] = 0

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

wf = floyd_warshall(dp)
ans = INF
for i in permutations(r):
    tmp = 0
    for j in range(1, len(i)):
        tmp += wf[i[j - 1] - 1][i[j] - 1]
    ans = min(ans, tmp)

print(int(ans))

Solution (Python):
from itertools import permutations
def warshallFloyd():
    for i in range(N):
        for j in range(N):
            for k in range(N):
                dp[j][k] = min(dp[j][k], dp[j][i] + dp[i][k])
    return

INF = 10 ** 18
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
dp = [[INF for _ in range(N)] for _ in range(N)]
ansF = False
for i in range(N):
    for j in range(N):
        if i == j:
            dp[i][j] = 0

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

warshallFloyd()
ans = INF
for i in permutations(r):
    tmp = 0
    for j in range(1, len(i)):
        tmp += dp[i[j - 1] - 1][i[j] - 1]
    ans = min(ans, tmp)

print(ans)

Solution (Python):
from itertools import permutations

N, M, R = map(int, input().split())
r = list(map(lambda x: int(x) - 1, input().split()))
d = [[float("inf") for _ in range(N)] for _ in range(N)] 
for i in range(M):
    x, y, z = map(int, input().split())
    d[x-1][y-1] = min(d[x-1][y-1], z)
    d[y-1][x-1] = min(d[x-1][y-1], z)
for i in range(N):
    d[i][i] = 0

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

short_dist = warshall_floyd(d)

ans = float('inf')
for ptn in permutations(r):
    dist = 0
    for x, y in zip(ptn, ptn[1:]):
        dist += short_dist[x][y]
    ans = min(ans, dist)
        
print(ans)

Solution (Python):
from collections import *
from itertools import *
import copy
from heapq import *


N,M,R=map(int,input().split())
Rlst=list(map(int,input().split()))
ABC=[list(map(int,input().split())) for i in range(M)]

data=[[] for i in range(N+1)]
nagasa={}
for a,b,c in ABC:
    data[a].append(b)
    data[b].append(a)
    A,B=min(a,b),max(a,b)
    nagasa.update({str(A)+" "+str(B):c})
mokutekiti=[[100000*200+1 for i in range(R)] for m in range(R)]
for r1i in range(R-1):
    for r2i in range(r1i+1,R):
        r1=Rlst[r1i]
        r2=Rlst[r2i]
        visited=set()
        stack=[0]
        heapify(stack)
        dic={0:[r1]}
        kyori=set([0])
        while stack:
            m=heappop(stack)
            
            
            a=dic[m].pop()
            if a==r2:
                break
            if not a in visited:
                visited.add(a)
                for b in data[a]:
                    if not b in visited or b==r2:
                        A,B=min(a,b),max(a,b)
                        tempm=m+nagasa[str(A)+" "+str(B)]
                        if b==r2:
                            if mokutekiti[r1i][r2i]>tempm:
                                mokutekiti[r1i][r2i]=tempm
                                mokutekiti[r2i][r1i]=tempm
                            heappush(stack,tempm)
                            if tempm in kyori:
                                dic[tempm].append(b)
                            else:
                                kyori.add(tempm)
                                dic.update({tempm:[b]})

                        else:
                            heappush(stack,tempm)
                            if tempm in dic:
                                dic[tempm].append(b)
                            else:
                                dic.update({tempm:[b]})



value=[]
for lst in permutations([i for i in range(R)],R):
    nagasa=0
    for i in range(R-1):
        nagasa+=mokutekiti[lst[i]][lst[i+1]]
    value.append(nagasa)
print(min(value))

Solution (Python):
N,M,R = map(int,input().split())
r = list(map(int,input().split()))
r.sort()
G = [[10**9 for i in range(N+1)] for j in range(N+1)]
for i in range(M):
    a,b,c = map(int,input().split())
    G[a][b] = min(G[a][b],c)
    G[b][a] = G[a][b]
def warshall_floyd(d):
    
    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])
    return d
warshall_floyd(G)
import itertools
ans = 10**9
for v in itertools.permutations(r):
    v = list(v)
    a = 0
    s = v.pop(0)
    for i in range(R-1):
        t = v[i]
        a += G[s][t]
        s = t
    ans = min(a,ans)
print(ans)

Solution (Python):
import itertools
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
m = [[10**10]*N for i in range(N)]

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

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

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

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

print(ans)

Solution (Python):
import heapq
from itertools import permutations
def dijkstra(n, tc_edges, s):
    
    min_dist = [float('inf')] * n
    min_dist[s] = 0
    next_v = []
    heapq.heappush(next_v, (0, s))
    
    while True:
        if len(next_v) == 0: break
        d, v = heapq.heappop(next_v)
        
        for u, d in tc_edges[v]:
            if min_dist[u] > min_dist[v] + d:
                min_dist[u] = min_dist[v] + d
                heapq.heappush(next_v, (min_dist[u], u))
                
    return min_dist
    
n, m, r = map(int, input().split())
r = list(map(int, input().split()))
edge = [[] for _ in range(n)]

for _ in range(m):
    a, b, c = map(int, input().split())
    edge[a-1].append([b-1, c])
    edge[b-1].append([a-1, c])

dist = [dijkstra(n, edge, i) for i in range(n)]

ans = float('inf')
for pr in permutations(r):
    temp = 0
    for i in range(len(r)-1):
        temp += dist[pr[i]-1][pr[i+1]-1]
        if temp >= ans: break
    
    ans = min(ans, temp)
    
print(ans)

Solution (Python):
from itertools import permutations
N,M,R = list(map(int,input().split()))
r = list(map(int,input().split()))
r = [i-1 for i in r]
ABC = [[float('inf') for i in range(N)]for j in range(N)]
for i in range(N):
    ABC[i][i] = 0
for i in range(M):
    a,b,c = list(map(int,input().split()))
    a -= 1
    b -= 1
    ABC[a][b] = c
    ABC[b][a] = c
for k in range(N):
    for i in range(N):
        for j in range(N):
            ABC[i][j] = min(ABC[i][j],ABC[i][k]+ABC[k][j])
ans = float('inf')
for i in permutations(r):
    cost = 0
    now = i[0]
    for j in range(1,len(i)):
        cost += ABC[now][i[j]]
        now = i[j]
    ans = min(ans,cost)
print(ans)

Solution (Python):
from collections import *
from itertools import *
import copy
from heapq import *


N,M,R=map(int,input().split())
Rlst=list(map(int,input().split()))
ABC=[list(map(int,input().split())) for i in range(M)]

data=[[] for i in range(N+1)]
nagasa={}
for a,b,c in ABC:
    data[a].append(b)
    data[b].append(a)
    A,B=min(a,b),max(a,b)
    nagasa.update({str(A)+" "+str(B):c})
mokutekiti=[[100000*200+1 for i in range(R)] for m in range(R)]
for r1i in range(R-1):
    for r2i in range(r1i+1,R):
        r1=Rlst[r1i]
        r2=Rlst[r2i]
        visited=set()
        stack=[0]
        heapify(stack)
        dic={0:[r1]}
        while stack:
            m=heappop(stack)
            
            
            a=dic[m].pop()
            if a==r2:
                break
            if not a in visited:
                visited.add(a)
                for b in data[a]:
                    if not b in visited or b==r2:
                        A,B=min(a,b),max(a,b)
                        tempm=m+nagasa[str(A)+" "+str(B)]
                        if b==r2:
                            if mokutekiti[r1i][r2i]>tempm:
                                mokutekiti[r1i][r2i]=tempm
                                mokutekiti[r2i][r1i]=tempm
                            heappush(stack,tempm)
                            if tempm in dic:
                                dic[tempm].append(b)
                            else:
                                dic.update({tempm:[b]})

                        else:
                            heappush(stack,tempm)
                            if tempm in dic:
                                dic[tempm].append(b)
                            else:
                                dic.update({tempm:[b]})



value=[]
for lst in permutations([i for i in range(R)],R):
    nagasa=0
    for i in range(R-1):
        nagasa+=mokutekiti[lst[i]][lst[i+1]]
    value.append(nagasa)
print(min(value))

Solution (Python):
from collections import *
from itertools import *
import copy
from heapq import *


N,M,R=map(int,input().split())
Rlst=list(map(int,input().split()))
ABC=[list(map(int,input().split())) for i in range(M)]

data=[[100000*200+1 for i in range(N)] for i in range(N)]
for a,b,c in ABC:
    data[a-1][b-1]=c
    data[b-1][a-1]=c

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



value=[]
for lst in permutations([i for i in range(R)],R):
    nagasa=0
    for i in range(R-1):
        nagasa+=data[Rlst[lst[i]]-1][Rlst[lst[i+1]]-1]
    value.append(nagasa)
print(min(value))

Solution (Python):
from collections import *
from itertools import *
import copy
from heapq import *


N,M,R=map(int,input().split())
Rlst=list(map(int,input().split()))
ABC=[list(map(int,input().split())) for i in range(M)]

data=[[] for i in range(N+1)]
nagasa={}
for a,b,c in ABC:
    data[a].append(b)
    data[b].append(a)
    A,B=min(a,b),max(a,b)
    nagasa.update({str(A)+" "+str(B):c})
mokutekiti=[[100000*200+1 for i in range(R)] for m in range(R)]
for r1i in range(R-1):
    for r2i in range(r1i+1,R):
        r1=Rlst[r1i]
        r2=Rlst[r2i]
        visited=set()
        stack=[0]
        heapify(stack)
        dic={0:[r1]}
        while stack:
            m=heappop(stack)
            
            
            a=dic[m].pop()
            if not a in visited:
                visited.add(a)
                for b in data[a]:
                    if not b in visited or b==r2:
                        A,B=min(a,b),max(a,b)
                        tempm=m+nagasa[str(A)+" "+str(B)]
                        if b==r2:
                            if mokutekiti[r1i][r2i]>tempm:
                                mokutekiti[r1i][r2i]=tempm
                                mokutekiti[r2i][r1i]=tempm
                        else:
                            heappush(stack,tempm)
                            if tempm in dic:
                                dic[tempm].append(b)
                            else:
                                dic.update({tempm:[b]})



value=[]
for lst in permutations([i for i in range(R)],R):
    nagasa=0
    for i in range(R-1):
        nagasa+=mokutekiti[lst[i]][lst[i+1]]
    value.append(nagasa)
print(min(value))

Solution (Python):
from scipy.sparse.csgraph import csgraph_from_dense,dijkstra,floyd_warshall
N,M,R = map(int,input().split())

machi = list(map(int,input().split()))

List = [[10**6]*(N) for i in range(N)]
for i in range(M):
  a,b,c = map(int,input().split())
  
  if List[a-1][b-1] > c:
    List[a-1][b-1] = c
    List[b-1][a-1] = c
G = csgraph_from_dense(List, null_value=10**6)
d = floyd_warshall(G)

import itertools
a = list(itertools.permutations(machi))
arr = []
for i in a:
  ans = 0
  for j in range(R):
    if j != R-1 :
      ans += d[i[j]-1][i[j+1]-1]
  arr.append(ans) 
  
print(int(min(arr)))

Solution (Python):
import itertools

N, M, r = map(int, input().split())
R = list(map(int, input().split()))
E = [[10 ** 20 if i != j else 0 for i in range(N)] for j in range(N)]
for _ in range(M):
    A, B, C = map(int, input().split())
    A -= 1
    B -= 1
    E[A][B] = C
    E[B][A] = C

for d in range(N):
    for v in range(N):
        for w in range(N):
            E[v][w] = min(E[v][w], E[w][v], E[v][d] + E[d][w])
            E[w][v] = E[v][w]

res = 10 ** 20
for case in itertools.permutations(R):
    tmp = 0
    c = list(case)
    for i in range(r - 1):
        tmp += E[c[i] - 1][c[i + 1] - 1]
    res = min(res, tmp)

print(res)

Solution (Python):
from itertools import permutations
 
N, M, R = map(int, input().split())
r = [a-1 for a in [int(x) for x in input().split()]]
d = [[float("inf")]*N for _ in range(N)]

for i in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = 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] = d[i][k]+d[k][j]

for p in permutations(r):
    distance = 0
    for i in range(len(p)-1):
        distance += d[p[i]][p[i+1]]
    res = min(distance, res)

print(res)

Solution (Python):
from sys import stdout
import itertools
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,m,rr = inm()
r = inl()
r = [x-1 for x in r]
dst = [ [] for i in range(n) ]
for i in range(m):
    a,b,c = inm()
    dst[a-1].append((b-1,c))
    dst[b-1].append((a-1,c))

ddprint("n {} m {} r {}".format(n,m,rr))
ddprint(dst)


dist = [ [BIG]*n for i in range(n) ]
for i in range(n):
    dist[i][i] = 0
    for j,c in dst[i]:
        dist[i][j] = c
for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])

ddprint("dist")
ddprint(dist)

pm = itertools.permutations(r,rr)
mn = BIG
for p in pm:
    sm = 0
    
    for i in range(rr-1):
        sm += dist[p[i]][p[i+1]]
    mn = min(mn,sm)
print(mn)

Solution (Python):
import numpy as np
from scipy.sparse.csgraph import dijkstra

N,M,R = list(map(int,input().split()))
r = list(map(int,input().split()))
for i in range(R):
    r[i] -= 1

connections = np.zeros((N,N))
for i in range(M):
    A,B,C = list(map(int,input().split()))
    A,B = A-1,B-1
    
    connections[A][B] = C
    connections[B][A] = C

connections = dijkstra(connections)

def explore(unvisited,total,start):
    if unvisited:
        ret = float('inf')
        for town in unvisited:
            ret = min(ret,explore(unvisited-set([town]),
                total+connections[start][town],town))
        return ret
    else:
        return total

ans = float('inf')
targets = set(r)
for s in r:
    ans = min(ans,explore(targets-set([s]),0,s))
print(int(ans))

Solution (Python):
import itertools
import sys
from scipy.sparse.csgraph import csgraph_from_dense
from scipy.sparse.csgraph import dijkstra
input = sys.stdin.readline


n, m, r = map(int, input().split())
visiting_town = list(map(int, input().split()))
edges = [[float('INF')]*n for _ in range(n)]

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

G = csgraph_from_dense(edges, null_value=float('INF'))
comp_dist = {}
for node in visiting_town:
    dist_list = dijkstra(G, directed=False, indices=node-1)
    comp_dist[node-1] = dist_list

candidates = []
for route in itertools.permutations(visiting_town):
    result = 0
    for _from, to in zip(route[:-1], route[1:]):
        dist = comp_dist[_from-1][to-1]
        result += dist
    candidates.append(result)

print(int(min(candidates)))

Solution (Python):
import itertools
import sys
from scipy.sparse.csgraph import csgraph_from_dense
from scipy.sparse.csgraph import dijkstra
input = sys.stdin.readline


n, m, r = map(int, input().split())
visiting_town = list(map(int, input().split()))
edges = [[float('INF')]*n for _ in range(n)]

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

G = csgraph_from_dense(edges, null_value=float('INF'))
comp_dist = dijkstra(G, directed=False)

candidates = []
for route in itertools.permutations(visiting_town):
    result = 0
    for _from, to in zip(route[:-1], route[1:]):
        dist = comp_dist[_from-1][to-1]
        result += dist
    candidates.append(result)

print(int(min(candidates)))

Solution (Python):
import itertools
import sys
from scipy.sparse.csgraph import csgraph_from_dense
from scipy.sparse.csgraph import floyd_warshall
input = sys.stdin.readline


n, m, r = map(int, input().split())
visiting_town = list(map(int, input().split()))
edges = [[float('INF')]*n for _ in range(n)]

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

G = csgraph_from_dense(edges, null_value=float('INF'))
comp_dist = floyd_warshall(G, directed=False)

candidates = []
for route in itertools.permutations(visiting_town):
    result = 0
    for _from, to in zip(route[:-1], route[1:]):
        dist = comp_dist[_from-1][to-1]
        result += dist
    candidates.append(result)

print(int(min(candidates)))

Solution (Python):
import heapq
import itertools
from collections import defaultdict


n, m, r = map(int, input().split())
visiting_town = list(map(int, input().split()))

edges = [[] for i in range(n+1)]
for _ in range(m):
    _from, to, distance = map(int, input().split())
    edges[_from].append([to, distance])
    edges[to].append([_from, distance])


comp_edges = defaultdict(dict)
for _from in visiting_town:
    seen = [False] * (n+1)
    todo = []
    for to, dist in edges[_from]:
        heapq.heappush(todo, [dist, to])

    while todo:
        dist, node = heapq.heappop(todo)
        if seen[node]:
            continue

        seen[node] = dist
        for to, add_dist in edges[node]:
            if seen[to] or to == _from:
                continue
            new_dist = dist + add_dist
            heapq.heappush(todo, [new_dist, to])

    for to in visiting_town:
        if to == _from:
            continue
        comp_edges[_from][to] = seen[to]

candidates = []
for route in itertools.permutations(visiting_town):
    result = 0
    for _from, to in zip(route[:-1], route[1:]):
        if to in comp_edges[_from]:
            dist = comp_edges[_from][to]
            result += dist
        else:
            break
    candidates.append(result)

print(min(candidates))

Solution (Python):
import itertools
n, m, r = map(int, input().split())
t = list(map(int, input().split()))
t.sort()
d = [[10 ** 18]*n for j 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
    d[a][b] = c
    d[b][a] = c

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


ans = 10**18
for p in itertools.permutations(t):
    now = 0
    for i in range(r-1):
        now += d[p[i]-1][p[i + 1]-1]
    ans = min(ans, now)
print(ans)

Solution (Python):
def warshall_floyd(d):
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d


n, m, r = map(int,input().split()) 
R = list(map(int,input().split()))

d = [[float("inf") for i in range(n)] for i in range(n)] 

for i in range(m):
    x, y, z = map(int,input().split())
    d[x-1][y-1] = z
    d[y-1][x-1] = z
for i in range(n):
    d[i][i] = 0 
wa = warshall_floyd(d)


from itertools import permutations
ptn = permutations(R)

ans = 10**19
for p in ptn:
  cost = 0
  roots = [(j-1, i-1) for i, j in zip(p, p[1:])]
  for i, j in roots:
    cost += wa[i][j]
  ans = min(ans, cost)
  
print(ans)

Solution (Python):
from itertools import permutations
import sys
input = sys.stdin.readline

def main():
    N, M, RR = map(int, input().split())
    R = list(map(int, input().split()))
    INF = float("inf")
    T = [[INF] * N for _ in range(N)]
    for _ in range(M):
        a, b, c = tuple(map(int, input().split()))
        T[a-1][b-1] = c
        T[b-1][a-1] = c
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if T[i][j] > T[i][k]+T[k][j]:
                    T[i][j] = T[i][k]+T[k][j]
    print(min(sum(T[rs[i]-1][rs[i+1]-1] for i in range(RR-1)) for rs in permutations(R)))

if __name__ == "__main__":
    main()

Solution (Python):
from itertools import permutations
import sys
input = sys.stdin.readline

def main():
    N, M, RR = map(int, input().split())
    R = list(map(int, input().split()))
    INF = float("inf")
    T = [[INF] * N for _ in range(N)]
    for _ in range(M):
        a, b, c = tuple(map(int, input().split()))
        T[a-1][b-1] = c
        T[b-1][a-1] = c
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if T[i][j] > T[i][k]+T[k][j]:
                    T[i][j] = T[i][k]+T[k][j]
    ans = INF
    for rs in permutations(R):
        cost = 0
        for i in range(RR-1):
            cost += T[rs[i]-1][rs[i+1]-1]
        ans = min(ans, cost)
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
def main():
    import itertools
    n,m,r=map(int,input().split())
    rx=[int(i) for i in input().split()]
    inf=100000000
    wf=[[inf]*n for i in range(n)]
    for i in range(n):
        wf[i][i]=0

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

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if wf[i][j]>wf[i][k]+wf[k][j]:
                    wf[i][j]=wf[i][k]+wf[k][j]
    cnt=0
    l=list(itertools.permutations([i for i in range(r)]))
    cnt=inf
    for i in l:
        cnt_sub=0
        for j in range(r-1):
            cnt_sub+=wf[rx[i[j]]-1][rx[i[j+1]]-1]
        cnt=min(cnt,cnt_sub)
    print(cnt)
main()

Solution (Python):
import itertools
def main():
    n,m,r=map(int,input().split())
    rx=[int(i) for i in input().split()]
    inf=100000000
    wf=[[inf]*n for i in range(n)]
    for i in range(n):
        wf[i][i]=0

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

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if wf[i][j]>wf[i][k]+wf[k][j]:
                    wf[i][j]=wf[i][k]+wf[k][j]
    cnt=0
    l=list(itertools.permutations([i for i in range(r)]))
    cnt=inf
    for i in l:
        cnt_sub=0
        for j in range(r-1):
            cnt_sub+=wf[rx[i[j]]-1][rx[i[j+1]]-1]
        cnt=min(cnt,cnt_sub)
    print(cnt)
main()

Solution (Python):
import itertools
n,m,r=map(int,input().split())
rx=[int(i) for i in input().split()]
inf=100000000
wf=[[inf]*n for i in range(n)]
for i in range(n):
    wf[i][i]=0

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

for k in range(n):
    for i in range(n):
        for j in range(n):
            if wf[i][j]>wf[i][k]+wf[k][j]:
                wf[i][j]=wf[i][k]+wf[k][j]
cnt=0
l=list(itertools.permutations([i for i in range(r)]))
cnt=inf
for i in l:
    cnt_sub=0
    for j in range(r-1):
        cnt_sub+=wf[rx[i[j]]-1][rx[i[j+1]]-1]
    cnt=min(cnt,cnt_sub)
print(cnt)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m,r = inpl()
x = inpl()
g = [[INF] *n for i in range(n)]
for i in range(m):
    a,b,c = inpl()
    g[a-1][b-1] = c
    g[b-1][a-1] = c
for i in range(n):
    g[i][i] = 0
for k in range(n):
    for i in range(n):
        for j in range(n):
            g[i][j] = min(g[i][k]+g[k][j], g[i][j])

res = INF
for flag in itertools.permutations(range(r)):
    cnt = 0
    for i in range(r-1):
        cnt += g[x[flag[i]]-1][x[flag[i+1]]-1]
    res = min(res, cnt)
print(res)

Solution (Python):
from itertools import permutations
from scipy.sparse.csgraph import floyd_warshall
import numpy as np
N, M, R = map(int, input().split())
r = tuple(map(int, input().split()))

inf = 10**9
graph = np.ones((N, N), dtype=int)*inf
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    graph[a][b] = c
    graph[b][a] = c
fy = floyd_warshall(graph)

ans = 10 ** 9
for p in permutations(r):
    tmp = 0
    for x, y in zip(p[:-1], p[1:]):
        x -= 1
        y -= 1
        tmp += int(fy[x][y])
    ans = min(ans, tmp)
print(ans)

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

Solution (Python):
def warshall_floyd(d):
    
    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])
    return d
  
  
n,m,r = map(int,input().split()) 
lists=list(map(int,input().split()))
d = [[float("inf") for i in range(n+1)] for i in range(n+1)] 

for i in range(m):
    x,y,z = map(int,input().split())
    d[x][y] = z
    d[y][x] = z
for i in range(n+1):
    d[i][i] = 0 
dislist=warshall_floyd(d)

import itertools

U=list(itertools.permutations(lists))

mini=10**100
for some in U:
  dd=0
  for j in range(r-1):
    if dislist[some[j]][some[j+1]]!=float("inf"):
      dd+=dislist[some[j]][some[j+1]]
    else:
      break
  mini=min(mini,dd)
print(mini)

Solution (Python):
n,m,R=map(int,input().split())
r=list(map(int,input().split()))
g=[[float("inf")]*n for _ in range(n)]
def warshall_floyd(d):
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

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

from itertools import permutations
P=permutations(r)
P=list(P)

ans=float("inf")
for p in P:
    
    l=0
    for i in range(1,R):
        s=p[i-1]-1
        f=p[i]-1
        l+=g[s][f]
    
    ans=min(ans,l)
print(ans)

Solution (Python):
from itertools import permutations, combinations
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
N,M,R = map(int,input().split())
r = list(map(int,input().split()))
r = [r[i]-1 for i in range(R)]
vve = [list(map(int,input().split())) for i in range(M)]
v1,v2,edge = zip(*vve)
v1 = list(v1)
v2 = list(v2)
for i in range(M):
  v1[i] -= 1
  v2[i] -= 1
csr = csr_matrix((edge,(v1,v2)),shape = (N,N))
dist = [[0 for j in range(R)] for i in range(R)]
for i,j in combinations(range(R),2):
  r1,r2=r[i],r[j]
  dist[i][j] = int(dijkstra(csr, directed = False,indices = r1)[r2])
  dist[j][i] = dist[i][j]
ans = 10**18
for x in permutations(range(R)):
  distsum = 0
  for i in range(1,R):
    distsum += dist[x[i]][x[i-1]]
  ans = min(ans,distsum)
print(ans)

Solution (Python):
import sys
from itertools import permutations
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,M,R=map(int,input().split())
    r=list(map(lambda x:int(x)-1,input().split()))
    d=[[INF]*N for _ in range(N)]
    for i in range(M):
        A,B,C=map(int,input().split())
        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):
                d[i][j]=min(d[i][j],d[i][k]+d[k][j])
    ans=INF
    for p in permutations(r):
        tmp=0
        for i in range(R-1):
            tmp+=d[p[i]][p[i+1]]
        ans=min(ans,tmp)
    print(ans)
            

if __name__ == '__main__':
    main()

Solution (Python):

import itertools

def warshall_floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k]+d[k][j])
    return d

n, m, R = map(int, input().split())
r = list(map(lambda x: int(x)-1,input().split()))
dist = [[float("inf")] * n for _ in range(n)]
for i in range(n):
    dist[i][i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    a, b = a-1, b-1
    dist[a][b] = c
    dist[b][a] = c
dist = warshall_floyd(dist)

l = list(itertools.permutations(r))
ans = float("inf")
for i in range(len(l)):
    tmp = 0
    for j in range(len(r)-1):
        tmp += dist[l[i][j]][l[i][j+1]]
    ans = min(ans, tmp)
print(ans)