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):
class WarshallFloyd:
    
    def __init__(self,n,_first_index=0):
        self.v = n
        self._first_idx=_first_index
        self.d = [[float("INF")]*(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
        f=self._first_idx
        self.d[x-f][y-f] = c
        self.d[y-f][x-f] = 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
n,m,r=map(int,input().split())
rs=[x-1 for x in map(int,input().split())]
w=WarshallFloyd(n,1)
for i in range(m):w.path(*map(int,input().split()))
v=w.build()
from itertools import permutations as pe
print(min(sum(v[f][t]for f,t in zip(i,i[1:]))for i in pe(rs)))

Solution (Python):
from itertools import permutations

def main():
    N: int
    M: int
    R: int
    A: int
    B: int
    C: int
    ans: int    
    INF: int
    INF = 10 ** 10
    N, M, R = map(int, input().split())
    r: list = list(map(lambda x: x - 1, map(int, input().split())))
    dist :list = [[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] = 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 = INF
    for item in permutations(r):
        L: int = len(item)
        d: int = 0
        for i in range(1,L):
            pre: int = item[i-1]
            now: int = item[i]
            d += dist[pre][now]
        ans = min(ans, d)
    print(ans)  

if __name__ == "__main__":
    main()

Solution (Python):
from copy import deepcopy
from itertools import permutations


def warshallfloyd(N):  
    DIST = deepcopy(mat)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                DIST[i][j] = min(DIST[i][j], DIST[i][k] + DIST[k][j])
    return DIST


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

mat = [[10 ** 10] * n for _ in range(n)]
for i in range(n):
    mat[i][i] = 0
for a, b, c in abc:
    mat[a - 1][b - 1] = c
    mat[b - 1][a - 1] = c

ans = float('inf')
dist = warshallfloyd(n)
for route in permutations(town, r):
    bfo, tmp = route[0], 0
    for i in route[1:]:
        tmp += dist[bfo - 1][i - 1]
        bfo = i
    ans = min(ans, tmp)
print(ans)

Solution (Python):
from copy import deepcopy
from itertools import permutations


def warshallfloyd(N, LIST):  
    DIST = deepcopy(LIST)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                DIST[i][j] = min(DIST[i][j], DIST[i][k] + DIST[k][j])
    return DIST


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

mat = [[10 ** 10] * n for _ in range(n)]
for i in range(n):
    mat[i][i] = 0
for a, b, c in abc:
    mat[a - 1][b - 1] = c
    mat[b - 1][a - 1] = c

ans = float('inf')
dist = warshallfloyd(n, mat)
for route in permutations(town, r):
    bfo, tmp = route[0], 0
    for i in route[1:]:
        tmp += dist[bfo - 1][i - 1]
        bfo = i
    ans = min(ans, tmp)
print(ans)

Solution (Python):
from copy import deepcopy
from itertools import permutations


def warshallfloyd(N, LIST):  
    DIST = deepcopy(LIST)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                DIST[i][j] = min(DIST[i][j], DIST[i][k] + DIST[k][j])
    return DIST


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

mat = [[10 ** 10] * n for _ in range(n)]
for i in range(n):
    mat[i][i] = 0
for a, b, c in abc:
    mat[a - 1][b - 1] = c
    mat[b - 1][a - 1] = c

ans = float('inf')
dist = warshallfloyd(n, mat)
for route in permutations(town, r):
    tmp = 0
    for i, j in zip(route[:-1], route[1:]):
        tmp += dist[i - 1][j - 1]
    ans = min(ans, tmp)
print(ans)

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

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

n,w = n,m 

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

for i in range(w):
    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 
lst=warshall_floyd(d)

pro=list(permutations(range(r)))

ans=float('inf')
for i in pro:
    tmp=0
    for j in range(r-1):
        now=i[j]
        nxt=i[j+1]
        tmp+=lst[rlst[now]-1][rlst[nxt]-1]
    ans=min(ans,tmp)
print(ans)

Solution (Python):
import itertools
N, M, R = map(int, input().split())
r=[int(x) for x in input().split()]
r=[i-1 for i in r]
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())
	a-=1
	b-=1
	d[a][b]=min(d[a][b], c)
	d[b][a]=min(d[b][a], 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])

	return d 

d=warshall_floyd(d, N)
ans=float("inf")
for l in list(itertools.permutations(r)):
	temp=sum([d[l[i]][l[i+1]] for i in range(R-1)])
	ans=min(ans, temp)
print(ans)

Solution (Python):
from itertools import permutations

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

INF = 10**9
cost = [[INF]*N for _ in range(N)]
for _ in range(M):
  A, B, C = map(int, input().split())
  A -= 1
  B -= 1
  cost[A][B] = C
  cost[B][A] = C

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

ans = INF

for route in permutations(r):
  temp = 0
  for i in range(R-1):
    temp += cost[route[i]][route[i+1]]
  ans = min(ans, temp)

print(ans)

Solution (Python):
import heapq

N, M, R = map(int, input().split())
D = [int(a) - 1 for a in input().split()]
D.sort()
Dtod = {}
dtoD = {}
Dest = set()
for i, d in enumerate(D):
    Dtod[d] = i
    dtoD[i] = d
    Dest.add(d)
Map = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    Map[a].append((b, c))
    Map[b].append((a, c))

Roots = [[float('inf')] * R for _ in range(R)]
for i, d in enumerate(D):
    Roots[i][i] = 0
    Q = [d]
    Root = [float('inf')] * N
    Root[d] = 0
    while Q and (float('inf') in Roots[i]):
        q = heapq.heappop(Q)
        fatigue, now = divmod(q, 10**3)
        if now in Dest:
            Roots[i][Dtod[now]] = min(fatigue, Roots[i][Dtod[now]])
            Roots[Dtod[now]][i] = min(fatigue, Roots[Dtod[now]][i])
        for nex, cost in Map[now]:
            if Root[nex] > cost + fatigue:
                Root[nex] = cost + fatigue
                heapq.heappush(Q, (cost + fatigue) * 10**3 + nex)

DP = [[float('inf')] * (1 << R) for _ in range(R)]
bit_count = [0]
for _ in range(R):
    bit_count += [x+1 for x in bit_count]

for i in range(1 << R):
    cnt = bit_count[i]
    for j in range(R):
        if (i >> j) & 1 ==1:
            if cnt == 1:
                DP[j][i] = 0
            for k in range(R):
                if j == k:
                    continue
                DP[k][i|(1 << k)] = min(DP[k][i|(1 << k)], DP[j][i] + Roots[j][k])
ans = float('inf')
for i in range(R):
    ans = min(ans, DP[i][-1])
print(ans)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
from operator import itemgetter

import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson


sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
nf = lambda: float(ns())
na = lambda: list(map(int, stdin.readline().split()))
nb = lambda: list(map(float, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

N, M, R = na()
r = na()
g = [[0] * N for _ in range(N)]
for i in range(M):
    a, b, c = na()
    a -= 1
    b -= 1
    g[a][b] = c
    g[b][a] = c

g = np.array(g)
d = shortest_path(g)

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

Solution (Python):
n,m,r=map(int,input().split())
road=list(map(int,input().split()))
cost=[[float("inf")]*n for i in range(n)]
for i in range(n):
    cost[i][i]=0
for i in range(m):
    
    a,b,c=map(int,input().split())
    a,b=a-1,b-1
    cost[a][b]=c
    cost[b][a]=c
for k in range(n):
    for i in range(n):
        for j in range(n):
            cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j])
import itertools
ans=float("inf")
for i in itertools.permutations(road):
    tmp=0
    for j in range(len(i)-1):
        tmp+=cost[i[j]-1][i[j+1]-1]
    if tmp<ans:
        ans=tmp
print(ans)

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
N, M, R = map(int,input().split())
r = list(map(int,input().split()))
d = [[float("inf")]*N for i in range(N)]
edge = [[] 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

warshall_floyd(d)
ans = float('inf')

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

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

N,M,R = map(int,readline().split())
r = list(map(int,readline().split()))
INF = 10 ** 10

G = [[INF] * N for i in range(N)]
for i in range(M):
  a,b,c = map(int,readline().split())
  G[a - 1][b - 1] = c
  G[b - 1][a - 1] = c
  
for i in range(N):
  G[i][i] = 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])
      
import itertools
ans = INF
for perm in itertools.permutations(range(R)):
  dist = 0
  for i in range(1, len(perm)):
    dist += G[r[perm[i - 1]] - 1][r[perm[i]] - 1]
  if ans > dist:
    ans = dist
    
print(ans)

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

with open(0) as f:
    N, M, R = map(int, f.readline().split())
    r = list(map(int, f.readline().split()))
    path = [tuple(map(int, line.split())) for line in f.readlines()]

graph = np.full((N,N), np.inf)
for a, b, c in path:
    graph[a-1, b-1] = c
    graph[b-1, a-1] = c

graph = dijkstra(graph, directed=False)
ans = np.inf
permutation = list(permutations(r))
for p in permutation:
    way = 0
    for x,y in zip(p[:len(r)], p[1:]):
        way += graph[x-1, y-1]
    ans = min(ans, way)
print(int(ans))

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





N, M, R = getNM()

d = [[float("inf")] * N for i in range(N)]
list_R = [int(i) - 1 for i in input().split()]
for i in range(M):
   x, y, z = getNM()
   d[x - 1][y - 1] = min(d[x - 1][y - 1], z)
   d[y - 1][x - 1] = min(d[x - 1][y - 1], z)

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

warshall_floyd(d)

ans = float('inf')
for case in permutations(list_R):
    x1 = case[0]
    opt = 0
    for j in range(1, R):
        x2 = case[j]
        opt += d[x1][x2]
        x1 = x2
    ans = min(ans, opt)
print(ans)

Solution (Python):
import math
from typing import List, Counter, Tuple
from collections import Counter
from itertools import permutations


def read_int() -> int:
    return int(input().strip())


def read_ints() -> List[int]:
    return list(map(int, input().strip().split(' ')))


def solve() -> int:
    N, M, R = read_ints()
    r = [a-1 for a in read_ints()]
    inf = 10**10
    D = [
        [inf for _ in range(N)] for _ in range(N)
    ]
    for i in range(N):
        D[i][i] = 0
    for _ in range(M):
        a, b, c = read_ints()
        D[a-1][b-1] = D[b-1][a-1] = c
    for k in range(N):
        for i in range(N):
            for j in range(N):
                D[i][j] = min(D[i][j], D[i][k]+D[k][j])
    min_cost: int = inf
    for path in permutations(r):
        cost: int = 0
        for i in range(1, len(path)):
            cost += D[path[i-1]][path[i]]
        min_cost = min(min_cost, cost)
    return min_cost


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

Solution (Python):
from itertools import permutations
N,M,R = map(int,input().split())
r = list(map(lambda x:int(x)-1,input().split()))
edges = [[] for _ in range(N)]
for _ in range(M):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    edges[a].append((b,c))
    edges[b].append((a,c))
V = N
INF = float("inf")
dp = [[INF]*V for _ in range(V)]
for i in range(V):
    for j, w in edges[i]:
        dp[i][j] = w
for k in range(V):
    for i in range(V):
        for j in range(V):
            dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])

ans = INF
for p in permutations(r):
    t = 0
    for i in range(1, R):
        t += dp[p[i]][p[i-1]]
    ans = min(ans, t)
print(ans)

Solution (Python):
from itertools import permutations
N,M,R = map(int,input().split())
r = list(map(int,input().split()))
for i in range(R):
  r[i] -= 1
g = [[10 ** 8] * N for i in range(N)]
for i in range(M):
  A,B,C = map(int,input().split())
  A -= 1 
  B -= 1
  g[A][B] = C
  g[B][A] = C
def warchall_floyd(n):
  for i in range(n):
    
    for j in range(n):
      
      for k in range(n):
        
        g[j][k] = min(g[j][k],g[j][i]+g[i][k])
        
warchall_floyd(N)
ans = float('inf')
for i in permutations(r):
  now = 0
  for j in range(R-1):
    now += g[i[j]][i[j+1]]
  if now < ans:
    ans = now
print(ans)

Solution (Python):
from itertools import permutations as p


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


dist = [[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, B = A - 1, B - 1
    dist[A][B] = dist[B][A] = C



def main():
    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 combi in p(r, R):
        temp = 0
        for i in range(R - 1):
            cost = dist[combi[i]][combi[i + 1]]
            if cost < INF:
                temp += cost
            
            else:
                break
        else:
            ans = min(ans, temp)

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from itertools import permutations as p


INF = float('inf')
N, M, R = map(int, input().split())
r = list(map(lambda x:int(x) - 1, input().split()))
dist = [[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, B = A - 1, B - 1
    dist[A][B] = dist[B][A] = C


def main():
    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 combi in p(r, R):
        temp = 0
        for i in range(R - 1):
            cost = dist[combi[i]][combi[i + 1]]
            if cost < INF:
                temp += cost
            else:
                break
        else:
            ans = min(ans, temp)

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import itertools

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()) 
arr=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())
    x-=1
    y-=1
    d[x][y] = z
    d[y][x] = z
for i in range(n):
    d[i][i] = 0 

table=warshall_floyd(d)

ans=float('inf')
for lst in itertools.permutations(arr,r):
  cnt=0
  for i in range(r-1):
    cnt+=table[lst[i]-1][lst[i+1]-1]

  ans=min(ans,cnt)


print(ans)

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

d=[[float("INF")]*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())
  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
per=list(permutations(r,R))

ans=float("INF")
for l in per:
  cnt=0
  for j in range(R-1):
    cnt+=d[l[j]-1][l[j+1]-1]
  ans=min(cnt,ans)
print(ans)

Solution (Python):
import itertools

n,m,r = map(int,input().split())
R = list(map(int,input().split()))
V = [[] for i in range(n+1)]
for i in range(m):
    a,b,c = map(int,input().split())
    V[a].append([b,c])
    V[b].append([a,c])
    
cost = [[float("Inf") for j in range(n+1)] for i in range(n+1)]
for i in range(1,n+1):
    for j in range(1,n+1):
        for v,d in V[i]:
            if v == j:
                cost[i][j] = d

for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            if cost[i][j] > cost[i][k] + cost[k][j]:
                cost[i][j] = cost[i][k] + cost[k][j]

L = list(itertools.permutations(R, r))
ans = float("Inf")

for x in L:
    p = 0
    for i in range(len(x)-1):
        p += cost[x[i]][x[i+1]]
        
    ans = min(ans, p)
print(ans)

Solution (Python):
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

def main():
    n,m,R = i_map()
    r = i_list()
    c = [[INF]*n for i in range(n)]
    for i in range(n):
        c[i][i] = 0

    for _ in range(m):
        a,b,d = i_map()
        a -= 1
        b -= 1
        c[a][b] = c[b][a] = d

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

    r = list(itertools.permutations(r, R))

    ans = INF
    for i in r:
        trial = 0
        for k in range(len(i)-1):
            a = i[k] - 1
            b = i[k+1] - 1
            trial += c[a][b]
        ans = min(ans,trial)
    print(ans)




if __name__=="__main__":
    main()

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

    n, m, r = map(int, input().split())
    l = [int(i) - 1 for i in input().split()]
    d = [[10**8] * n for _ in range(n)]
    for _ in range(m):
        i, j, k = map(int, input().split())
        d[i-1][j-1] = k
        d[j-1][i-1] = k

    
    for k in range(n):
        for i in range(n-1):
            for j in range(i+1, n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
                    d[j][i] = d[i][j]

    
    
    from itertools import permutations

    answer = float('inf')
    for i in permutations(l):
        ans = 0
        for j in range(r-1):
            ans += d[i[j]][i[j+1]]
        if ans < answer:
            answer = ans

    print(answer)

main()

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

    n, m, r = map(int, input().split())
    l = [int(i) - 1 for i in input().split()]
    d = [[10**8] * n for _ in range(n)]
    for _ in range(m):
        i, j, k = map(int, input().split())
        d[i-1][j-1] = k
        d[j-1][i-1] = k

    
    for k in range(n):
        for i in range(n-1):
            for j in range(i+1, n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
                    d[j][i] = d[i][j]

    
    
    from itertools import permutations

    answer = float('inf')
    for i in permutations(l):
        ans = 0
        for j in range(r-1):
            ans += d[i[j]][i[j+1]]
        if ans < answer:
            answer = ans

    print(answer)

main()

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

    n, m, r = map(int, input().split())
    l = [int(i) - 1 for i in input().split()]
    d = [[10**8] * n for _ in range(n)]
    for _ in range(m):
        i, j, k = map(int, input().split())
        d[i-1][j-1] = k
        d[j-1][i-1] = k

    
    for k in range(n):
        for i in range(n-1):
            for j in range(i+1, n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
                    d[j][i] = d[i][j]

    
    
    from itertools import permutations

    answer = 10**8
    for i in permutations(l):
        ans = 0
        for j in range(r-1):
            ans += d[i[j]][i[j+1]]
        if ans < answer:
            answer = ans

    print(answer)

main()

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

    n, m, r = map(int, input().split())
    l = list(map(int, input().split()))
    for i in range(r):
        l[i] -= 1
    d = [[10**8] * n for _ in range(n)]
    for _ in range(m):
        i, j, k = map(int, input().split())
        d[i-1][j-1] = k
        d[j-1][i-1] = k

    
    for k in range(n):
        for i in range(n-1):
            for j in range(i+1, n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
                    d[j][i] = d[i][j]

    
    
    from itertools import permutations

    answer = 10**8
    for i in permutations(l):
        ans = 0
        for j in range(r-1):
            ans += d[i[j]][i[j+1]]
        if ans < answer:
            answer = ans

    print(answer)

main()

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

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

n,w = n,m

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

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


lst=list(permutations(r))

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

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

    n, m, r = map(int, input().split())
    l = list(map(int, input().split()))
    for i in range(r):
        l[i] -= 1
    d = [[10**8] * n for _ in range(n)]
    for _ in range(m):
        i, j, k = map(int, input().split())
        d[i-1][j-1] = k
        d[j-1][i-1] = k

    
    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]

    
    
    from itertools import permutations

    answer = 10**8
    for i in permutations(l):
        ans = 0
        for j in range(r-1):
            ans += d[i[j]][i[j+1]]
        if ans < answer:
            answer = ans

    print(answer)

main()

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

    n, m, r = map(int, input().split())
    l = list(map(int, input().split()))
    for i in range(r):
        l[i] -= 1
    d = [[float('inf')] * n for _ in range(n)]
    for _ in range(m):
        i, j, k = map(int, input().split())
        d[i-1][j-1] = k
        d[j-1][i-1] = k

    
    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]

    
    
    from itertools import permutations

    answer = float('inf')
    for i in permutations(l):
        ans = 0
        for j in range(r-1):
            ans += d[i[j]][i[j+1]]
        if ans < answer:
            answer = ans

    print(answer)

main()

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

N,M,R=list(map(int,input().split()))
r=list(map(int,input().split()))
ABC = [[float('inf')]*(N+1) for _ in range(N+1)]

for _ in range(M):
    a,b,c = map(int,input().split())
    if ABC[a][b]>c:
        ABC[a][b]=c
        ABC[b][a]=c


dist = [[float('inf')]*(N+1) for _ in range(N+1)]
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            ABC[i][j] = min(ABC[i][j],ABC[i][k] + ABC[k][j])

rotate = itertools.permutations(r)
ans = float('inf')
for rot in rotate:
    tmp = 0
    flag = 0
    for i in range(len(rot)-1):
        tmp +=ABC[rot[i]][rot[i+1]]
        if tmp>ans:
            flag = 1
            break
    if flag==0:
        ans = min(ans,tmp)
print(ans)

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

def main():
    import heapq
    import itertools

    def dijkstra(s, n):
        hq = [(0, s)]
        heapq.heapify(hq)  
        cost = [float('inf')] * n  
        cost[s] = 0  
        while hq:
            c, v = heapq.heappop(hq)
            if c > cost[v]:  
                continue
            for d, u in e[v]:
                tmp = d + cost[v]
                if tmp < cost[u]:
                    cost[u] = tmp
                    heapq.heappush(hq, (tmp, u))
        return cost



    N, M, R = MI()
    r = LI()
    e = [[]for _ in range(N)]
    dis_list = [[]for _ in range(N)]
    for i in range(M):
        a, b, c = MI()
        a, b = a - 1, b - 1
        e[a].append((c, b))
        e[b].append((c, a))
    for r_ in r:
        dis_list[r_ - 1] = dijkstra(r_ - 1, N)

    Ans_list = []
    P = itertools.permutations(r)
    for p in P:
        dis = 0
        for i in range(R - 1):
            dis += dis_list[p[i] - 1][p[i + 1] - 1]
        Ans_list.append(dis)
    ans = min(Ans_list)
    print(ans)

if __name__ == "__main__":
    main()