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):
n,m,r=map(int,input().split())

ans=3000000000

def permu(ju,now,su,co):
    if now==0:
        global ans
        ans=min(ans,su)
        return
    else:
        for i in range(r):
            if ju[i]:
                ju[i]=False
                su+=dp[co][rute[i]-1]
                permu(ju,now-1,su,rute[i]-1)
                ju[i]=True
                su-=dp[co][rute[i]-1]
    return

rute=list(map(int,input().split()))
dp=[[30000000 for i in range(n)] for i 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 i in range(n):
    for j in range(n):
        for k in range(n):
            dp[j][k]=min(dp[j][i]+dp[i][k],dp[j][k])


ju=[True for i in range(r)]
for i in range(r):
    ju[i]=False
    permu(ju,r-1,0,rute[i]-1)
    ju[i]=True
print(ans)

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

def WarshallFloyd(M):
    M = csgraph_from_dense(M)
    return floyd_warshall(M)

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

E = WarshallFloyd(E)
ans = min(sum(E[p[i]][p[i + 1]] for i in range(K - 1)) for p in permutations(R))
print(int(ans))

Solution (Python):
from itertools import permutations

def WarshallFloyd(M):
    N = len(M)
    for k in range(N):
        for j in range(N):
            for i in range(N):
                M[i][j] = min(M[i][j], M[i][k] + M[k][j])
    return M

INF = 1e10

N, M, K = map(int, input().split())
R = [int(i) - 1 for i in input().split()]
E = [[INF] * N for _ in range(N)]
for a, b, c in (map(int, input().split()) for _ in range(M)):
    a -= 1; b -= 1
    E[a][b] = E[b][a] = c

E = WarshallFloyd(E)
ans = min(sum(E[p[i]][p[i + 1]] for i in range(K - 1)) for p in permutations(R))
print(ans)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    N,M,R = map(int,input().split())
    r = list(map(int,input().split()))
    ABC = []
    D = [[float("inf")]*(N+1) for i in range(N+1)]
    for i 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])
                
    import itertools
    ans = float("inf")
    for v in itertools.permutations(r,R):
        
        tmp = 0
        for i in range(R-1):
            tmp += D[v[i]][v[i+1]]
        if tmp < ans:
            ans = tmp
    
    print(ans)
        
    
    
main()

Solution (Python):
from itertools import product, permutations,combinations


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

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

inf = 10000000000

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

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

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

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

min_dist = inf
for zyunro in permutations(r, len(r)):
	dist_sum = 0
	for i in range(R - 1):
		dist_sum += dist[zyunro[i] - 1][zyunro[i+1] - 1]
	min_dist = min(min_dist, dist_sum)

print(min_dist)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    n,m,r=map(int,input().split())
    R=list(map(lambda x:int(x)-1,input().split()))
    
    A=[[INF]*n for _ in range(n)]
    for i in range(n): A[i][i]=0
    for _ in range(m):
        a,b,c=map(int,input().split())
        a-=1
        b-=1
        A[a][b]=c
        A[b][a]=c
    
    from itertools import product
    for k,i,j in product(range(n),repeat=3):
        A[i][j]=min(A[i][j],A[i][k]+A[k][j])
    
    from itertools import permutations
    per=permutations(R)
    ans=INF
    for R in per:
        score=0
        for i in range(r-1):
            score+=A[R[i]][R[i+1]]
        ans=min(ans,score)
    print(ans)

resolve()

Solution (Python):
import itertools

N, M, R = map(int, input().split())
cities = list(map(int, input().split()))
INF = 10**10
dp = [[INF] * (N+1) for _ in range(N+1)]
for _ in range(M):
  s, g, c = map(int, input().split())
  dp[s][g] = c
  dp[g][s] = c
for i in range(N+1):
  dp[i][i] = 0
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])
patterns = itertools.permutations(cities, R)
ans = INF
for ptn in patterns:
  dis = 0
  for i in range(R-1):
    dis += dp[ptn[i]][ptn[i+1]]
  ans = min(ans, dis)
print(ans)

Solution (Python):
N, M, R = map(int, input().split())
rs = list(map(int, input().split()))
rs = [r-1 for r in rs]
D = [[100000*2000]*N for i 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] = 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 = 100000*2000
import itertools
for rs2 in itertools.permutations(rs):
  r2 = 0
  for i in range(1, R):
    r2 += D[rs2[i-1]][rs2[i]]
  r = min(r, r2)
print(r)

Solution (Python):
from itertools import*;from scipy.sparse import*
N,M,R=map(int,input().split());r=map(int,input().split())
G=[[9e9]*N for _ in[0]*N]
for _ in[0]*M:A,B,C=map(int,input().split());G[A-1][B-1]=G[B-1][A-1]=C
D=csgraph.dijkstra(csr_matrix(G))
print(int(min(sum(D[i-1,j-1]for i,j in zip(t,t[1:]))for t in permutations(r))))

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


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


    N, M, R = map(int, input().split())
    r = list(map(int, 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 = map(int, input().split())
        D[a-1][b-1] = c
        D[b-1][a-1] = c

    warshall_floyd(D, N)

    ans = float('inf')
    for P in itertools.permutations(r):
        cost = 0
        for i in range(R-1):
            cost += D[P[i]-1][P[i+1]-1]
        ans = min(ans, cost)

    print(ans)


if __name__ == '__main__':
    main()

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

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

def main():
    N, M, R = map(int, input().split())
    r = list(map(int, 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 = map(int, input().split())
        D[a-1][b-1] = c
        D[b-1][a-1] = c

    warshall_floyd(D, N)

    ans = float('inf')
    for P in itertools.permutations(r):
        cost = 0
        for i in range(R-1):
            cost += D[P[i]-1][P[i+1]-1]
        ans = min(ans, cost)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import itertools

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


N, M, R = map(int, input().split())
r = list(map(int, 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 = map(int, input().split())
    D[a-1][b-1] = c
    D[b-1][a-1] = c

warshall_floyd(D, N)

ans = float('inf')
for P in itertools.permutations(r):
    cost = 0
    for i in range(R-1):
        cost += D[P[i]-1][P[i+1]-1]
    ans = min(ans, cost)

print(ans)

Solution (Python):
def warshal_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()))
R = [r_-1 for r_ in R]

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

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

d = warshal_floyd(d)

import itertools
ans = float('inf')
for p in itertools.permutations(R):
  q = 0
  for i in range(len(p)-1):
    q += d[p[i]][p[i+1]]
  if q <= ans:
    ans = q
print(ans)

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

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

    MAX = int(1e9)
    link = [[MAX if i != j else 0 for j in range(N)] for i in range(N)]

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

    ans = -1
    for t in permutations(r):
        tmp = 0
        for i in range(1, R):
            tmp += link[t[i-1]-1][t[i]-1]
        if ans == -1:
            ans = tmp
        else:
            ans = min(ans, tmp)
    print(int(ans))

if __name__ == "__main__":
    main()

Solution (Python):
import itertools

def war(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

def main():
    N, M, R = map(int, input().split())
    r = list(map(int, input().split()))
    d = [[float('inf')] * N for _ in range(N)]

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

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

    war(N,d)
    ans = float('inf')

    for a in itertools.permutations(r):
        tmp = 0
        for i in range(len(a)-1):
            tmp += d[a[i]-1][a[i+1]-1]
        ans = min(ans, tmp)

    print(ans)


main()

Solution (Python):
import itertools
 
N, M, R = map(int, input().split())
r = [int(x) - 1 for x in input().split()]
 
dist = [[float('inf')] * N for _ in range(N)]
for _ in range(M):
	a, b, c = map(int, input().split())
	a -= 1
	b -= 1
	dist[a][b] = 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 = float('inf')
k = list(itertools.permutations(r))
for i in k:
	sumDist = 0
	for j in range(len(i) - 1):
		sumDist += dist[i[j]][i[j+1]]
	ans = min(ans, sumDist)
print(ans)

Solution (Python):
from itertools import permutations as p
def wf(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j]=min(d[i][j],d[i][k]+d[k][j])
    return d
n,m,r=map(int,input().split())
d=[[10**9]*n for i in range(n)] 
rl=list(map(int,input().split()))
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 i in range(n):
    d[i][i]=0
dl=wf(d)
pl=list(p(rl,r))
x=10**9
for i in pl:
  t=0
  for j in range(r-1):
    t+=dl[i[j]-1][i[j+1]-1]
  x=min(x,t)
print(x)

Solution (Python):
n,m,r = map(int,input().split())
l = list(map(int,input().split()))
g = [[10**10]*(n+1) for _ in range(n+1)]
for i in range(n+1):
  g[i][i] = 0
for _ in range(m):
  a,b,c = map(int,input().split())
  g[a][b] = c
  g[b][a] = c
for k in range(1,n+1):
  for i in range(1,n):
    for j in range(i+1,n+1):
      if g[i][j] >= g[i][k] + g[k][j]:
        g[i][j] = g[i][k] + g[k][j]
        g[j][i] = g[i][j]
g[0] = [0]*(n+1)
def dfs(cur,res,dis,use):
  if res == 0:
    return dis
  ans = 10**10
  for i in range(r):
    if not use[i]:
      use[i] = 1
      ans = min(ans, dfs(l[i],res-1,dis+g[cur][l[i]],use))
      use[i] = 0
  return ans
print(dfs(0,r,0,[0]*r))

Solution (Python):
import itertools


def dijkstra(v, G):
    import heapq

    ret = [10 ** 10] * len(G)
    ret[v] = 0
    q = [(ret[i], i) for i in range(len(G))]
    heapq.heapify(q)

    while len(q):
        tmpr, u = heapq.heappop(q)
        if tmpr == ret[u]:
            for w, l in G[u]:
                if ret[w] > ret[u] + l:
                    ret[w] = ret[u] + l
                    heapq.heappush(q, (ret[w], w))
    return ret


N, M, R = map(int, input().split())
r = list(map(int, input().split()))
NE = [[] for _ in range(N)]
for _ in range(M):
    A, B, C = map(int, input().split())
    NE[A - 1].append((B - 1, C))
    NE[B - 1].append((A - 1, C))

RE = [[0] * R for _ in range(R)]
for iR in range(R):
    for jR in range(iR + 1, R):
        lR = dijkstra(r[iR] - 1, NE)[r[jR] - 1]
        RE[iR][jR] = lR
        RE[jR][iR] = lR

ans = 10 ** 10
for p in itertools.permutations(range(R)):
    ans = min(ans, sum([RE[p[i]][p[i + 1]] for i in range(R - 1)]))

print(ans)

Solution (Python):

import sys, itertools

def WarshallFloyd(V: int, cost: "List[List[int]]"):
    """
    全ての頂点対の間の最短距離を求めます。
    ==============
    V: 頂点数
    cost: 隣接行列(辺が存在しない部分はINF)
    --------------
    cost: 最短距離の行列
    """
    for k in range(V):
        for i in range(V):
            for j in range(V):
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
    return cost

def solve(N: int, M: int, R: int, r: "List[int]", A: "List[int]", B: "List[int]", C: "List[int]"):
    INF = 1e18
    G = [[INF for _ in range(N)] for _ in range(N)]
    for i in range(M):
        G[A[i]-1][B[i]-1] = C[i]
        G[B[i]-1][A[i]-1] = C[i]
    cost = WarshallFloyd(N, G)
    mn = 1e18
    for p in itertools.permutations(r):
        path = 0
        for i in range(R-1):
            path += cost[p[i+1]-1][p[i]-1]
        mn = min(path, mn)
    print(mn)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    R = int(next(tokens))  
    r = [int(next(tokens)) for _ in range(R)]  
    A = [int()] * (M)  
    B = [int()] * (M)  
    C = [int()] * (M)  
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    solve(N, M, R, r, A, B, C)

if __name__ == '__main__':
    main()

Solution (Python):
import sys,itertools
input=sys.stdin.readline
INF=float('inf')
n,m,r=map(int,input().split())
R=list(map(int,input().split()))
distance=[[INF]*n for _ in range(n)]
for _ in range(m):
   a,b,c=map(int,input().split())
   distance[a-1][b-1]=c
   distance[b-1][a-1]=c

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

ans=INF
for p in itertools.permutations(R):
   cnt=0
   for q in range(r-1):
      cnt+=distance[p[q]-1][p[q+1]-1]
   ans=min(ans,cnt)

print(ans)

Solution (Python):
n, m, r = map(int,input().split())
R = list(map(int,input().split()))
A = [list(map(int,input().split())) for i in range(m)]

M = [[float("inf")] * (n+1) for i in range(n+1)]

for i in range(1, n+1):
    M[i][i] = 0
for i in range(m):
    M[A[i][0]][A[i][1]] = A[i][2]
    M[A[i][1]][A[i][0]] = A[i][2]






from scipy.sparse.csgraph import floyd_warshall
M = floyd_warshall(M)

import itertools
R1 = list(itertools.permutations(R))

ans = float("inf")
for i in range(len(R1)):
    ans1 = 0
    for j in range(r-1):
        ans1 += M[R1[i][j]][R1[i][j+1]]
    ans = min(ans, ans1)

print(int(ans))

Solution (Python):

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


def A():
    s = S()
    if "9" in s:
        print("Yes")
    else:
        print("No")
    return


def B():
    n = II()
    ans = 0
    for _ in range(n):
        l, r = LI()
        ans += r - l + 1
    print(ans)
    return


def C():
    n = II()
    A = {}
    for _ in range(n):
        k = II()
        if not k in A:
            A[k] = 1
        else:
            A[k] += 1
    ans = 0
    for item in A.values():
        ans += item % 2
    print(ans)
    return


def D():
    n, m, R = LI()
    r = LI()
    edg = [[0 if i == k else inf for k in range(n)] for i in range(n)]
    for _ in range(m):
        a, b, c = LI_()
        edg[a][b] = c + 1
        edg[b][a] = c + 1
    for k in range(n):
        for a in range(n):
            for b in range(n):
                edg[a][b] = min(edg[a][b], edg[a][k] + edg[k][b])
    ans = inf
    fullserch = itertools.permutations(range(R), R)
    for fulls in fullserch:
        b = 0
        for i in range(R - 1):
            b += edg[r[fulls[i]] - 1][r[fulls[i + 1]] - 1]
        ans = min(ans, b)
    print(ans)
    return


if __name__ == '__main__':
    D()

Solution (Python):



import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().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

n,m,R = LI()
r = LI()
d = [[inf]*n for _ in range(n)]
for _ in range(m):
    a,b,c = LI()
    d[a-1][b-1] = c
    d[b-1][a-1] = c

d = warshall_floyd(d)
ans = inf
for i in permutations(r,R):
    tmp = 0
    for j in range(R-1):
        tmp += d[i[j]-1][i[j+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()))
s=[[0]*n for i in range(n)]
for i in range(m):
    a, b, c = list(map(int, input().split()))
    a, b = a-1, b-1
    s[a][b] = c
    s[b][a] = c
s=floyd_warshall(s)   

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

Solution (Python):
from itertools import permutations

N, M, R = map(int, input().split())
r = [int(i)-1 for i in input().split()]
v = [[] for _ in range(N)]
for _ in range(M) :
    A, B, C = map(int, input().split())
    v[A-1].append((B-1, C))
    v[B-1].append((A-1, C))

def dijkstra(s) :
    queue = [(s, 0)]
    dist = [float('inf')] * N
    dist[s] = 0
    while queue :
        cur, ccost = queue.pop()
        for nex, ncost in v[cur] :
            if ccost + ncost < dist[nex] :
                dist[nex] = ccost + ncost
                queue.append((nex, ccost + ncost))
    return dist
    
dist = dict()
for rr in r :
    dist[rr] = dijkstra(rr)

lr = len(r)
m = float('inf')
for perm in permutations(r) :
    tot = 0
    for i in range(lr-1) :
        tot += dist[perm[i]][perm[i+1]]
    m = min(m, tot)
    
print(m)

Solution (Python):
from itertools import permutations

inf = float("inf")

N, M, R = map(int, input().split())
r = [int(s) - 1 for s in input().split()]
d = [[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
for k in range(N):
    for i in range(N):
        for j in range(N):
            d[i][j] = d[j][i] = min(d[i][j], d[i][k] + d[k][j])
ans = min([sum([d[r[p[i]]][r[p[i+1]]] for i in range(R-1)])
           for p in permutations(range(R))])
print(ans)

Solution (Python):
import itertools

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

def main():
    n,m,r = map(int,input().split())
    ls = [int(x) for x in input().split()]
    map_ls = [[float("inf") for _ in range(n+1)] for _ in range(n+1)]
    for _ in range(m):
        a,b,c = map(int,input().split())
        map_ls[a][b] = c
        map_ls[b][a] = c
    edes = Warshall_Floyd(map_ls,n+1)
    ans = int(10**9+7)
    for i in list(itertools.permutations(ls)):
        cnt = 0
        for j in range(1,r):
            now_,next_ = i[j-1],i[j]
            
            cnt += edes[now_][next_]
        ans = min(ans,cnt)
    print(ans)


if __name__ == "__main__":
    main()

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

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

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

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


    def ind(i, R, rem, l, ans):
        if i == R:
            ans.append(l)
            return ans
        for r in rem:
            nl = l[:]
            nl.append(r)
            nr = rem[:]
            nr.remove(r)
            ans = ind(i+1, R, nr, nl, ans)
        return ans

    inds = ind(0, R, [i for i in range(R)], [], [])

    for k, ind in enumerate(inds):
        D = 0
        for j in range(R-1):
            D += dp[Rs[ind[j]]-1][Rs[ind[j+1]]-1]
        if k == 0:
            ans = D
        ans = min(ans, D)
    print(ans)

if __name__ == "__main__":
    main()

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

n,m,r=[int(x) for x in input().split()]
rlist=[int(x)-1 for x in input().split()]
abc=[[int(x) for x in input().split()] for _ in range(m)]

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

for item in abc:
  if item[2]<adj[item[0]-1][item[1]-1]: adj[item[0]-1][item[1]-1]=item[2]
  if item[2]<adj[item[1]-1][item[0]-1]: adj[item[1]-1][item[0]-1]=item[2] 

adj=floyd_warshall(adj)

res=float("inf")

for route in itertools.permutations(rlist):
  tmp=sum([adj[route[i]][route[i+1]] for i in range(len(route)-1)])
  if tmp<res: res=tmp

print(int(res))

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

n,m,r=[int(x) for x in input().split()]
rlist=[int(x)-1 for x in input().split()]
abc=[[int(x) for x in input().split()] for _ in range(m)]

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

for item in abc:
  if item[2]<adj[item[0]-1][item[1]-1]: adj[item[0]-1][item[1]-1]=item[2]
  if item[2]<adj[item[1]-1][item[0]-1]: adj[item[1]-1][item[0]-1]=item[2] 

d=floyd_warshall(adj)

res=float("inf")

for route in itertools.permutations(rlist):
  tmp=sum([d[route[i]][route[i+1]] for i in range(len(route)-1)])
  if tmp<res: res=tmp

print(int(res))

Solution (Python):
import itertools

inf = 10 ** 9
n, m, r = map(int, input().split())
r_list = [int(i) - 1 for i in input().split()]
a_list = [[inf for _ in range(n)] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    a_list[a][b] = a_list[b][a] = c
for k in range(n):
    for i in range(n):
        for j in range(i + 1, n):
            x = a_list[i][k] + a_list[k][j]
            if x < a_list[i][j]:
                a_list[i][j] = a_list[j][i] = x
k = list(itertools.permutations(r_list))
ans = inf
for kk in k:
    temp = 0
    for k1, k2 in zip(kk[:-1], kk[1:]):
        temp += a_list[k1][k2]
    if ans > temp:
        ans = temp
print(ans)

Solution (Python):
from itertools import permutations
import numpy as np

MAX = 1e9
N, M, r = map(int, input().split())
R = list(map(lambda x: int(x) - 1, input().split()))
E = np.array([MAX]*(N**2), dtype=int).reshape((N, N))
for i in range(N):
    E[i, i] = 0
for _ in range(M):
    s, t, d = map(int, input().split())
    E[s-1, t-1] = d
    E[t-1, s-1] = d

for k in range(N):
    for i in range(N):
        E[i, :] = np.minimum(E[i, :], E[i, k] + E[k, :])

perm = permutations(R)
ans = MAX
for p in perm:
    c = 0
    for i in range(r-1):
        c += E[p[i]][p[i+1]]
    ans = min(ans, c)
print(ans)