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 = list(map(lambda x:int(x)-1,(input().split())))

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

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

dist = warshall_floyd(dist)

min_ans = float("inf")
for perm in itertools.permutations(r):
    ans = 0
    for i in range(len(r)-1):
        ans += dist[perm[i]][perm[i+1]]
    min_ans = min(ans,min_ans)

print(min_ans)

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

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


dist=[[float("inf")]*(N+1) for i in range(N+1)] 
for i in range(M):
  a,b,c=map(int,input().split())
  dist[a][b]=c
  dist[b][a]=c
for i in range(N+1):
  dist[i][i]=0

dist=warshall_floyd(dist)


max_answer=float("inf")
for perm in itertools.permutations(rlist):
  
  answer=0
  for i in range(R-1):
    answer+=dist[perm[i]][perm[i+1]]
  
  max_answer=min(max_answer,answer)  
  
print(max_answer)

Solution (Python):
import itertools

n,m,r = map(int,input().split())
wa = [[float("INF")]*n for i in range(n)]
l = [i-1 for i in map(int,input().split())]
for i in range(m):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    wa[a][b] = c
    wa[b][a] = c
for i in range(n):
    wa[i][i] = 0

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

ans = float("INF")

for p in list(itertools.permutations(l)):
    count = 0
    for i in range(r-1):
        count += wa[p[i]][p[i+1]]
    ans = min(ans,count)
print(ans)

Solution (Python):
import sys
from itertools import permutations
 
 
def input():
    return sys.stdin.readline().strip()
 
 
def main():
    N, M, R = 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
 
    r = list(map(int, input().split()))
    d = [[float("inf")] * 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  
    D = warshall_floyd(d)
    P = list(permutations(r))
    cost = float("inf")
    for p in P:
        c = 0
        for i in range(R - 1):
            c += D[p[i] - 1][p[i + 1] - 1]
        if c < cost:
            cost = c
    print(cost)
 
 
if __name__ == "__main__":
    main()

Solution (Python):
import sys
from itertools import permutations


def input():
    return sys.stdin.readline().strip()


def main():
    N, M, R = map(int, input().split())

    def warshall_floyd(d):
        
        for k in range(N):
            for i in range(N):
                for j in range(N):
                    tmp = d[i][k] + d[k][j]
                    if d[i][j] > tmp:
                        d[i][j] = tmp
        return d

    r = list(map(int, input().split()))
    d = [[float("inf")] * 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  
    D = warshall_floyd(d)
    P = list(permutations(r))
    cost = float("inf")
    for p in P:
        c = 0
        for i in range(R - 1):
            c += D[p[i] - 1][p[i + 1] - 1]
        if c < cost:
            cost = c
    print(cost)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from itertools import permutations


def input():
    return sys.stdin.readline().strip()


def main():
    N, M, R = map(int, input().split())

    def warshall_floyd(d):
        
        for k in range(N):
            for i in range(N):
                for j in range(N):
                    tmp = d[i][k] + d[k][j]
                    if d[i][j] > tmp:
                        d[i][j] = tmp
        return d

    r = list(map(int, input().split()))
    d = [[float("inf")] * 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  
    D = warshall_floyd(d)
    P = list(permutations(r))
    cost = float("inf")
    for p in P:
        c = 0
        for i in range(R - 1):
            c += D[p[i] - 1][p[i + 1] - 1]
        if c < cost:
            cost = c
    print(cost)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from itertools import permutations

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, M, R = map(int, input().split())
    r = list(map(lambda x: int(x) - 1, input().split()))
    P = permutations(r)

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

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

    for k in range(N):
        for i in range(N):
            for j in range(N):
                tmp = dp[i][k] + dp[k][j]
                if tmp < dp[i][j]:
                    dp[i][j] = tmp

    ans = float("inf")
    for p in P:
        tmp = 0
        for i in range(R - 1):
            tmp += dp[p[i]][p[i + 1]]

        if tmp < ans:
            ans = tmp

    print(ans)


if __name__ == "__main__":
    main()

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

"""
https://juppy.hatenablog.com/entry/2018/11/01/%E8%9F%BB%E6%9C%AC_python_%E5%85%A8%E7%82%B9%E5%AF%BE%E6%9C%80%E7%9F%AD%E7%B5%8C%E8%B7%AF%E6%B3%95%EF%BC%88%E3%83%AF%E3%83%BC%E3%82%B7%E3%83%A3%E3%83%AB%E3%83%95%E3%83%AD%E3%82%A4%E3%83%89%E6%B3%95
"""

def warshall_floyd(d):
    n = len(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

graph = [[float("inf") for i in range(N)] for j 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 = dijkstra(graph)

ans = 1e10
for i in permutations(r):
    flag = True
    way = list(i)
    tmp = 0
    for i in range(len(way)-1):
        if dist[way[i]-1][way[i+1]-1] < 0:
            flag = False
            break
        tmp += dist[way[i]-1][way[i+1]-1]
    if flag:
        ans = min(tmp,ans)

print(int(ans))

Solution (Python):


from itertools import permutations
N,M,R = map(int,input().split())
r = list(map(int,input().split()))

"""
https://juppy.hatenablog.com/entry/2018/11/01/%E8%9F%BB%E6%9C%AC_python_%E5%85%A8%E7%82%B9%E5%AF%BE%E6%9C%80%E7%9F%AD%E7%B5%8C%E8%B7%AF%E6%B3%95%EF%BC%88%E3%83%AF%E3%83%BC%E3%82%B7%E3%83%A3%E3%83%AB%E3%83%95%E3%83%AD%E3%82%A4%E3%83%89%E6%B3%95
"""

def warshall_floyd(d):
    n = len(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

graph = [[float("inf") for i in range(N)] for j 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 = warshall_floyd(graph)

ans = 1e10
for i in permutations(r):
    flag = True
    way = list(i)
    tmp = 0
    for i in range(len(way)-1):
        if dist[way[i]-1][way[i+1]-1] < 0:
            flag = False
            break
        tmp += dist[way[i]-1][way[i+1]-1]
    if flag:
        ans = min(tmp,ans)

print(ans)

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

n,m,r = map(int,input().split())
rr = np.array(list(map(int,input().split()))) - 1

L = np.zeros((n,n),int)
for _ in range(m):
    a,b,c = map(int,input().split())
    L[a-1,b-1] = c

shortest = floyd_warshall(L, directed = False)

ans = float('inf')

for route in permutations(rr,len(rr)):
    ans = min(ans, shortest[route[:-1],route[1:]].sum())
print(int(ans))

Solution (Python):
import itertools
INF=10**30
N,M,R=map(int,input().split())
r=list(map(lambda x:int(x)-1,input().split()))

dist=[[INF]*N for i in range(N)]
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
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])
ans=INF
for x in itertools.permutations(r):
    res=0
    for i in range(len(x)-1):
        res+=dist[x[i]][x[i+1]]
    ans=min(ans,res)
print(ans)

Solution (Python):
import itertools

MAX_DIS = 10**10
N,M,R = map(int,input().split(" "))
r_list = list(map(int,input().split(" ")))
roads = [[MAX_DIS]*N for i in range(N)]
for i in range(N):
    roads[i][i] = 0
for i in range(M):
    A,B,C = map(int,input().split(" "))
    roads[A-1][B-1] = C
    roads[B-1][A-1] = C
for k in range(N):
    for i in range(N):
        for j in range(N):
            roads[i][j] = min(roads[i][j],roads[i][k]+roads[k][j])
min_dis = MAX_DIS
for directions in itertools.permutations(r_list):
    distance  = 0
    for dir in range(1,len(directions)):
        distance += roads[directions[dir-1]-1][directions[dir]-1]
    if distance < min_dis:
        min_dis =distance
print(min_dis)

Solution (Python):



import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall
from scipy.sparse import csr_matrix

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

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

E = np.array(E)
E = shortest_path(E,method = "FW")


stack = []
for i in range(len(r)):
  stack.append([r[i],[],0])
ans = 10 ** 18
while stack:
  v,visited,dist = stack.pop()
  if len(visited) != 0:
    dist += E[visited[-1]][v]
  visited2 = visited.copy()
  visited2.append(v)
  if len(visited2) == len(r):
    if dist < ans:
      ans = dist
    continue
  for i in range(len(r)):
    if r[i] not in visited2:
      stack.append([r[i],visited2,dist])
    
print(int(ans))

Solution (Python):
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
from itertools import permutations

n,m,R = map(int, input().split())
r = list(map(int, input().split()))
r = [i-1 for i in r]
abc = [list(map(int, input().split())) for i in range(m)]
edge = [[10 ** 9] * (n) for i in range(n)]
for a,b,c in abc:
  a-=1
  b-=1
  edge[a][b] = c
  edge[b][a] = c
d = floyd_warshall(edge)
ans = 10 ** 18
for i in permutations(r):
  tmp = 0
  for j in range(R-1):
    tmp += d[i[j]][i[j+1]]
  ans = min(ans,tmp)
print(int(ans))

Solution (Python):
t,r,g=map(int,input().split())
d=[[float("INF") for ccc in range(t)] for i in range(t)]
for i in range(t):
    d[i][i]=0
gl=list(map(int,input().split()))
for j in range(r):
    x,y,c=map(int,input().split())
    d[x-1][y-1]=c
    d[y-1][x-1]=c
for i in range(t):
    for j in range(t):
        for k in range(t):
            d[k][j]=min(d[k][j],d[k][i]+d[i][j])
from itertools import permutations as pe
ans=float("INF")
for G in pe(gl):
    p=0
    for qw in range(g-1):
        p+=d[G[qw]-1][G[qw+1]-1]
    ans=min(ans,p)
print(ans)

Solution (Python):
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

class WarshallFloyd():
    def __init__(self, N):
        self.N = N
        self.d = [[float("inf") for i in range(N)]
                  for i in range(N)]  

    def add(self, u, v, c, directed=False):
        """
        0-indexedであることに注意
        u = from, v = to, c = cost
        directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.d[u][v] = c
            self.d[v][u] = c
        else:
            self.d[u][v] = c

    def WarshallFloyd_search(self):
        
        
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    self.d[i][j] = min(
                        self.d[i][j], self.d[i][k] + self.d[k][j])
        for i in range(self.N):
            self.d[i][i] = 0
        return self.d

n,m,o = na()
r = na()
g = WarshallFloyd(n)

for i in range(m):
    a,b,c = na()
    g.add(a-1,b-1,c)

import itertools
p = min(8,n)
rs = list(itertools.permutations(r))

ans = 10000000000000
d = g.WarshallFloyd_search()
for l in rs:
    q = 0
    for j in range(len(l)-1):
        q += d[l[j+1]-1][l[j]-1]
    ans = min(ans, q)

print(ans)

Solution (Python):
import itertools 

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

class WarshallFloyd:
    def __init__(self,n):
        self.v = n
        self.d = [[1e100]*n for _ in range(n)]
        for i in range(n):
            self.d[i][i] = 0

    def path(self,x,y,c):
        if x == y:
            return False
        self.d[x][y] = c
        self.d[y][x] = c
        return True

    def build(self):
        for k in range(self.v):
            for i in range(self.v):
                for j in range(self.v):
                    self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])
        return self.d
wf = WarshallFloyd(N)

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

d = wf.build()
ans = 1e100
for T in itertools.permutations(r):
    Td = 0
    for i in range(len(T) - 1):
        Td += d[T[i]-1][T[i+1] - 1]
    ans = min(ans , Td)
print(ans)

Solution (Python):
from itertools import permutations
INF = 10 ** 8
N, M, R = map(int,input().split())
r = list(map(lambda x: int(x)-1 ,input().split()))
MAP = [[INF for i in range(N)] for j in range(N)]
for i in range(M):
    A, B, C = map(int,input().split())
    MAP[A-1][B-1] = C
    MAP[B-1][A-1] = C
for k in range(N):
    for i in range(N):
        for j in range(N):
            MAP[i][j] = min(MAP[i][j], MAP[i][k] + MAP[k][j])

ans = INF
for L in permutations(r):
    temp = 0
    for i in range(R-1):
        temp += MAP[L[i]][L[i+1]]
    ans = min(ans, temp)
print(ans)

Solution (Python):


import itertools
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

int1 = lambda x: int(x) - 1

N, M, R = map(int, input().split())
T = sorted(list(map(int1, input().split())))
A = np.array([tuple(map(int, input().split())) for _ in range(M)]).T

matr = csr_matrix((A[2], (A[0] - 1, A[1] - 1)), shape=(N, N))
way = [dijkstra(matr, indices=t, directed=False)[T].astype(int).tolist() for t in T]

result = float('inf')
for t in itertools.permutations(range(R)):
    tmp = 0
    for i in range(R - 1):
        tmp += way[t[i]][t[i + 1]]
    result = min(result, tmp)
print(result)

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

from itertools import permutations


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][j], D[i][k] + D[k][j])

P = list(permutations(R))

answer = float("inf")
for p in P:
    temporary = 0
    for k in range(r - 1):
        i, j = p[k], p[k + 1]
        temporary += D[i][j]
    answer = min(answer, temporary)

print(answer)

Solution (Python):
from itertools import permutations
n, m, r = map(int, input().split())
towns = [int(x) - 1 for x in input().split()]
inf = 10 ** 10
d = [[inf for _ in range(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

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

warshall_floyd(d, n)
ans = 10 ** 10
for t in permutations(towns):
    tmp = 0
    for i in range(len(t) - 1):
        tmp += d[t[i]][t[i+1]]
    ans = min(ans, tmp)


print(ans)

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

n,m,r= map(int, input().split())
rr= 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 i in range(n):
    d[i][i]=0

for i,j,k in a:
    i-=1
    j-=1
    d[i][j]=k
    d[j][i]=k



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)




INF=float('inf')
dp=[[INF]*r for i in range(1<<r)]
dp[0]=[0]*r

for i in range(1<<r):
    for k in range(r):
        
        if (i >> k) & 1:
            if i^(1<<k)==0:
                dp[i][k]=0
            else:
                
                for l in range(r):
                    if (i ^ (1 << k))>>l:
                        dpm = dp[i ^ (1 << k)][l]
                        ad = d[rr[l] - 1][ rr[k] - 1]
                        dp[i][k] = min(dpm + ad, dp[i][k])

print(min(dp[-1]))

Solution (Python):
import itertools
n,m,r = map(int,input().split())
ri = [int(i) for i in input().split()]


mat=[[10**18 for i in range(n+1)] for j in range(n+1)]

for i in range(n+1):
	mat[i][i]=0

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

for i in range(1,n+1):
	for x in range(1,n+1):
		for y in range(1,n+1):
			mat[x][y] = min(mat[x][y], mat[x][i] + mat[i][y])
            
            
permutations = list(itertools.permutations(range(1, r+1)))




ans = 10**18

for i in range(len(permutations)):
    tmp = 0
    for j in range(r-1):
        
        tmp += mat[ri[permutations[i][j]-1]][ri[permutations[i][j+1]-1]]
    ans = min(ans,tmp)
    
print(ans)

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

def warshall_floyd(dist):
    n = len(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])

def main():
    N, M, R = map(int, input().split())
    A = [int(i)-1 for i in input().split()]
    inf = float('inf')
    G = [[inf] * N for _ in range(N)]
    for i in range(N):
        G[i][i] = 0
    for _ in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        G[a][b] = min(G[a][b], c)
        G[b][a] = min(G[b][a], c)
    warshall_floyd(G)
    ans = float('inf')
    for perm in permutations(A, R):
        tmp = 0
        for i in range(R-1):
            tmp += G[perm[i]][perm[i+1]]
        ans = min(ans, tmp)
    print(ans)
    

if __name__ == '__main__':
    main()

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

import sys
input = sys.stdin.readline
n,m,r = map(int,input().split())
R = [int(i)-1 for i in input().split()]
d = [[10**9]*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
    
chk = tuple(warshall_floyd(d))
ans = float('inf')

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

Solution (Python):
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from pprint import pprint

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

n,m,R = myinput()
r = list(myinput())
abc = mylistinput(m)

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


for i in range(m):
    a = abc[i][0] - 1
    b = abc[i][1] - 1
    c = abc[i][2]
    d[a][b] = c
    d[b][a] = c


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



def warshall_floyd(n,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(n,d)


rp = list(permutations(r))


ls_count = []
for i in rp:
    count = 0
    for j in range(len(i)-1):
        s = i[j] - 1
        t = i[j+1] - 1
        count += d[s][t]
    ls_count.append(count)


ans = min(ls_count)
print(ans)

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

n, m, R = map(int, input().split())
r = list(map(int, input().split()))
INF = 10**10
dist = [[INF for _ in range(n)] for _ in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    dist[a][b] = c
    dist[b][a] = c

def warshall_floyd(n, 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

dist = warshall_floyd(n, dist)
ans = INF
for t in permutations(r):
    ans_t = 0
    for i in range(R-1):
        ans_t += dist[t[i]-1][t[i+1]-1]
    ans = min(ans, ans_t)
print(ans)

Solution (Python):
from itertools import permutations


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

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

    ans = 1001001001
    for way in permutations(r):
        ans_now = 0
        for i in range(R - 1):
            ans_now += dist[way[i]][way[i + 1]]
        if ans > ans_now: ans = ans_now
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import permutations


N, M, R = map(int, input().split())
r = list(map(int, input().split()))
INF = float('inf')

graph = [[INF for _ in range(N)] for _ in range(N)]

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

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

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

total_min = INF
for i in permutations(r, len(r)):
    total = 0
    for j in range(len(r)-1):
        total += graph[i[j]-1][i[j-1]-1]
    if total < total_min:
        total_min = total

print(total_min)

Solution (Python):

from itertools import permutations


def submit():
    n, m, _ = map(int, input().split())
    rlist = list(map(int, input().split()))
    rlist = [r - 1 for r in rlist]

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

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

    
    min_cost = float('inf')
    for pt in permutations(rlist):
        cost = 0
        for i in range(len(pt) - 1):
            cost += dp[pt[i]][pt[i + 1]]
        
        if min_cost > cost:
            min_cost = cost

    print(min_cost)


submit()

Solution (Python):
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

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

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 = [[float("inf") for i in range(n)] for i in range(n)] 

for i in range(m):
    x,y,z = abc[i]
    x-=1
    y-=1
    d[x][y] = z
    d[y][x] = z
for i in range(n):
    d[i][i] = 0 
warshall_floyd(d)

lst=list(permutations(r))


ans=float('inf')
for i in range(len(lst)):
    tmp=0
    for j in range(len(lst[i])-1):
        tmp+=d[lst[i][j+1]-1][lst[i][j]-1]
    ans=min(ans,tmp)
print(ans)

Solution (Python):
INF = 10 ** 8
import itertools

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

G = [[INF] * N for _ in range(N)]
for i in range(N):
    G[i][i] = 0
for el in ABC:
    a, b, c = el
    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][k] + G[k][j], G[i][j])


p = itertools.permutations(r)
m = INF
for el in p:
    
    dist = 0
    for i in range(R - 1):
        dist += G[el[i] - 1][el[i + 1] - 1]
    m = min(m, dist)
print(m)

Solution (Python):
from itertools import product,permutations

n,m,R = map(int,input().split())
r = list(map(int,input().split()))
INF = 10**10
d = [[INF for i in range(n)] for j 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,i,j in product(range(n),range(n),range(n)):d[i][j] = min(d[i][j],d[i][k]+d[k][j])

ans = INF

for v in permutations(r,R):
    dis = 0
    for i in range(R-1):
        dis += d[v[i]-1][v[i+1]-1]
    ans = min(ans,dis)

print(ans)

Solution (Python):
n,m,R = map(int,input().split())
r = list(map(int,input().split()))
INF = 10**10
d = [[INF for i in range(n)] for j 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])

from itertools import permutations

ans = INF
for v in permutations(r,R):
    dis = 0
    for i in range(R-1):
        dis += d[v[i]-1][v[i+1]-1]
    ans = min(ans,dis)

print(ans)

Solution (Python):
import copy
from collections import deque
n, m, r = map(int,input().split())
R = list(map(int, input().split()))

f_inf = float('inf')
wf = [[f_inf for _ in range(n+1)] for __ in range(n+1)]

tree = [[] for _ in range(n+1)]
for i in range(m):
    a, b, c = map(int, input().split())
    wf[a][b] = c
    wf[b][a] = c
for i in range(1, n+1):
    wf[i][i] = 0
for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            wf[i][j] = min(wf[i][j], wf[i][k]+wf[k][j])

all_type = []
def get_all_type(r, info, lon):
    if lon == len(info):
        return [info]
    result = []
    for i in r:
        if i in info:
            continue
        else:
            next_info = copy.deepcopy(info)
            next_info.append(i)
            result.extend(get_all_type(r, next_info, lon))
    return result

Result = []
for i in get_all_type(R, [], r):
    j = deque(i)
    x = j.popleft()
    result = 0
    while j:
        y = j.popleft()
        result += wf[x][y]
        x = y
    Result.append(result)
print(min(Result))

Solution (Python):
n,m,r  = map(int,input().split())
r_list = list(map(int,input().split()))
matrix = [[float("inf") for i in range(n)] for j in range(n)]
for c in range(n):
  matrix[c][c] = 0
for v in range(m):
  a,b,c = map(int,input().split())
  if matrix[a-1][b-1] > c:
    matrix[a-1][b-1] = c
    matrix[b-1][a-1] = c
import numpy as np
matrix = np.array(matrix)
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
load = shortest_path(matrix, directed=False)
import itertools
ans_list = []
for balls in itertools.permutations(r_list):
    balls = list(balls)
    ans = 0
    for i in range(1,len(r_list)):
      ans += load[balls[i-1]-1][balls[i]-1]
    ans_list.append(int(ans))
    
print(min(ans_list))