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

def warshall_floid(graph: list) -> list:
    """warshall-floid法: 各頂点から各頂点への最短距離を求める
    計算量: O(V^3)
    """
    n = len(graph)
    INF = 10 ** 18
    dp = [[INF] * n for i in range(n)]
    for i in range(n):
        dp[i][i] = 0
    for i in range(n):
        for j, cost in graph[i]:
            dp[i][j] = cost

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

n, m, r = map(int, input().split())
r = list(map(int, input().split()))
info = [list(map(int, input().split())) for i in range(m)]

graph = [[] for i in range(n)]
for i in range(m):
    a, b, cost = info[i]
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))
dp = warshall_floid(graph)

ans = 10 ** 18
for ptn in itertools.permutations(r):
    tmp = 0
    for i in range(1, len(ptn)):
        tmp += dp[ptn[i] - 1][ptn[i - 1] - 1]
    ans = min(ans, tmp)
print(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()))
l=[[float('inf')]*n for _ in range(n)]
for _ in range(m):
    a,b,c,=map(int,input().split())
    a-=1
    b-=1
    l[a][b]=c
    l[b][a]=c
for i in range(n):
    l[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

F1 = floyd_warshall(l)
ans=float('inf')
for v in permutations(R):
    temp=0
    for i in range(r-1):
        temp+=F1[v[i]-1][v[i+1]-1]
    ans=min(ans,temp)
print(int(ans))

Solution (Python):
from itertools import permutations as p
 
from scipy.sparse.csgraph import floyd_warshall
 
n, m, r = map(int, input().split())
R = list(map(int, input().split()))
l = [[0]*n for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    l[a][b] = c
    l[b][a] = c
F = floyd_warshall(l)
 
ans = float("inf")
for v in p(R):
    temp = 0
    for i in range(r-1):
        temp += F[v[i]-1][v[i+1]-1]
    ans = min(ans, temp)
print(int(ans))

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def warshallFloyd():
    for k in range(N):
        for i in range(N-1):
            for j in range(i, N):
                tmp = min(E[i][j], E[i][k] + E[k][j])
                E[i][j] = E[j][i] = tmp

def dfs(c, p, d):
    if c == R:
        ans[0] = min(ans[0], d)
        return
    for i in range(R):
        if used[i]:
            continue
        used[i] = True
        if p == -1:
            dfs(c+1, i, 0)
        else:
            dfs(c+1, i, d + E[S[p]-1][S[i]-1])
        used[i] = False

N, M, R = map(int, input().split())
S = list(map(int, input().split()))
E = [[float('inf')] * N for _ in range(N)]
for i in range(N):
    E[i][i] = 0
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    E[a][b] = E[b][a] = c
warshallFloyd()
ans = [float('inf')]
used = [False] * R
dfs(0, -1, 0)
print(*ans)

Solution (Python):
from itertools import permutations

class Graph():  
    def __init__(self, n, edge):
        self.n = n
        self.graph = [[] for _ in range(n)]
        for e in edge:
            self.graph[e[0] - 1].append((e[1] - 1, e[2]))
            self.graph[e[1] - 1].append((e[0] - 1, e[2]))

    def warshall_floyd(self, INF=10**18):
        dist = [[INF for j in range(self.n)] for i in range(self.n)]
        for i in range(self.n):
            dist[i][i] = 0
        for i in range(self.n):
            for j, cost in self.graph[i]:
                dist[i][j] = cost
        for k in range(self.n):
            for i in range(self.n):
                for j in range(self.n):
                    if dist[i][k] != INF and dist[k][j] != INF:
                        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
        return dist

N, M, R = map(int, input().split())
T = list(map(int, input().split()))
E = [tuple(map(int, input().split())) for _ in range(M)]

G = Graph(N, E)
D = G.warshall_floyd()

ans = 10**18

for p in permutations(range(R)):
    dist = 0
    for i in range(R - 1):
        t1, t2 = T[p[i]], T[p[i + 1]]
        dist += D[t1 - 1][t2 - 1]
    ans = min(ans, dist)

print(ans)

Solution (Python):


import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))




from itertools import product, permutations, combinations

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra






N, M, r = read_ints()
R = [x - 1 for x in read_ints()]
adj_mat = [[0] * N for _ in range(N)]
for _ in range(M):
    a, b, c = read_ints()
    a -= 1
    b -= 1
    adj_mat[a][b] = c
    adj_mat[b][a] = c


D = dijkstra(csr_matrix(adj_mat, dtype='int'), directed=False)


ans = 2 ** 31


def get_kyori(p):
    ret = 0
    for ps, pt in zip(p[:-1], p[1:]):
        ret += D[ps, pt]
    return ret


for p in permutations(R):
    ans = min(ans, get_kyori(p))
print(int(ans))

Solution (Python):
from itertools import permutations as perm

n, m, r = map(int, input().split())
r = list(map(lambda x: int(x) - 1, input().split()))
d = [[10 ** 10] * n for _ in range(n)]
for i in range(m):
    abc = tuple(map(int, input().split()))
    a = abc[0] - 1
    b = abc[1] - 1
    c = abc[2]
    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])
            d[j][i] = d[i][j]

ans = 10 ** 10
for arr in perm(r):
    rep = 0
    for i in range(len(arr) - 1):
        rep += d[arr[i]][arr[i + 1]]
    ans = min(ans, rep)
print(ans)

Solution (Python):
from itertools import permutations as perm

n, m, r = map(int, input().split())
r = list(map(lambda x: int(x) - 1, input().split()))
d = [[10 ** 9] * n for _ in range(n)]
for i in range(m):
    abc = tuple(map(int, input().split()))
    a = abc[0] - 1
    b = abc[1] - 1
    c = abc[2]
    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])
            d[j][i] = d[i][j]

ans = 10 ** 9
for arr in perm(r):
    rep = 0
    for i in range(len(arr) - 1):
        rep += d[arr[i]][arr[i + 1]]
    ans = min(ans, rep)
print(ans)

Solution (Python):
from itertools import permutations
N, M, R, *L = map(int, open(0).read().split())
city = L[:R]
inf = L[R:]
dist = [[10**10]*N for i in range(N)]
for x,y,c in zip(*[iter(inf)]*3):
  dist[x-1][y-1] = c
  dist[y-1][x-1] = c
for i in range(N):
  dist[i][i] = 0

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

ans = 10**10
for m in permutations(city):
  n = 0
  for i in range(R-1):
    n += dist[m[i]-1][m[i+1]-1]
  ans = min(ans,n)
print(ans)

Solution (Python):
import itertools


N,M,R = map(int,input().split())
rs = list(map(lambda x:int(x)-1,input().split()))
cost=[[10**9]*N for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    cost[a-1][b-1] = c
    cost[b-1][a-1] = c

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

ans = 10**9
for roads in itertools.permutations(rs):
    co = 0
    p = roads[0]
    for r in roads[1:]:
        co += cost[p][r]
        p = r
    ans = min(ans,co)
print(ans)

Solution (Python):
from itertools import permutations
inf=10**9
n,m,R=map(int,input().split())
r=list(map(int,input().split()))
rr=permutations(r,R)
dis=[[inf]*n for _ in range(n)]
for i in range(m):
	a,b,c=map(int,input().split())
	dis[a-1][b-1]=c
	dis[b-1][a-1]=c
for i in range(n):
	for j in range(n):
		for k in range(n):
			dis[j][k]=min(dis[j][i]+dis[i][k],dis[j][k])
ans=10**12
for x in rr:
	e=0
	for i in range(R-1):
		e+=dis[x[i+1]-1][x[i]-1]
	ans=min(ans,e)
print(ans)

Solution (Python):
import copy
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()))
for i in range(r):
  R[i]=R[i]-1
d=[[10**10]*n for i in range(n)] 
for i in range(m):
  a,b,c=map(int,input().split())
  a=a-1
  b=b-1
  d[a][b]=c
  d[b][a]=c
for i in range(n):
  d[i][i]=0
D=warshall_floyd(d)
s=1
S=[]
for i in range(1,r+1):
  s=s*i
  S.append(s)
ans=10**10
for i in range(s):
  RR=copy.copy(R)
  E=[]
  for j in range(r-1):
    E.append(RR[i//S[r-j-2]])
    RR.pop(i//S[r-j-2])
    i=i-S[r-j-2]*(i//S[r-j-2])
  E.append(RR[0]) 
  di=0
  for i in range(r-1):
    di=di+D[E[i]][E[i+1]]
  if di<ans:
    ans=di
print(ans)

Solution (Python):
from itertools import permutations
n,m,r=map(int,input().split())
rlis=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
d=[[10**10]*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
dist=warshall_floyd(d)
rlisp=list(permutations(rlis,r))
ans=10**10
for i in rlisp:
  cnt=0
  for j in range(r-1):
    cnt+=dist[i[j]-1][i[j+1]-1]
  ans=min(ans,cnt)
print(ans)

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

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

r = [e - 1 for e in r]

g = [[0] * N for _ in range(N)]
for a, b, c in abc:
	a -= 1
	b -= 1
	g[a][b] = c
	g[b][a] = c

dist = floyd_warshall(csr_matrix(g))

ans = float("inf")
for pat in permutations(r, len(r)):
	sm = 0
	for e1, e2 in zip(pat, pat[1:]):
		sm += dist[e1][e2]

	ans = min(ans, sm)

ans = int(ans)
print(ans)

Solution (Python):
from subprocess import call
call(('pypy3','-c',"""N,M,R=map(int,input().split())
r=list(map(int,input().split()))
A=[list(map(int,input().split())) for i in range(M)]
d=[[float("inf")]*N for i in range(N)]

for a,b,c in A:
  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])
      
import itertools 
ans=1000000000
for i in itertools.permutations(range(R),R):
  D=0
  for j in range(R-1):
    D+=d[r[i[j]]-1][r[i[j+1]]-1]
  ans=min(D,ans)
print(ans)
"""))

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

dist = [[float('inf') for _ in range(N+1)] for _ in range(N+1)]

for i in range(N+1):
    dist[i][i] = 0
for a, b, c in ABC:
    dist[a][b] = c
    dist[b][a] = c


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

from itertools import permutations as per

ans = float('inf')
for k in per(r, R):
    score = 0
    for i in range(R-1):
        score += dist[k[i]][k[i+1]]
    ans = min(ans, score)

print(ans)

Solution (Python):
import itertools
import sys

N, M, R = map(int, input().split())
r = [int(i) for i in input().split()]
r.sort()
a = [[sys.maxsize for j in range(N)] for i in range(N)]
for i in range(M):
	A, B, C = map(int, input().split())
	a[A - 1][B - 1] = C
	a[B - 1][A - 1] = C
for i in range(N):
	a[i][i] = 0
for i in range(N):
	for j in range(N):
		if a[j][i] == sys.maxsize:
			continue
		for k in range(N):
			if a[i][k] == sys.maxsize:
				continue
			a[j][k] = min(a[i][k] + a[j][i], a[j][k])
ans = sys.maxsize
for i in itertools.permutations(r):
	b = 0
	j = 1
	while j < R:
		b += a[i[j - 1] - 1][i[j] - 1]
		j += 1
	ans = min(b, ans)
print(ans)

Solution (Python):
import sys
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, csgraph_from_dense
import itertools

input = sys.stdin.readline


def main():
    N, M, R = [int(x) for x in input().split()]
    r = [int(x) - 1 for x in input().split()]
    ABC = [[int(x) for x in input().split()] for _ in range(M)]

    EDGE = [[10 ** 9] * N for j in range(N)]

    for a, b, c in ABC:
        EDGE[a - 1][b - 1] = c
        EDGE[b - 1][a - 1] = c

    G = csgraph_from_dense(EDGE, null_value=10 ** 9)

    d = floyd_warshall(G)

    ans = float("inf")
    for a in itertools.permutations(r):
        tmp = 0
        c = a[0]
        for n in a:
            tmp += int(d[c][n])
            c = n
        ans = min(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import permutations


def floyd_warshall(dist):
    v = len(dist)
    for k in range(v):
        for i in range(v):
            for j in range(v):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])


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 _ in range(M):
    A, B, C = map(int, input().split())
    A -= 1
    B -= 1
    dist[A][B] = dist[B][A] = C
floyd_warshall(dist)
ans = float('inf')
for perm in permutations(r):
    d = 0
    for i in range(R-1):
        d += dist[perm[i]][perm[i+1]]
    ans = min(ans, d)
print(ans)

Solution (Python):
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
from itertools import permutations
n,m,r,*L=map(int,open(0).read().split())
f=floyd_warshall(csr_matrix((L[r+2::3],(L[r::3],L[r+1::3])),(n+1,n+1)),0)
print(int(min(sum(f[s,t]for s,t in zip(o,o[1:]))for o in permutations(L[:r]))))

Solution (Python):
import itertools

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

DP = [[10**10 for _ in range(n+1)] for _ in range(n+1)]
for i in range(1,n+1):
    DP[i][i] = 0

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

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

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

print(ans)

Solution (Python):
from itertools import permutations
class WarshallFloyd:
    def __init__(self,n):
        self.n = n
        self.inf = float('inf')
        self.d = [[self.inf for _ in range(n)] for _ in range(n)]
        for i in range(self.n):
            self.d[i][i] = 0
    def register(self,v1,v2,l,multiple=True):
        self.d[v1][v2] = l
        if multiple:
            self.d[v2][v1] = l
    def solve(self):
        for i in range(self.n):
            for j in range(self.n):
                for k in range(self.n):
                    self.d[j][k] = min(self.d[j][k],self.d[j][i]+self.d[i][k])
        return self.d
N,M,R = map(int,input().split())
v = list(map(int,input().split()))
Edges = [[] for i in range(N)]
W = WarshallFloyd(N)
for i in range(M):
    a,b,c = map(int,input().split())
    a,b = a-1,b-1
    W.register(a,b,c)
D = W.solve()
a = permutations(v,R)
ans = 100000000000
for e in a:
    value = 0
    for e1,e2 in zip(e[:-1],e[1:]):
        value += D[e1-1][e2-1]
    ans = min(ans,value)
print(ans)

Solution (Python):
import sys
from itertools import permutations
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

N, M, R = [int(x) for x in input().strip().split()]
r = [int(x) for x in input().strip().split()]
G = [[float('inf')] * N for _ in range(N)]
for m in range(M):
    a, b, c = [int(x) for x in input().strip().split()]
    G[a-1][b-1] = c
    G[b-1][a-1] = c

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

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 rr in permutations(r):
    ans_ = 0
    for i in range(len(rr)-1):
        ans_ += G[rr[i]-1][rr[i+1]-1]
    ans = min(ans, ans_)
print(ans)

Solution (Python):

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

import itertools

def main():
    mod=10**9+7
    N,M,R=MI()
    r=LI()
    inf=10**10
    d=[[inf]*N for _ in range(N)]
    for _ in range(M):
        a,b,c=MI()
        a-=1
        b-=1
        d[a][b]=c
        d[b][a]=c
    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
        
    d=warshall_floyd(d)
    
    ans=inf
    for ite in itertools.permutations(range(R), R):
        temp=0
        for i in range(R-1):
            a=r[ite[i]]-1
            b=r[ite[i+1]]-1
            temp+=d[a][b]
        ans=min(ans,temp)
        
    print(ans)
            
        
        
    
    
    

main()

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

N, M, R = [int(x) for x in input().split()]
r = [int(x) - 1 for x in input().split()]
d = [[float("inf")] * N for _ in range(N)]
for i in range(N):
    d[i][i] = 0
for _ in range(M):
    A, B, C = [int(x) for x in input().split()]
    d[A - 1][B - 1] = C
    d[B - 1][A - 1] = C
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
d = warshall_floyd(d)

from itertools import permutations
ans = 10 ** 10
route = list(permutations(r))
for i in route:
    cnt = 0
    for j in range(R - 1):
        cnt += d[i[j]][i[j + 1]]
    ans = min(ans, cnt)

print(ans)

Solution (Python):
import itertools
import sys

N, M, R = map(int, input().split())
r = [int(i) for i in input().split()]
a = [[sys.maxsize for i in range(N)] for i in range(N)]
for i in range(N):
	a[i][i] = 0
for i in range(M):
	A, B, C = map(int, input().split())
	a[A - 1][B - 1] = C
	a[B - 1][A - 1] = C
for i in range(N):
	for j in range(N):
		if a[j][i] == sys.maxsize:
			continue
		for k in range(N):
			if a[i][k] == sys.maxsize:
				continue
			a[j][k] = min(a[i][k] + a[j][i], a[j][k])
r.sort()
ans = sys.maxsize
for i in itertools.permutations(r):
	b = 0
	j = 1
	while j < R:
		b += a[i[j - 1] - 1][i[j] - 1]
		j += 1
	ans = min(b, ans)
print(ans)

Solution (Python):




import heapq
import sys
import itertools
 
sys.setrecursionlimit(10**7)

def bfs(cost,node):
    root[node]=min(root[node],cost)
    for next_c,next_n in way[node]:
        if root[next_n]==10**9:
            heapq.heappush(q,[cost+next_c,next_n])
    return
    
N,M,R=map(int,input().split())
r=list(map(int,input().split()))

way=[[] for i in range(N)]

for _ in range(M):
    A,B,C=map(int,input().split())
    way[A-1].append([C,B-1])
    way[B-1].append([C,A-1])

made=[]


for start in r:
    root=[10**9]*N
    q=[[0,start-1]]
    heapq.heapify(q)
    while q:
        temp=heapq.heappop(q)
        
        if root[temp[1]]==10**9:
            bfs(temp[0],temp[1])
    made.append(root)


ans=10**9
for order in itertools.permutations([i for i in range(len(r))]):
    
    temp=0
    for i in range(len(order)-1):
        fro=r[order[i]]
        aft=r[order[i+1]]
        
        
        
        temp+=abs(made[order[i]][aft-1]-made[order[i]][fro-1])
    ans=min(ans,temp)
print(ans)

Solution (Python):

n,m,r = map(int,input().split())
must = list(map(lambda x: int(x)-1,input().split()))
inf = 10**18
wf = [[inf for _ in range(n)] for _ in range(n)]
for i in range(n):
  wf[i][i] = 0
for _ in range(m):
  a,b,l = map(int,input().split())
  a -= 1
  b -= 1
  wf[a][b] = l
  wf[b][a] = l
for k in range(n):
  for i in range(n):
    for j in range(n):
      wf[i][j] = min(wf[i][j],wf[i][k]+wf[k][j])

can = []
import itertools
for perm in itertools.permutations(range(r)):
  ans = 0
  for i in range(r-1):
    ans += wf[must[perm[i]]][must[perm[i+1]]]
  can.append(ans)

print(min(can))

Solution (Python):
from itertools import permutations


def warshall_floyd(d, n):
    
    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')] * N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c

d = warshall_floyd(d, N)

ans = float('inf')
for p in permutations(r):
    total = 0
    for i in range(1, len(p)):
        total += d[p[i-1]-1][p[i]-1]
    ans = min(ans, total)
print(ans)

Solution (Python):
from itertools import permutations as p

from scipy.sparse.csgraph import floyd_warshall

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

ans = float("inf")
for v in p(R):
  temp = 0
  for i in range(r-1):
    temp += F[v[i]-1][v[i+1]-1]
  ans = min(ans, temp)
  
print(int(ans))

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

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
graph = [[INF]*N for _ in range(N)]
for i in range(M):
    A, B, C = map(int, input().split())
    graph[A-1][B-1] = C
    graph[B-1][A-1] = C
dist_matrix = floyd_warshall(graph)

ans = INF
for root in permutations(r):
    cnt = 0
    for j in range(R-1):
        cnt += dist_matrix[root[j]-1][root[j+1]-1]
    ans = min(ans, cnt)
print(int(ans))

Solution (Python):
n,m,z = map(int, input().split())
r = list(map(int, input().split()))
wf=[[10**10 for i in range(n)] for j in range(n)]
for i in range(m):
    a,b,c = list(map(int,input().split()))
    wf[a-1][b-1] = c
    wf[b-1][a-1] = c

for i in range(n):
    wf[i][i]=0

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

from itertools import *
ans=10**10
for vils in list(permutations(r)):
    cnt=0
    for i in range(z-1):
        cnt+=wf[vils[i]-1][vils[i+1]-1]
    if ans>cnt:
        ans=cnt
print(ans)

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

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

d = np.array([[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 = floyd_warshall(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(int(ans))

Solution (Python):
N,M,R=map(int, input().split())
r=map(lambda x:int(x)-1, input().split())
dp=[[10**9]*N for _ in range(N)]
for _ in range(M):
    A,B,C=map(int, input().split())
    A-=1
    B-=1
    dp[A][B]=C
    dp[B][A]=C
for z in range(N):
    for x in range(N):
        for y in range(N):
            dp[x][y]=min(dp[x][y], dp[x][z]+dp[z][y])

import itertools
ans=10**9
for rp in itertools.permutations(r):
    t=0
    for i in range(R-1):
        t+=dp[rp[i]][rp[i+1]]
    ans=min(ans,t)
print(ans)

Solution (Python):
N,M,R=map(int, input().split())
r=list(map(lambda x:int(x)-1, input().split()))
dp=[[10**9]*N for _ in range(N)]
for _ in range(M):
    A,B,C=map(int, input().split())
    A-=1
    B-=1
    dp[A][B]=C
    dp[B][A]=C
for z in range(N):
    for x in range(N):
        for y in range(N):
            dp[x][y]=min(dp[x][y], dp[x][z]+dp[z][y])

import itertools
ans=10**9
for p in itertools.permutations(range(R)):
    t=0
    rp=[r[i] for i in p]
    for i in range(R-1):
        t+=dp[rp[i]][rp[i+1]]
    ans=min(ans,t)
print(ans)

Solution (Python):
N,M,R=map(int, input().split())
r=list(map(int, input().split()))
dp=[[10**9]*N for _ in range(N)]
for _ in range(M):
    A,B,C=map(int, input().split())
    A-=1
    B-=1
    dp[A][B]=C
    dp[B][A]=C
for z in range(N):
    for x in range(N):
        for y in range(N):
            dp[x][y]=min(dp[x][y], dp[x][z]+dp[z][y])

import itertools
ans=10**9
for p in itertools.permutations(range(R)):
    t=0
    rp=[r[i] for i in p]
    for i in range(R-1):
        t+=dp[rp[i]-1][rp[i+1]-1]
    ans=min(ans,t)
print(ans)

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def MI(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



from itertools import permutations

N,M,R = LI()
r = LI()
A,B,C = MI(M,3)

def WF(E,n):
    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])
    return E

E = [[float('inf')]*N for _ in range(N)]
for i in range(N):
    E[i][i] = 0         
for i in range(M):
    E[A[i]-1][B[i]-1] = C[i]
    E[B[i]-1][A[i]-1] = C[i]     

E2 = WF(E,N) 

X = list(permutations(r))
ans = float('inf')

for x in X:
    now = 0
    for i in range(1,len(x)):
        now += E2[x[i-1]-1][x[i]-1]
    if now < ans:
        ans = now

print(ans)

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


sys.setrecursionlimit(1000000)
MOD = int(1e09) + 7
INF = int(1e15)


def main():
    
    N, M, R = Scanner.map_int()
    r = Scanner.map_int()
    for i in range(R):
        r[i] -= 1
    G = [[] for _ in range(N)]
    d = [[INF for _ in range(N)]for _ in range(N)]
    for i in range(N):
        d[i][i] = 0
    for i in range(M):
        a, b, c = Scanner.map_int()
        a -= 1
        b -= 1
        G[a].append((b, c))
        G[b].append((a, c))
        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])
    r.sort()
    ans = INF
    for v in itertools.permutations(r):
        now = 0
        for i in range(len(v)-1):
            now += d[v[i]][v[i+1]]
        ans = min(ans, now)
    print(ans)
    return


if __name__ == "__main__":
    main()

Solution (Python):
from itertools import permutations
N, M, R = map(int, input().split())
r = [int(c)-1 for c in input().split()]
cost = [[float('inf')]*N for i in range(N)]
for i in range(M):
  a, b, c = map(int, input().split())
  cost[a-1][b-1] = c
  cost[b-1][a-1] = c
def warshall_floyd(d,n):
    
    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
dist = warshall_floyd(cost,N)
ls = list(permutations(r))
ans = -1
for l in ls:
  m = 0
  p = l[0]
  flag = False
  for q in l[1:]:
    m += dist[p][q]
    p = q
  if ans==-1 or ans>m:
    ans = m
print(ans)

Solution (Python):
import sys
import itertools
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n,m,r = map(int,readline().split())

lst1 = [[float("inf")]*n for _ in range(n)]

lst2 = list(map(int,readline().split()))
for i in range(len(lst2)):
    lst2[i] -= 1

for i in range(m):
    x,y,w = map(int,readline().split())
    lst1[x-1][y-1] = w
    lst1[y-1][x-1] = w

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

lst1 = warshall_floyd(lst1)

ans = 10**10
for i in list(itertools.permutations(lst2)):
    res = 0
    before = i[0]
    for j in i[1:]:
        res += lst1[before][j]
        before = j

    ans = min(res,ans)
print(ans)