Problem:
 Score : 400 points    Problem Statement There are N towns in the State of Atcoder, connected by M bidirectional roads.  The i -th road connects Town A_i and B_i and has a length of C_i .  Joisino is visiting R towns in the state, r_1,r_2,..,r_R (not necessarily in this order).  She will fly to the first town she visits, and fly back from the last town she visits, but for the rest of the trip she will have to travel by road.  If she visits the towns in the order that minimizes the distance traveled by road, what will that distance be?      Constraints  2≤N≤200  1≤M≤N×(N-1)/2  2≤R≤min(8,N) ( min(8,N) is the smaller of 8 and N .)  r_i≠r_j (i≠j)  1≤A_i,B_i≤N, A_i≠B_i  (A_i,B_i)≠(A_j,B_j),(A_i,B_i)≠(B_j,A_j) (i≠j)  1≤C_i≤100000  Every town can be reached from every town by road.  All input values are integers.         Input Input is given from Standard Input in the following format:  N  M  R  r_1  ...  r_R  A_1  B_1  C_1  :  A_M  B_M  C_M       Output Print the distance traveled by road if Joisino visits the towns in the order that minimizes it.        Sample Input 1 3 3 3
1 2 3
1 2 1
2 3 1
3 1 4      Sample Output 1 2  For example, if she visits the towns in the order of 1 , 2 , 3 , the distance traveled will be 2 , which is the minimum possible.       Sample Input 2 3 3 2
1 3
2 3 2
1 3 6
1 2 2      Sample Output 2 4  The shortest distance between Towns 1 and 3 is 4 . Thus, whether she visits Town 1 or 3 first, the distance traveled will be 4 .       Sample Input 3 4 6 3
2 3 4
1 2 4
2 3 3
4 3 1
1 4 1
4 2 2
3 1 6      Sample Output 3 3

Solution (Python):
from itertools import product, permutations


def warshall_floyd(d):
    
    for k, i, j in product(range(n), repeat=3):
        if d[i][j] > d[i][k] + d[k][j]:
            d[i][j] = d[i][k] + d[k][j]


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

ans = float("inf")
for np in permutations(r_list):
    cand = sum([d[np[i]][np[i + 1]] for i in range(r - 1)])
    ans = min(ans, cand)

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

INF = float("inf")

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

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)

Solution (Python):
from itertools import permutations
 
 
def warshall_floyd(d):
    
    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]
 
 
INF = float("inf")
 
n, m, r = map(int, input().split())
r_list = list(map(lambda x: int(x) - 1, input().split()))
d = [[INF] * n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    d[a][b] = d[b][a] = c
warshall_floyd(d)
 
ans = float("inf")
for np in permutations(r_list):
    cand = sum([d[np[i]][np[i + 1]] for i in range(r - 1)])
    ans = min(ans, cand)
 
print(ans)

Solution (Python):
from scipy.sparse import *
from itertools import *
 
n,m,r = [int(x) for x in input().split()]
R = [int(i)-1 for i in input().split()]
route_list = [[0]*n for i in range(n)]
ans = 10**9
for j in range(m):
  a,b,c = map(int,input().split())
  route_list[a-1][b-1] = c
  route_list[b-1][a-1] = c
 
Co = csgraph.floyd_warshall(route_list)
 
for v in permutations(R):
  temp = 0
  for i in range(1,r):
    temp += Co[v[i-1]][v[i]]
  ans = min(ans,temp)
print(int(ans))

Solution (Python):
from scipy.sparse import *
from itertools import *
 
n,m,r = [int(x) for x in input().split()]
R = [int(i)-1 for i in input().split()]
route_list = [[10**8]*n for i in range(n)]
ans = 10**9
for j in range(m):
  a,b,c = map(int,input().split())
  route_list[a-1][b-1] = c
  route_list[b-1][a-1] = c
 
Co = csgraph.floyd_warshall(csr_matrix(route_list))
 
for v in permutations(R):
  temp = 0
  for i in range(1,r):
    temp += Co[v[i-1]][v[i]]
  ans = min(ans,temp)
print(int(ans))

Solution (Python):
from scipy.sparse import *
from itertools import *

n,m,r = [int(x) for x in input().split()]
R = [int(i)-1 for i in input().split()]
route_list = [[0]*n for i in range(n)]
ans = 10**9
for j in range(m):
  a,b,c = map(int,input().split())
  route_list[a-1][b-1] = c
  route_list[b-1][a-1] = c
 
Co = csgraph.floyd_warshall(csr_matrix(route_list))
 
for v in permutations(R):
  temp = 0
  for i in range(1,r):
    temp += Co[v[i-1]][v[i]]
  ans = min(ans,temp)
print(int(ans))

Solution (Python):
import math
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):
                d[i][j] = min(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**9]*N for i 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):
import numpy as np
from scipy.sparse.csgraph import dijkstra
import itertools
from scipy.sparse import csr_matrix
inf = 1 + 10**8
n, m, r = list(map(int, input().split()))
r = list(map(int, input().split()))
graph = np.full((n+1,n+1), inf)
for i in range(m):
    a,b,c = list(map(int, input().split()))
    graph[a][b] = c
    graph[b][a] = c
p_list = list(itertools.permutations(r,len(r)))
graph = dijkstra(csr_matrix(graph))
min_cost = inf * 200
for i in p_list:
    candidate = 0
    for j in range(len(i) - 1):
        candidate += graph[i[j]][i[j + 1]]
    if min_cost > candidate:
        min_cost = candidate
print(int(min_cost))

Solution (Python):
import sys
import itertools
input = sys.stdin.readline
inf = 200000000
n, m, r = map(int,input().split())
rs = list(map(int,input().split()))
d = [[inf] * (n+1) for j in range(n+1)]
for i in range(n+1):
    d[i][i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    d[a][b] = d[b][a] = c
for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(i+1,n+1):
            d[i][j] = d[j][i] = min(d[i][j], d[i][k] + d[k][j])
p = list(itertools.permutations(range(r)))
s = inf
for q in p:
    t = 0
    for i in range(r-1):
        t += d[rs[q[i]]][rs[q[i+1]]]
    if s > t:
        s = t
print(s)

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

import itertools
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')

N, M, R = LI()
r = LI()
cur = 0
ans = inf
d = [[float("inf") for i in range(N)] for i in range(N)]

for i in range(M):
    x,y,z = map(int,input().split())
    d[x-1][y-1] = z
    d[y-1][x-1] = z
for i in range(N):
    d[i][i] = 0 

W = warshall_floyd(N,d)
loop = int(1)


for course in itertools.permutations(r):
    cur = int(0)
    for i in range(len(course)-1):
        to = course[i+1]
        go = course[i]
        cur += W[go-1][to-1]
    ans = min(ans,cur)

print(ans)

Solution (Python):
import itertools

N,M,R = map(int,input().split())
Visit = list(map(int,input().split()))
lVisit = len(Visit)

Data = []
INF = 10**10
for _ in range(N):
    Data.append([INF]*N)
for i in range(N):
    Data[i][i] = 0
for _ in range(M):
    a,b,c = map(int,input().split())
    Data[a-1][b-1] = c
    Data[b-1][a-1] = c

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

ans = 10**10
for course in list(itertools.permutations(Visit)):
    sum1 = 0
    for i in range(lVisit-1):
        to = course[i+1]
        fm = course[i]
        sum1 += Data[fm-1][to-1]
    ans = min(ans,sum1)
print(ans)

Solution (Python):



def wantans(nowp,sc,rlis,ans):

    if len(rlis) == 0:
        ans = min(ans , sc)
        return ans

    for i in range(len(rlis)):

        nexsc = sc

        nexlis = []
        for j in range(len(rlis)):
            if i != j:
                nexlis.append(rlis[j])

        if nowp != None:
            nexsc += lis[nowp][rlis[i]]
            
        ans = wantans(rlis[i],nexsc,nexlis,ans)

    return ans
        




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

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

lis = [ [float("inf")] * N for i in range(N) ]

for i in range(N):

    lis[i][i] = 0

for i in range(M):

    A,B,C = map(int,input().split())

    A -= 1
    B -= 1

    lis[A][B] = C
    lis[B][A] = C

for k in range(N):

    for i in range(N):

        for j in range(N):

            lis[i][j] = min(lis[i][j],lis[i][k]+lis[k][j])



for i in range(R):
    r[i] -= 1
    
ans = wantans(None,0,r,float("inf"))

print (ans)

Solution (Python):
from itertools import permutations


class WarshallFloyd(object):

    def __init__(self, adj):
        """
        ワーシャル・フロイド法によって全頂点間の最短距離を O(|V|^3) で計算する。

        :param adj: 隣接行列 adj[i][j] でi番目の頂点からj番目の頂点へのコストを示す パスがなければINF
        """
        self._dist = adj  
        for i in range(len(adj)):
            self._dist[i][i] = 0

        self._solve()

    def _solve(self):
        v_len = len(self._dist)
        for i in range(v_len):  
            for j in range(v_len):  
                for k in range(v_len):  
                    self._dist[j][k] = min(self._dist[j][k], self._dist[j][i] + self._dist[i][k])

    def distance(self, start, goal):
        return self._dist[start][goal]

    def path(self, start, goal):
        pass


N, M, R = map(int, input().split())
r = list(map(int, input().split()))
adj = [[float('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

wf = WarshallFloyd(adj)

ans = float('inf')
tours = list(map(list, permutations(r, R)))
for tour in tours:
    cost = 0
    for i in range(1, len(tour)):
        cost += wf.distance(tour[i - 1], tour[i])
    ans = min(ans, cost)
print(ans)

Solution (Python):
import itertools
n,m,R=map(int,input().split())
r=list(map(int,input().split()))
abc=[list(map(int,input().split())) for i in range(m)]
inf=float("inf")
data=[[inf]*(n+1) for i in range(n+1)]
for i in range(n+1):
    data[i][i]=0
for u in abc:
    a,b,c=u
    data[a][b]=c
    data[b][a]=c
for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            data[i][j]=min(data[i][j],data[i][k]+data[k][j])
ans=inf
for h in itertools.permutations(r):
    l=0
    for j in range(1,R):
        l+=data[h[j-1]][h[j]]
    ans=min(ans,l)
print(ans)

Solution (Python):
import itertools
def main():

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

    dist = [[float('inf') for _ in range(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())
        dist[a-1][b-1] = c
        dist[b-1][a-1] = 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])

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

    return ans

if __name__ == '__main__':
    print(main())

Solution (Python):
import math
import itertools
import sys
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N, M, R = IL()
r = IL()
abc = [IL() for _ in range(M)]

dp = [[MAX_INT]*(N+1) for _ in range(N+1)]
for a, b, c in abc:
  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):
      if i == j:
        dp[i][j] = 0
      else:
        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])


ans = MAX_INT
for root in itertools.permutations(r):
  tmp = 0
  for i in range(R-1):
    tmp += dp[root[i]][root[i + 1]]
  else:
    ans = min(ans, tmp)
print(ans)

Solution (Python):
from scipy.sparse import*
from itertools import*
n,m,r = map(int,input().split())
R = [int(i)-1 for i in input().split()]
cost = [[0]*n for i in range(n)]
ans = 10**9
for j in range(m):
  a,b,c = map(int,input().split())
  cost[a-1][b-1] = c
  cost[b-1][a-1] = c

Co = csgraph.floyd_warshall(csr_matrix(cost))

for v in permutations(R):
  temp = 0
  for i in range(1,r):
    temp += Co[v[i-1]][v[i]]
  ans = min(ans,temp)
print(int(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()))
    r = 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])

    md = 10 ** 10
    for v in itertools.permutations(r, len(r)):
        l = 0
        d = 0
        for i, vv in enumerate(v):
            if i == 0:
                l = vv - 1
            else:
                d += wl[l][vv-1]
                l = vv-1
        md = min(md, d)
    print(md)


if __name__ == '__main__':
    solve()

Solution (Python):
from itertools import permutations

inf = float('inf')
n, m, r = map(int, input().split())  
t = tuple(int(x) - 1 for x in input().split())  
g = [[inf] * n for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    g[a][b] = c
    g[b][a] = 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 = inf
for p in permutations(t):
    ans = min(ans, sum(g[a][b] for a, b in zip(p, p[1:])))
print(ans)

Solution (Python):
from itertools import permutations


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


INF = float("inf")

n, m, r = map(int, input().split())
r_list = list(map(lambda x: int(x) - 1, input().split()))
d = [[INF] * n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    d[a][b] = d[b][a] = c
warshall_floyd(d)

ans = float("inf")
for np in permutations(r_list):
    cand = sum([d[np[i]][np[i + 1]] for i in range(r - 1)])
    ans = min(ans, cand)

print(ans)

Solution (Python):
def dijkstra(s,n,w,cost):
    
    
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    while True:
        v = -1
        
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d
import itertools
N,M,R=[int(x) for x in input().split()]
r=[int(x) for x in input().split()]
cost = [[float("inf") for i in range(N)] for i in range(N)] 
d=[[0]*N for _ in range(N)]
for i in range(M):
  x,y,z = [int(x) for x in input().split()]
  cost[x-1][y-1]=z
  cost[y-1][x-1]=z
for i in range(N):
  d[i]=dijkstra(i,N,M,cost)
r=list(itertools.permutations(r))
ans=10**9
for i in r:
  res=0
  for j in range(len(i)-1):
    res+=d[i[j]-1][i[j+1]-1]
  ans=min(ans,res)
print(ans)

Solution (Python):
n,m,k1=map(int,input().split())
mat=[[10**9 for j in range(n)]for i in range(n)]
r=[int(i)-1 for i in input().split()]
for i in range(m):
    a,b,c=map(int,input().split())
    mat[a-1][b-1]=c 
    mat[b-1][a-1]=c
for i in range(n):
    mat[i][i]=0 
dp=[[10**9 for j in range(n)]for i in range(n)]
for i in range(n):
    dp[i][i]=0 
for k in range(n):
    for i in range(n):
        for j in range(n):
            if mat[k][j]==10**9:
                continue 
            mat[i][j]=min(mat[i][j], mat[i][k]+mat[k][j])
            mat[j][i]=mat[i][j]

dp=mat 
mini=10**100 

from itertools import permutations
for i in permutations(r) : 
    ans=0 
   
    for j in range(1,k1): 
        ans+=dp[i[j-1]][i[j]]
    
    mini=min(mini,ans)
print(mini)

Solution (Python):


import itertools

def main():
  n, m, r = map(int, input().split())
  list_r = [one_r-1 for one_r in map(int, input().split())]

  dist = [[float("inf")] * n for _ in range(n)]
  for i in range(n):
    dist[i][i] = 0
  for i in range(m):
    a, b, c = map(int, input().split())
    dist[a-1][b-1] = c
    dist[b-1][a-1] = c
  for k in range(n):
    for i in range(n):
      for j in range(n):
        if dist[i][j] > dist[i][k] + dist[k][j]:
          dist[i][j] = dist[i][k] + dist[k][j]

  result = float("inf")
  for one_cand in itertools.permutations(list_r):
    temp = 0
    for i in range(r-1):
      temp += dist[one_cand[i]][one_cand[i+1]]
    if temp < result:
      result = temp
  print(result)
  

if __name__ == "__main__":
  main()

Solution (Python):


import itertools

def main():
  n, m, r = map(int, input().split())
  list_r = [one_r-1 for one_r in map(int, input().split())]

  dist = [[float("inf")] * n for _ in range(n)]
  for i in range(n):
    dist[i][i] = 0
  for i in range(m):
    a, b, c = map(int, input().split())
    dist[a-1][b-1] = c
    dist[b-1][a-1] = c
  for k in range(n):
    for i in range(n):
      for j in range(n):
        if dist[i][j] > dist[i][k] + dist[k][j]:
          dist[i][j] = dist[i][k] + dist[k][j]

  result = float("inf")
  for one_cand in itertools.permutations(list_r):
    temp = 0
    for i in range(r-1):
      temp += dist[one_cand[i]][one_cand[i+1]]
    if temp < result:
      result = temp
  print(result)
  

if __name__ == "__main__":
  main()

Solution (Python):
import itertools

def main():
  n, m, r = map(int, input().split())
  list_r = [one_r-1 for one_r in map(int, input().split())]

  dist = [[float("inf")] * n for _ in range(n)]
  for i in range(n):
    dist[i][i] = 0
  for i in range(m):
    a, b, c = map(int, input().split())
    dist[a-1][b-1] = c
    dist[b-1][a-1] = c
  for k in range(n):
    for i in range(n):
      for j in range(n):
        if dist[i][j] > dist[i][k] + dist[k][j]:
          dist[i][j] = dist[i][k] + dist[k][j]

  result = float("inf")
  for one_cand in itertools.permutations(list_r):
    temp = 0
    for i in range(r-1):
      temp += dist[one_cand[i]][one_cand[i+1]]
    if temp < result:
      result = temp
  print(result)
  

if __name__ == "__main__":
  main()

Solution (Python):
from itertools import permutations
import sys

def main():
    
    N, M, R = map(int, sys.stdin.readline().split())
    r = [i - 1 for i in map(int, sys.stdin.readline().split())]
    
    d = [[float('inf')] * N for _ in range(N)]
    
    for i in range(N):
        d[i][i] = 0
        
    for i 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 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]
    
    ans = 10**12
    
    for each in permutations(r):
        t_dis = 0
        for i in range(R-1):
            t_dis += d[each[i]][each[i+1]]  
        
        ans = min(ans, t_dis)
    
    print(ans)

if __name__ == '__main__':
    main()

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

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

G = [[10**8]*(N+1) for _ in range(N+1)]   
for _ in range(M):
    A, B, C = map(int, input().split())
    
    G[A][B] = C
    G[B][A] = C

    
    

dg = csgraph_from_dense(G, null_value=10**8)
d = floyd_warshall(dg)


ans = 10**12
for Q in itertools.permutations(r):
    c = 0
    for i in range(R-1):
        c += d[Q[i]][Q[i+1]]
    ans = min(ans, c)
print(int(ans))

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

N, M, R = map(int, input().split())
r = list(input().split())
edge = np.array([input().split() for _ in range(M)], dtype = np.int64).T
graph = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))

lst = floyd_warshall(graph, directed = False)

def calc(path):
    cost = 0
    s = int(path[0]) - 1
    for i in range(1, R):
        g = int(path[i]) - 1
        cost += lst[s, g]
        s = g
    return cost

ans = 10 ** 18
for tmp in permutations(r):
    
    ans = min(ans, calc(tmp))

print (int(ans))

Solution (Python):
def resolve():
    
    N,M,R = map(int,input().split())
    r = list(map(int,input().split()))
    DP = [[2 ** 63 - 1 for _ in range(N)] for _ in range(N)]

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

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

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

    import itertools
    ans = 2 ** 63 - 1 
    for v in itertools.permutations(r,R):
        s = 0
        for i in range(R-1):
            s += DP[v[i]-1][v[i+1]-1]
        ans = min(ans,s)
    print(ans)
resolve()

Solution (Python):
import itertools
n,m,R = map(int,input().split())
r = list(map(int,input().split()))
cost = [[-1]*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(n):
            if k == i or k == j or cost[i][k] == -1 or cost[k][j] == -1:
                continue
            if cost[i][j] == -1:
                cost[i][j] = cost[i][k]+cost[k][j]
            else:
                cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j])

ans = -1
for p in itertools.permutations(r):
    c = 0
    for i in range(R-1):
        c += cost[p[i]-1][p[i+1]-1]
    if ans == -1:
        ans = c
    else:
        ans = min(c, ans)
print(ans)

Solution (Python):
import heapq
import itertools


class Graph:
    def __init__(self, n_nodes):
        self.n_nodes = n_nodes
        self.edges = [[] for _ in range(n_nodes)]

    def add_edge(self, s, t, d=None, undirected=False):
        if d is not None:
            self.edges[s].append((t, d))
        else:
            self.edges[s].append(t)
        if undirected:
            self.add_edge(t, s, d)

    def add_edges(self, edges, undirected=False):
        for edge in edges:
            self.add_edge(*edge, undirected=undirected)


class Dijkstra:
    def __init__(self, graph):
        self.graph = graph

    def compute_all(self, s):
        distances = [float('inf') for _ in range(self.graph.n_nodes)]
        visited = [False for _ in range(self.graph.n_nodes)]
        prev_nodes = [None for _ in range(self.graph.n_nodes)]
        distances[s] = 0
        q = []
        for t in range(self.graph.n_nodes):
            heapq.heappush(q, (distances[t], t))
        while q:
            dist_x, x = heapq.heappop(q)
            if visited[x]:
                continue
            visited[x] = True

            for y, d_xy in self.graph.edges[x]:
                if visited[y]:
                    continue
                dist_y = dist_x + d_xy
                if dist_y < distances[y]:
                    distances[y] = dist_y
                    prev_nodes[y] = x
                    heapq.heappush(q, (dist_y, y))
        return distances, prev_nodes


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

graph = Graph(n + 1)
graph.add_edges([list(map(int,
                          input().split())) for _ in range(m)],
                undirected=True)
dijkstra = Dijkstra(graph)
distances = []
for i in range(n + 1):
    ds, _ = dijkstra.compute_all(i)
    distances.append(ds)
res = float('inf')
for perm in itertools.permutations(rs):
    s = sum([distances[a][b] for a, b in zip(perm, perm[1:])])
    res = min(res, s)
print(res)

Solution (Python):
import itertools


class Graph:
    def __init__(self, n_nodes):
        self.n_nodes = n_nodes
        self.edges = [[] for _ in range(n_nodes)]

    def add_edge(self, s, t, d=None, undirected=False):
        if d is not None:
            self.edges[s].append((t, d))
        else:
            self.edges[s].append(t)
        if undirected:
            self.add_edge(t, s, d)

    def add_edges(self, edges, undirected=False):
        for edge in edges:
            self.add_edge(*edge, undirected=undirected)


class FloydWarshall:
    def __init__(self, graph):
        self.graph = graph
        self.distances = [[float('inf')] * graph.n_nodes
                          for _ in range(graph.n_nodes)]
        self.nexts = [[None] * graph.n_nodes for _ in range(graph.n_nodes)]
        self._init()

    def _init(self):
        for x in range(self.graph.n_nodes):
            self.distances[x][x] = 0
        for source in range(self.graph.n_nodes):
            for destination, distance in self.graph.edges[source]:
                self.distances[source][destination] = distance
                self.nexts[source][destination] = destination

    def compute_shortest_path_lengths(self):
        for k in range(self.graph.n_nodes):
            for i in range(self.graph.n_nodes):
                for j in range(self.graph.n_nodes):
                    s = self.distances[i][k] + self.distances[k][j]
                    if s < self.distances[i][j]:
                        self.distances[i][j] = s
                        self.nexts[i][j] = self.nexts[i][k]

    def get_shortest_path(self, x, y):
        if self.nexts[x][y] is None:
            return []
        path = [x]
        while path[-1] != y:
            s = path[-1]
            t = self.nexts[s][y]
            path.append(t)
        return path


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

graph = Graph(n + 1)
graph.add_edges([list(map(int,
                          input().split())) for _ in range(m)],
                undirected=True)
fw = FloydWarshall(graph)
fw.compute_shortest_path_lengths()
res = float('inf')
for perm in itertools.permutations(rs):
    s = sum([fw.distances[a][b] for a, b in zip(perm, perm[1:])])
    res = min(res, s)
print(res)

Solution (Python):
import sys
sys.setrecursionlimit(500000)


def dfs(c,p,d):
    if c == R:
        if ans[0] > d:
            ans[0] = d
        return
    for i in range(R):
        if memo[i]:continue
        memo[i] = True
        if p == -1:
            dfs(c+1,i,0)
        else:dfs(c+1,i,d+graph[r[p]][r[i]])
        memo[i] = False

N,M,R = map(int,input().split())
r = [i-1 for i in map(int,input().split())]
graph = [[float("Inf") if i != j else 0 for i in range(N)] for j in range(N)]
for i in range(M):
    x,y,z = map(int,input().split())
    graph[x-1][y-1] = z
    graph[y-1][x-1] = z
for k in range(N):
    for i in range(N):
        for j in range(N):
            if graph[i][j] > graph[i][k] + graph[k][j]:
                graph[i][j] = graph[i][k] + graph[k][j]
memo = [False]*R
ans = [float("Inf")]
dfs(0,-1,0)
print(ans[0])

Solution (Python):

from heapq import heappop, heappush
from itertools import permutations


def dijkstra(source: int) -> "Array[int]":
    
    size = len(G)
    dist = [float("inf")] * size
    dist[source] = 0
    undetermined = size - 2  
    queue = [(0, source)]
    while queue:
        cost, v = heappop(queue)
        if cost > dist[v]:
            continue
        for next_cost, u in G[v]:
            if cost + next_cost < dist[u]:
                dist[u] = cost + next_cost
                heappush(queue, (dist[u], u))
        undetermined -= 1
        if not undetermined:
            return dist
    return dist


def main():
    global G
    N, M, R, *RABC = map(int, open(0).read().split())
    visit, ABC = RABC[:R], RABC[R:]
    G = [[] for _ in range(N + 1)]
    for v, u, cost in zip(*[iter(ABC)] * 3):
        G[v].append((cost, u)), G[u].append((cost, v))
    dist = {v: dijkstra(v) for v in visit}
    ans = float("inf")
    for perm in permutations(visit):
        cur = sum(dist[v][u] for v, u in zip(perm, perm[1:]))
        ans = min(ans, cur)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

from heapq import heapify, heappop, heappush
from itertools import permutations


def dijkstra(source: int) -> list:
    dist = [float("inf")] * (N + 1)
    undetermined = N  
    queue = [(0, source)]
    heapify(queue)
    while queue:
        cost, v = heappop(queue)
        if cost > dist[v]:
            continue
        dist[v] = cost
        for next_cost, u in G[v]:
            if cost + next_cost < dist[u]:
                heappush(queue, (cost + next_cost, u))
        undetermined -= 1
        if not undetermined:
            return dist


def main():
    global G, N
    N, M, R, *RABC = map(int, open(0).read().split())
    visit, ABC = RABC[:R], RABC[R:]
    G = [[] for _ in range(N + 1)]
    for v, u, cost in zip(*[iter(ABC)] * 3):
        G[v].append((cost, u)), G[u].append((cost, v))
    dist = {v: dijkstra(v) for v in visit}
    ans = float("inf")
    for perm in permutations(visit):
        cur = sum(dist[v][u] for v, u in zip(perm, perm[1:]))
        ans = min(ans, cur)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

from heapq import heapify, heappop, heappush
from itertools import permutations


def dijkstra(G: "Array[Array[int]]", size: int, start: int) -> list:
    dist = [float("inf")] * size
    checked = [0] * size
    checked[0] = 1
    queue = [(0, start)]
    heapify(queue)
    while queue:
        cost, v = heappop(queue)
        if cost > dist[v]:
            continue
        dist[v] = cost
        for next_cost, u in G[v]:
            if cost + next_cost < dist[u]:
                heappush(queue, (cost + next_cost, u))
        checked[v] = 1
        if sum(checked) == size:
            return dist


def main():
    global G, N
    N, M, R, *RABC = map(int, open(0).read().split())
    visit, ABC = RABC[:R], RABC[R:]
    G = [[] for _ in range(N + 1)]
    for v, u, cost in zip(*[iter(ABC)] * 3):
        G[v].append((cost, u)), G[u].append((cost, v))
    dist = {v: dijkstra(G, N + 1, v) for v in visit}
    ans = float("inf")
    for perm in permutations(visit):
        cur = sum(dist[v][u] for v, u in zip(perm, perm[1:]))
        ans = min(ans, cur)
    print(ans)


if __name__ == "__main__":
    main()