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):
import itertools
N, M, r = map(int, input().split())
R = [int(a)-1 for a in input().split()]

X = [[0 if i == j else 1<<100 for j in range(N)] for i in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    X[a-1][b-1] = c
    X[b-1][a-1] = c

for k in range(N):
    for i in range(N):
        for j in range(N):
            X[i][j] = min(X[i][j], X[i][k] + X[k][j])
mi = 1<<100
for A in itertools.permutations(R, r):
    mi = min(mi, sum([X[A[i-1]][A[i]] for i in range(1, r)]))

print(mi)

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

N,M,R = map(int,input().split())
r = [int(x) for x in input().split()]

edge = np.zeros((N+1,N+1))
for _ in range(M):
    A,B,C = map(int,input().split())
    edge[A,B] = C

dist = shortest_path(edge,directed = False).astype(int)

answer = 10**18
for visit in itertools.permutations(r):
    p = 0
    prev = visit[0]
    for x in visit[1:]:
        if prev != None:
            p += dist[prev,x]
        prev = x
    answer = min(answer,p)

print(answer)

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

N,M,R=map(int,input().split())
r=[int(x)-1 for x in input().split()]
dist=[[0 for _ in range(N)] for _ in range(N)]
for i in range(M):
    x,y,z=map(int,input().split())
    dist[x-1][y-1]=z
    dist[y-1][x-1]=z
tr=floyd_warshall(dist)
ans=10**12
for tmp in permutations(r):
    cnt=0
    for i in range(R-1):
        cnt+=tr[tmp[i]][tmp[i+1]]
    ans=min(ans,cnt)

print(int(ans))

Solution (Python):
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    def dfs(i=-1,s=0,cnt=1):
        if cnt==rn:return s
        if i==-1:
            return min(dfs(j) for j in range(rn))
        vis[i]=True
        ri=rr[i]
        res=inf
        for j in range(rn):
            if vis[j]:continue
            rj=rr[j]
            res=min(res,dfs(j,s+dist[ri][rj],cnt+1))
        vis[i]=False
        return res


    inf=10**9
    n, m, rn = MI()
    rr = LI()
    to = defaultdict(list)
    dist=[[inf]*n for _ in range(n)]
    for _ in range(m):
        a, b, c = MI()
        a, b = a - 1, b - 1
        to[a].append((b, c))
        to[b].append((a, c))
        dist[a][b]=dist[b][a]=c
    for w in range(n):
        distw=dist[w]
        for u in range(n):
            for v in range(n):
                duv=distw[u]+distw[v]
                if duv<dist[u][v]:dist[u][v]=dist[v][u]=duv
    vis=[False]*rn
    print(dfs())

main()

Solution (Python):
import itertools

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

D = [[float('inf') for _ in range(N)] for _ in range(N)]
for _ in range(M):
  a,b,c = map(int,input().split())
  a -= 1
  b -= 1
  D[a][b] = c
  D[b][a] = c
for i in range(N):
  D[i][i] = 0

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 = float('inf')
for p in list(itertools.permutations(r)):
  d = 0
  for i in range(R-1):
    d += D[p[i]-1][p[i+1]-1]
  ans = min(d,ans)
print(ans)

Solution (Python):
from itertools import permutations

def main():
    N, M, R = map(int, input().split())
    r = list(map(int, input().split()))
    d = [[float('inf')] * N for _ in range(N)]
    for _ 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 = float('inf')
    for D in list(permutations(r)):
        tmp = 0
        for i in range(len(D)-1):
            tmp += d[D[i]-1][D[i+1]-1]
        ans = min(ans, tmp)

    print(ans)



           



if __name__ == "__main__":
    main()

Solution (Python):


from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string



def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]

def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7


input=sys.stdin.readline
show_flg=False


n,m,R=MI()
r=LI_()
g,_=GI(n,m)

show(g)
inf=float('inf')
def wf(e):
    n=len(e)
    d=[[inf]*n for _ in range(n)]
    for a in range(n):
        for b,c in g[a]:
            d[a][b]=c
            d[b][a]=c
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j]>d[i][k]+d[j][k]:
                    d[i][j]=d[i][k]+d[j][k]
    
    return d

ans=inf
md=wf(g)
dists=[]
def search(st,d,ls):
    if len(ls)==1:
        dists.append(d+md[st][ls[0]])
        return
    for gl in ls:
        search(gl,d+md[st][gl],[i for i in ls if i!=gl])
    return

for i in r:search(i,0,[j for j in r if i!=j])
print(min(dists))

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect_left
from heapq import heappush, heappop
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M, R = MAP()
r = LIST()
ABC = [LIST() for _ in range(M)]

dist = [[INF]*N for _ in range(N)]

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

for A, B, C in ABC:
    dist[A-1][B-1] = C
    dist[B-1][A-1] = C

graph = csr_matrix(dist)
dist_mat = floyd_warshall(graph, directed=False)

ans = INF
for n in permutations(r):
    tmp = 0  
    for i in range(1, len(r)):
        tmp += dist_mat[n[i-1]-1][n[i]-1]
    ans = min(ans, tmp)
print(int(ans))

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

n,m,R=map(int,input().split())
r=list(map(int,input().split()))
s=[[0]*n for i in range(n)]
for i in range(m):
    a, b, c = list(map(int, input().split()))
    a, b = a-1, b-1
    s[a][b] = c
    s[b][a] = c
s=floyd_warshall(s)   

ans=float('inf')
for i in permutations(r):
    an=0
    for j in range(R-1):
        an+=s[i[j]-1][i[j+1]-1]
    ans=min(ans,an)
print(int(ans))

Solution (Python):
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
abc = [list(map(int, input().split())) for _ in range(M)]

cost = [[float('inf')] * N for _ in range(N)]
for i in range(M):
    a, b, c = abc[i][0], abc[i][1], abc[i][2]
    cost[a-1][b-1] = c
    cost[b-1][a-1] = c

from scipy.sparse.csgraph import floyd_warshall
dist = floyd_warshall(cost)

mindist = float('inf')
import itertools
for it in itertools.permutations(r):
    it = list(it)
    d = 0
    for i in range(R - 1):
        d += int(dist[it[i]-1][it[i+1]-1])
    
    mindist = min(mindist, d)
print(mindist)

Solution (Python):

import sys
import itertools
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n, m, _ = map(int, input().split())
d = [[float("inf") for i in range(n)] for i in range(n)]
for i in range(n):
    d[i][i] = 0  
r = list(map(int, input().split()))


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 _ in range(m):
    a, b, c = map(int, input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
warshall_floyd(d)

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

Solution (Python):
import itertools

N,M,R = map(int,input().split())
r = list(map(int,input().split()))
L = []
ans = float('inf')
for i in range(M):
    L.append(list(map(int,input().split())))
cost = []
for i in range(N):
    T = [float('inf') for j in range(N)]
    cost.append(T)
for i in range(M):
    cost[L[i][0]-1][L[i][1]-1] = L[i][2]
    cost[L[i][1]-1][L[i][0]-1] = L[i][2]
for l in range(N):
    for k in range(N):
        for m in range(N):
            cost[k][m] = min(cost[k][l]+cost[l][m], cost[k][m])

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

Solution (Python):
from itertools import permutations
from scipy.sparse.csgraph import dijkstra, csgraph_from_dense
N, M, R = map(int, input().split())
t = set(map(int, input().split()))
ABC = [map(int, input().split()) for i in range(M)]

root = [[10**9]*N for i in range(N)]
for a, b, c in ABC:
    root[a-1][b-1] = c
    root[b-1][a-1] = c
g = csgraph_from_dense(root, null_value=10**9)
G = dijkstra(g)
ans = 10**9
for l in permutations(t):
    tmp = 0
    for i in range(1, R):
        tmp += min(root[l[i-1]-1][l[i]-1], G[l[i-1]-1][l[i]-1])
    ans = min(tmp, ans)
print(int(ans))

Solution (Python):
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy


from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): 
    return int(input())
def inpm(): 
    return map(int,input().split())
def inpl(): 
    return list(map(int, input().split()))
def inpls(): 
    return list(input().split())
def inplm(n): 
    return list(int(input()) for _ in range(n))
def inpll(n): 
    return sorted([list(map(int, input().split())) for _ in range(n)])
def sortx(x,n,k):
    if k == 0:x.sort(key=lambda y:y[1,n])
    else:x.sort(reversed=True, key=lambda y:y[1,n])

def graphm():
    n,m=inpm()
    g=[[] for _ in range(n)]
    for _ in range(m):
        a,b,w=inpm()
        a-=1
        b-=1
        g[a].append((w,b))
        g[b].append((w,a))
    return n,m,g

def warshall_floyd(): 
    n,m,r = map(int,input().split()) 
    R=inpl()
    d=[[10**10 for _ in range(n)] for _ in range(n)]
    for i in range(m):
        x,y,z = inpm()
        x -= 1
        y -= 1
        d[x][y] = z
        d[y][x] = z
    for i in range(n):
        d[i][i] = 0 
    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 = float('inf')
    for com in permutations(R,r):
        ans_pre = 0
        for i in range(r-1):
            ans_pre += d[com[i]-1][com[i+1]-1]
        ans = min(ans,ans_pre)
    print(ans)

def main(): 
    warshall_floyd()

if __name__ == "__main__":
    main()

Solution (Python):
import sys
from itertools import permutations as per
input = sys.stdin.readline
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
d = [[float("inf")] * (N + 1) for _ in range(N + 1)]
for i in range(N + 1):
  d[i][i] = 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):
      d[i][j] = min(d[i][k] + d[k][j], d[i][j])
res = float("inf")
for p in per(r, R):
  t = 0
  for i in range(R - 1):
    t += d[p[i]][p[i + 1]]
  res = min(t, res)
print(res)

Solution (Python):
from itertools import permutations
def wf(d):
  n=len(d[0])
  for k in range(n):
    for i in range(n):
      for j in range(n):
        if d[i][j]>d[i][k]+d[k][j]:
          d[i][j]=d[i][k]+d[k][j]
  return d
n,m,r=map(int,input().split());R=min(r,8)
d = [[10**12for i in range(n)]for j in range(n)]
l=[int(i)-1 for i in input().split()]
for i in range(m):
  a,b,c=map(int,input().split())
  d[a-1][b-1]=d[b-1][a-1] = c
d=wf(d)

ans=30**8
for v in permutations(l):
  cnt=sum(d[v][u] for v, u in zip(v, v[1:]))
  ans=min(ans,cnt)
print(ans)

Solution (Python):
import itertools
n,m,r=map(int,input().split());R=min(r,8)
d = [[10**12for i in range(n)]for j in range(n)]
l=list(map(int,input().split()))
for i in range(r):
  l[i]-=1
for i in range(m):
  a,b,c=map(int,input().split())
  d[a-1][b-1]=d[b-1][a-1] = 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**12
for v in itertools.permutations(l, R):
  cnt=0
  for i in range(1,R):
    cnt+=d[v[i-1]][v[i]]
  ans=min(ans,cnt)
print(ans)

Solution (Python):







N, M, R = map(int, input().split(' '))
r = [int(c) - 1 for c in input().split(' ')]

INF = float("inf")
table = [[INF for _ in range(N)] for _ in range(N)]
for i in range(N):
    table[i][i] = 0

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


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


import itertools
ans = INF
len_r = len(r)
for indices in itertools.permutations(r):
    indices = list(indices)
    ans = min(ans, sum([table[indices[i]][indices[i+1]] for i in range(len_r-1)]))

print(ans)

Solution (Python):
from heapq import heappush,heappop
import itertools
n,m,r=map(int,input().split())
l1=list(map(int,input().split()))
inf=10**10
l=[[] for i in range(n+1)]
for i in range(m):
  a,b,c=map(int,input().split())
  l[a].append([b,c])
  l[b].append([a,c])
def dijkstra(s):
  q=[(0,s)]
  dist=[inf]*(n+1)
  dist[s]=0
  while q:
    c,v=heappop(q)
    if dist[v]<c:
      continue
    for i in l[v]:
      t=i[0]
      cost=i[1]
      if dist[v]+cost<dist[t]:
        dist[t]=dist[v]+cost
        heappush(q,[dist[t],t])
  return dist
dic={}
for i in range(r):
  d=dijkstra(l1[i])
  dic[l1[i]]=d
p=itertools.permutations(l1,r)
ans=inf
for i in p:
  p1=i
  ans1=0
  for j in range(r-1):
    num1=p1[j]
    num2=p1[j+1]
    ans1+=dic[num1][num2]
  if ans>ans1:
    ans=ans1
print(ans)

Solution (Python):

import itertools
N,M,R = map(int,input().split())
rlist = list(map(int,input().split()))


def warshall_floyd(dist):
    
    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])
    return dist

inf = float("inf")
dist = [[inf for i in range(N)] for j in range(N)]
for i in range(N):
    dist[i][i] = 0

for i in range(M):
    a,b,c = map(int,input().split())
    dist[a-1][b-1] = c
    dist[b-1][a-1] = c
    
dist = warshall_floyd(dist)
per = [i for i in range(R)]
ind = list(itertools.permutations(per,R))

MIN = inf
for index in ind:
    now = 0
    for i in range(R-1):
        f = index[i]
        b = index[i+1]
        now+=dist[rlist[f]-1][rlist[b]-1]
    MIN = min(MIN,now)
    
print(MIN)

Solution (Python):
N, M, R = map(int, input().split())
towns = list(map(int, input().split()))
allEdges = [[float('inf') for i in range(N)] for i in range(N)]
for i in range(M):
    A, B, C = map(int, input().split())
    allEdges[A-1][B-1] = C
    allEdges[B-1][A-1] = C

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

graph = [[float('inf') for i in range(R)] for j in range(R)]

for i in range(R):
    for j in range(R):
        graph[i][j] = allEdges[towns[i] - 1][towns[j] - 1]

dp = [[-1 for i in range(R)] for j in range(1 << R)]

def recurse(seen, cur):
    if seen == (1 << R) - 1:
        return 0
    if dp[seen][cur] != -1:
        return dp[seen][cur]
    
    cost = float('inf')
    for i in range(R):
        if seen & (1 << i) == 0:
            cost = min(cost, recurse(seen | (1 << i), i) + graph[cur][i])
    dp[seen][cur] = cost
    return dp[seen][cur]

cost = float('inf')
for i in range(R):
    cost = min(cost, recurse(1 << i, i))

print(cost)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m,r=map(int,input().split())
    R=list(map(lambda x:int(x)-1,input().split()))
    A=[[INF]*n for _ in range(n)]
    for _ in range(m):
        a,b,c=map(int,input().split())
        a-=1; b-=1
        A[a][b]=A[b][a]=c

    from itertools import product
    for k,i,j in product(range(n),repeat=3):
        A[i][j]=min(A[i][j],A[i][k]+A[k][j])

    
    N=2**r
    dp=[[INF]*r for _ in range(N)]

    
    for x in range(r):
        dp[1<<x][x]=0

    
    for V in range(N):
        for x in range(r):
            if(not (V>>x)&1): continue
            for y in range(r):
                if((V>>y)&1): continue 
                dp[V+(1<<y)][y]=min(dp[V+(1<<y)][y],dp[V][x]+A[R[x]][R[y]])

    
    print(min(dp[N-1][x] for x in range(r)))
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m,r=map(int,input().split())
    R=list(map(lambda x:int(x)-1,input().split()))
    A=[[INF]*n for _ in range(n)]
    for _ in range(m):
        a,b,c=map(int,input().split())
        a-=1; b-=1
        A[a][b]=A[b][a]=c

    from itertools import product
    for k,i,j in product(range(n),repeat=3):
        A[i][j]=min(A[i][j],A[i][k]+A[k][j])

    from itertools import permutations
    ans=INF
    for p in permutations(R):
        score=0
        for i in range(r-1):
            score+=A[p[i+1]][p[i]]
        ans=min(ans,score)
    print(ans)
resolve()

Solution (Python):
def warshall_floyd(cost, num_v):
    """
    ワーシャルフロイド法
    :param cost: 隣接行列
    :param num_v: 頂点数
    :return: 各頂点からの最短距離
    """
    for k in range(num_v):
        for i in range(num_v):
            for j in range(num_v):
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
    return cost


import itertools


def abc073_d():
    n, m, r = map(int, input().split())
    *r, = map(int, input().split())
    inf = float("inf")
    cost = [[inf] * n for _ in range(n)]
    for _ in range(m):
        a, b, c = map(int, input().split())
        cost[a - 1][b - 1] = c
        cost[b - 1][a - 1] = c
    for i in range(n):
        cost[i][i] = 0

    cost = warshall_floyd(cost, n)
    ans = inf
    for permutation in itertools.permutations(r):
        c = 0
        b = permutation[0]
        for i in permutation[1:]:
            c += cost[b - 1][i - 1]
            b = i
        ans = min(ans, c)
    print(ans)


if __name__ == '__main__':
    abc073_d()

Solution (Python):
import itertools

N,M,R = map(int, input().split())
rlist = [int(r) for r in input().split()]
INF = 10**9
E = [[INF]*N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    E[a-1][b-1] = c
    E[b-1][a-1] = c
    
for k in range(N):
    for i in range(N):
        for j in range(N):
            E[i][j] = min(E[i][j], E[i][k]+E[k][j])
            
ans = 10**9

for i in range(R):
    rlist[i] -= 1
    
for p in itertools.permutations(rlist):
    d = 0
    for i in range(1, R):
        d += E[p[i-1]][p[i]]
    ans = min(ans, d)
    
print(ans)

Solution (Python):
import sys
from itertools import permutations
input = sys.stdin.buffer.readline
inf = float('inf')

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
adj = [[inf for _ in range(N+1)] for _ in range(N+1)]
for _ in range(M):
    a, b, c = map(int, input().split())
    adj[a][b] = c
    adj[b][a] = c

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

ans = inf
for r_list in permutations(r):
    ans_new = 0
    for i in range(R-1):
        ans_new += adj[r_list[i]][r_list[i+1]]
    ans = min(ans, ans_new)

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
import heapq
N,M,R=map(int,input().split())
r=list(map(int,input().split()))
abc=[[] for _ in range(N)]
for _ in range(M):
  a,b,c=map(int,input().split())
  abc[a-1].append([b,c])
  abc[b-1].append([a,c])

l=[]
for s in r:
  nseen=[i for i in r]
  dist=[float("inf")]*N
  dist[s-1]=0
  q=[[dist[i],i] for i in range(N)]
  heapq.heapify(q)
  while q:
    d,ind=heapq.heappop(q)
    if d<=dist[ind]:
      for n,c in abc[ind]:
        if dist[n-1]>d+c:
          dist[n-1]=d+c
          heapq.heappush(q,[dist[n-1],n-1])
  l.append(dist)

ans=float("inf")
seen=[]
dis=0
def dfs(pos):
  global dis
  global ans
  seen.append(pos)
  if len(seen)==R:
    ans=min(ans,dis)
  else:
    for i in r:
      if i not in seen:
        dis+=l[r.index(pos)][i-1]
        dfs(i)
        dis-=l[r.index(pos)][i-1]
  seen.remove(pos)

for i in r:
  dfs(i)
  
print(ans)

Solution (Python):
import itertools

n,m,R=map(int,input().split())
r=list(map(int,input().split()))
INF = 10**10
d=[[INF for i in range(n)] for i in range(n)]

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

for i in range(R):
    r[i] -= 1

res = INF
for rp in itertools.permutations(r):
    tres = 0
    for i in range(R-1):
        tres += d[rp[i]][rp[i+1]]
    res = min(res,tres)

print(res)

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

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

edge=np.zeros((n+1,n+1))
for i in range(m):
    a,b,c=map(int,input().split())
    edge[a,b]=c

dist=shortest_path(edge,directed=False).astype(int)

ans=10**18
for v in itertools.permutations(r):
    ans2=0
    p=v[0]
    for x in v[1:]:
        if p!=None:
            ans2+=dist[p,x]
        p=x
    ans=min(ans,ans2)

print(ans)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m,R = LI()
    r = LI()
    for i in range(R):
        r[i] -= 1
    v = [[float("inf")]*n for i in range(n)]
    for i in range(m):
        a,b,c = LI()
        a -= 1
        b -= 1
        v[a][b] = c
        v[b][a] = c
    l = 1<<R
    for k in range(n):
        for i in range(n):
            for j in range(n):
                nv = v[i][k]+v[j][k]
                if nv < v[i][j]:
                    v[i][j] = nv
    dp = [[float("inf")]*R for i in range(l)]
    for i in range(R):
        dp[1<<i][i] = 0
    for b in range(l):
        for i in range(R):
            if not (1<<i)&b:
                continue
            x = r[i]
            for j in range(R):
                bj = 1<<j
                if bj&b:
                    continue
                y = r[j]
                nd = dp[b][i]+v[x][y]
                nb = b|bj
                if nd < dp[nb][j]:
                    dp[nb][j] = nd
    print(min(dp[-1]))
    return


if __name__ == "__main__":
    solve()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    n, m, R = LI()
    r = LI_()
    edg = [[inf] * n for i in range(n)]
    for _ in range(m):
        a, b, c = LI_()
        c += 1
        edg[a][b] = c
        edg[b][a] = c
    for i in range(n):
        edg[i][i] = 0
    for k in range(n):
        for i in range(n):
            for j in range(n):
                edg[i][j] = min(edg[i][j], edg[i][k] + edg[k][j])
    fulls = itertools.permutations(range(R), R)
    ans = inf
    for full in fulls:
        b = -1
        tmp = 0
        for f in full:
            if b == -1:
                b = r[f]
                continue
            tmp += edg[r[f]][b]
            b = r[f]
        ans = min(ans, tmp)
    print(ans)

    return


def B():
    return


def C():
    return


def D():
    return


def E():
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == '__main__':
    A()

Solution (Python):
import sys, copy
from itertools import permutations

def wf(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())
Rs = list(map(int,input().split()))

d = [[float('inf') for i in range(N)] for i in range(N)]
for _ in range(M):
  a,b,c = map(int,sys.stdin.readline().split())
  d[a-1][b-1] = c
  d[b-1][a-1] = c

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

wf(d)

ans = float('inf')
for prm in permutations(Rs, R):
  ans = min(ans, sum([d[prm[i-1]-1][prm[i]-1] for i in range(1,R)]))
print(ans)

Solution (Python):
import itertools
n,m,r=map(int,input().split())
rr=list(map(int,input().split()))
inf=10000000000
g=[[inf for i in range(n)] for j in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    g[a-1][b-1]=c
    g[b-1][a-1]=c
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=10**10
for i in itertools.permutations(range(0,r),r):
    kai=0
    for j in range(r-1):
        kai+=g[rr[i[j]]-1][rr[i[j+1]]-1]
    ans=min(ans,kai)
print(ans)

Solution (Python):
import sys
import itertools


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    wn, wm, r = list(map(int, input().rstrip('\n').split()))
    rl = list(map(int, input().rstrip('\n').split()))
    inf = 10 ** 13
    wl = [[inf] * wn for _ in range(wn)]
    for i in range(wn):
        wl[i][i] = 0

    for i in range(wm):
        wa, wb, wc = list(map(int, input().rstrip('\n').split()))
        wl[wa - 1][wb - 1] = wc
        wl[wb - 1][wa - 1] = wc

    for i in range(wn):
        for j in range(wn):
            for k in range(wn):
                wl[j][k] = min(wl[j][k], wl[j][i] + wl[i][k])
    mt = 10 ** 10
    for v in itertools.permutations(rl):
        t = 0
        for i in range(1, r):
            t += wl[v[i]-1][v[i-1]-1]
        mt = min(mt, t)
    print(mt)


if __name__ == '__main__':
    solve()

Solution (Python):
from itertools import permutations

def warshall_floyd(d):
    
    n=len(d[0])
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
    return d

N,M,R=[int(x) for x in input().split()]
r=[int(x)-1 for x in input().split()]


route_list=[[10**8]*N for _ in range(N)]

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

wa_list=warshall_floyd(route_list)
ans=30**9

for perm in permutations(r):
    
    cur = sum(wa_list[v][u] for v, u in zip(perm, perm[1:]))
    ans = min(ans, cur)

print(ans)

Solution (Python):
from itertools import permutations

def warshall_floyd(d):
    
    n=len(d[0])
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
    return d

N,M,R=[int(x) for x in input().split()]
r=[int(x)-1 for x in input().split()]

INF = float("inf")
route_list=[[INF]*N for _ in range(N)]

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

wa_list=warshall_floyd(route_list)
ans=30**9

for perm in permutations(r):
    
    cur = sum(wa_list[v][u] for v, u in zip(perm, perm[1:]))
    ans = min(ans, cur)

print(ans)