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 permutations, product
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

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

dist = [[float('inf') for _ in range(N)] for _ in range(N)]
A, B, C = [0] * M, [0] * M, [0] * M
for i in range(M):
    a, b, c = abc[i]
    A[i] = a - 1
    B[i] = b - 1
    C[i] = c

g = csr_matrix((C, (A, B)), shape=(N, N), dtype=int)
dist = floyd_warshall(g, directed=False)

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

Solution (Python):
import itertools
N, M, R = map(int, input().split())
r = [int(x) - 1 for x in input().split()]
G = [[10 ** 7 for j in range(N)] for i in range(N)]
for i in range(N):
  G[i][i] = 0
for i in range(M):
  a, b, c = map(int, input().split())
  G[a - 1][b - 1] = c
  G[b - 1][a - 1] = c
def warshall_floyd(G):
  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])
  return G
G = warshall_floyd(G)
D = 10 ** 8
for L in itertools.permutations(r):
  d = 0
  pre = L[0]
  for l in L[1:]:
    d += G[pre][l]
    pre = l
  D = min(d, D)
print(D)

Solution (Python):
from itertools import permutations, product

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

dist = [[float('inf') for _ in range(N)] for _ in range(N)]
for a, b, c in abc:
    dist[a - 1][b - 1] = c
    dist[b - 1][a - 1] = c

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

ans = float('inf')
for route in permutations(r):
    d = 0
    for i in range(R - 1):
        s = route[i] - 1
        g = route[i + 1] - 1
        d += dist[s][g]
    ans = min(ans, d)
print(ans)

Solution (Python):
import itertools
N, M, R = map(int, raw_input().split())
r = [int(x)-1 for x in raw_input().split()]
D = []
for i in range(N):
  D.append([200000000]*N)
  D[i][i]=0
A = [0]*M
B = [0]*M
C = [0]*M
for i in range(M):
  a, b, C[i] = map(int, raw_input().split())
  A[i] = a-1
  B[i] = b-1
  D[A[i]][B[i]] = C[i]
  D[B[i]][A[i]] = C[i]
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])
ml = 2000000000
for p in itertools.permutations(r):
  l = 0
  for i in range(R-1):
    l += D[p[i]][p[i+1]]
  ml = min(ml, l)
print ml

Solution (Python):
N, M, R = map(int, input().split())
RL = [int(x) for x in input().split()]

import heapq
def dijkstra(adj, n, st=1):
    dj = [2**64] * (n + 1)
    dj[st] = 0
    q = []
    heapq.heappush(q, (0, st))
    while q:
        fc, fn = heapq.heappop(q)
        if dj[fn] < fc: continue
        for tn, lc in adj[fn]:
            if dj[fn] + lc < dj[tn]:
                dj[tn] = dj[fn] + lc
                heapq.heappush(q, (dj[tn], tn))
    return dj

adj = dict((x, []) for x in range(N + 1))
for _ in range(M):
    a, b, c = map(int, input().split())
    adj[a].append((b, c))
    adj[b].append((a, c))

costs = [None] * len(RL)
for i, r in enumerate(RL):
    costs[i] =  dijkstra(adj, N, r)

import functools
@functools.lru_cache(maxsize=None)
def f(last, cost, left):
    if not left: return cost
    ret = float('inf')
    for i, x in enumerate(left):
        ret = min(ret, f(x, cost + costs[RL.index(last)][x], left[:i] + left[i+1:]))
    return ret

print(min(f(x, 0, tuple(set(RL) - set([x]))) for x in RL))

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

fn = lambda: [int(x) for x in input().split()]
N, M, R = fn()
r = [int(ri) - 1 for ri in input().split()]
A, B, C = [0]*M, [0]*M, [0]*M
for i in range(M):
    A[i], B[i], C[i] = fn()
    A[i], B[i] = A[i] - 1, B[i] - 1

G = csr_matrix((C, (A, B)), shape=(N, N), dtype=int)
D = floyd_warshall(G, directed=False)

routes = permutations(r)
result = float('inf')
for route in routes:
    d = sum([D[route[i], route[i+1]] for i in range(len(route) - 1)])
    result = min(result, d)
print(int(result))

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):
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())


N,M,R = inpl()
rr = inpl()

weight = [[INF for i in range(N)] for j in range(R)]
for r in range(R):
	weight[r][rr[r]-1] = 0

lines = defaultdict(set)
for i in range(M):
	a,b,c = inpl()
	a -= 1
	b -= 1
	lines[a].add((b,c))
	lines[b].add((a,c))

def search (s,w_0,r):
	global weight
	global q
	for line in list(lines[s]):
		t = line[0]
		w = w_0 + line[1]
		if weight[r][t] > w:
			heapq.heappush(q, [w,t])
			weight[r][t] = w

for r in range(R):
	q = [ [0, rr[r]-1] ]
	heapq.heapify(q)
	while q:
		w_0,s = heapq.heappop(q)
		search(s,w_0,r)

ans = INF
for li in list(itertools.permutations(range(R))):
	tmp = 0
	for i in range(R-1):
		s = li[i]
		t = li[i+1]
		tmp += weight[s][rr[t]-1]
	ans = min(ans,tmp)

print(ans)

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def warshall_floyd(g):
    d = defaultdict(dict)
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v))
    V = set(V)
    for i in V:
        for j in V:
            if i in g and j in g[i]:
                d[i][j] = g[i][j]
            else:
                d[i][j] = sys.maxsize
    for k in g:
        for i in g:
            for j in g:
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]

    return d


@mt
def slv(N, M, R, ABC):
    g = defaultdict(dict)
    for a, b, c in ABC:
        g[a][b] = c
        g[b][a] = c

    d = warshall_floyd(g)
    ans = sys.maxsize
    for m in permutations(R):
        c = 0
        for i in range(len(R)-1):
            c += d[m[i]][m[i+1]]
        ans = min(ans, c)

    return ans


def main():
    N, M, R = read_int_n()
    R = read_int_n()
    ABC = [read_int_n() for _ in range(M)]
    print(slv(N, M, R, ABC))


if __name__ == '__main__':
    main()

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

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

u,v,l = zip(*[map(int,input().split()) for i in range(m)])

A=csgraph.dijkstra(csr_matrix((l,(u,v)),[n+1]*2),0)

s=min(sum(A[i][j] for i,j in zip(a[:-1],a[1:])) for a in pm(r))
print(int(s))

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

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

u,v,l = zip(*[map(int,input().split()) for i in range(m)])

A=csgraph.dijkstra(csr_matrix((l,(u,v)),(n+1,n+1)),0)

s=min(sum(A[i][j] for i,j in zip(a[:-1],a[1:])) for a in pm(r))
print(int(s))

Solution (Python):
import itertools
N,M,R=map(int,input().split())
r=[int(i)-1 for i in input().split()]
P=[set() for i in range(N)]
for i in range(M):
    A,B,C=map(int,input().split())
    P[A-1].add((B-1,C))
    P[B-1].add((A-1,C))
p=[[0 for i in range(R)] for i in range(R)]
def dijkstra(s):
    d=[10**9 for i in range(N)]
    d[s]=0
    Q=set(range(N))
    while(len(Q)>0):
        u=list(Q)[0]
        for v in Q:
            if d[v]<d[u]:
                u=v
        Q-=set([u])
        for v in P[u]:
            if d[v[0]]>d[u]+v[1]:
                d[v[0]]=d[u]+v[1]
    return d
for i in range(R):
    L=dijkstra(r[i])
    for j in range(R):
        p[i][j]=L[r[j]]
S=list(itertools.permutations(range(R),R))
ans=10**9
for sg in S:
    tmp=0
    for i in range(R-1):
        tmp+=p[sg[i]][sg[i+1]]
    if tmp<ans:
        ans=tmp
print(ans)

Solution (Python):
import heapq

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

INF = 1 << 40
G, dist = [[] for i in range(N)], [[INF for k in range(N)] for j in range(N)]


def dijkstra(s):
    check = [0 for i in range(N)]
    dist[s][s], pq = 0, []
    heapq.heappush(pq, (0, s))

    while len(pq) != 0:
        u = heapq.heappop(pq)
        check[u[1]] = 2

        if dist[s][u[1]] < u[0]:
            continue

        for v in G[u[1]]:
            if dist[s][u[1]] + v[1] < dist[s][v[0]]:
                dist[s][v[0]], check[v[0]] = dist[s][u[1]] + v[1], 1
                heapq.heappush(pq, (dist[s][v[0]], v[0]))


check_dfs, cost_lst = [0 for m in range(R)], []


def dfs(s, cnt, cost):
    if cnt == 0:
        cost_lst.append(cost)
        return

    for i in range(R):
        if check_dfs[i] == 0:
            check_dfs[i] = 1
            dfs(r[i]-1, cnt-1, cost+dist[s][r[i]-1])
            check_dfs[i] = 0


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

    for i in range(R):
        dijkstra(r[i]-1)

    for i in range(R):
        check_dfs[i] = 1
        dfs(r[i]-1, R-1, 0)
        check_dfs[i] = 0

    print(min(cost_lst))


if __name__ == '__main__':
    main()

Solution (Python):
import math
from itertools import permutations

def make_list(V,E):
 
    edges = []
    path=[[0]*E for i in range(V) ]   
    
    for i in range(V):
        a=[int(x) for x in str(input()).split()]
        for j in range(len(a)):
            
            path[i][j]=i
           
                
                
	
        edges.append((a))    
	

   
     
    return edges ,path



def warshall_floyd(glath):
	
	for k in range(len(glath)):
		for i in range(len(glath)):
			for j in range(len(glath[i])):
				if glath[i][j] > glath[i][k] + glath[k][j]:
                                   glath[i][j] = glath[i][k] + glath[k][j]
                                   glath[j][i] = glath[i][k] + glath[k][j]
				
				
	return glath





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

r=[int(x) for x in str(input()).split()]


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


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




all_cost=warshall_floyd(graph)






max_count=float("inf")


for i in permutations(r):
        cost=0
        for j in range(len(i)-1):
                
                cost+= all_cost[i[j]-1][i[j+1]-1]
       
        max_count=min(max_count,cost)





print(max_count)

Solution (Python):
from itertools import permutations

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

visit = list(map(int, input().split()))
g = [[float('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] = c
    g[b][a] = c


def dijkstra(start):
    c_l = [float('inf')] * N
    c_l[start] = 0
    visited = [False] * N
    while True:
        min_v = float('inf')
        next = -1
        visited[start] = True
        for i in range(N):
            if visited[i]:
                continue
            if g[start][i]:
                d = c_l[start] + g[start][i]
                if d < c_l[i]:
                    c_l[i] = d
                if min_v > c_l[i]:
                    min_v = c_l[i]
                    next = i
        start = next
        if next == -1:
            break
    return c_l


cost_list = []
for i in range(N):
    cost_list.append(dijkstra(i))

cost = float('inf')
for town in permutations(visit):
    c = 0
    for i in range(R - 1):
        c += cost_list[town[i] - 1][town[i + 1] - 1]
    cost = min(cost, c)
print(cost)

Solution (Python):
import itertools

n,m,R = map(int,input().split())
r = list(map(int,input().split()))
data = [[]for _ in range(0,n+1)]
d = [[] for _ in range(0,R)]

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

def dijkstra(start,num):
    g = [float("inf") for _ in range(0,n+1)]
    used = ["false" for _ in range(0,n+1)]
    g[start] = 0
    queue= []
    queue.append((start,data[start]))
    while queue:
        start,edge = queue.pop(0)
        for to,cost in edge:
            if g[to] > g[start] + cost:
                g[to] = g[start] + cost
                queue.append((to,data[to]))
    for i in range(0,R):
        d[num].append(g[r[i]])
    


for i in range(0,R):
    dijkstra(r[i],i)
    
ans = float("inf")
seq = itertools.permutations([i for i in range(0,R)])
for i in seq:
    dis = 0
    for j in range(0,len(i)-1):
        dis += d[i[j]][i[j+1]]
    if ans > dis:
        ans = dis
print(ans)

Solution (Python):
N, M, R = [int(_) for _ in input().split()]
r = [int(_) - 1 for _ in input().split()]

from collections import defaultdict
from itertools import permutations

INF = 10**10

D = [[INF] * N for _ in range(N)]

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

result = INF


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

for xs in permutations(r):
    r = 0
    for i in range(R - 1):
        st, ed = xs[i], xs[i + 1]
        r += D[st][ed]
    result = min(result, r)

print(result)

Solution (Python):
from itertools import permutations

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

INF=float('inf')
d=[[INF for x in range(N)] for y 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 i in range(N):
  for j in range(N):
    for k in range(N):
      if d[j][i]+d[i][k] < d[j][k]:
        d[j][k]=d[j][i]+d[i][k]

ans=INF
for root in permutations(r):
  cnt=0
  for i in range(R-1):
    cnt+=d[root[i]-1][root[i+1]-1]
    if cnt>ans:
      break
  ans=min(ans,cnt)
print(ans)

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

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


def full(L):
    if len(L) == 1:
        return [L]
    else:
        L2 = []
        for i in range(len(L)):
            L2.extend([[L[i]] + Lc for Lc in full(L[:i] + L[i+1:])])
        return L2


L = full(R)
ans = float("inf")
for l in L:
    a = 0
    for i in range(Rs-1):
        a += D[l[i]][l[i+1]]
    ans = min(ans, a)

print(ans)

Solution (Python):
from itertools import permutations
import heapq
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
D = [[] for _ in range(N)]
inf = float("inf")
for i in range(N):
    for j in range(N):
        if i == j:
            D[i].append(0)
        else:
            D[i].append(inf)

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


def WarshallFloyd(D):
    """
    >>> WarshallFloyd([[0, 1, 4], [1, 0, 1], [4, 1, 0]])
    [[0, 1, 2], [1, 0, 1], [2, 1, 0]]
    """
    for k in range(len(D)):
        for i in range(len(D)):
            for j in range(len(D)):
                D[i][j] = min(D[i][j], D[i][k] + D[k][j])
    return D


def _dijkstra(D, s, F):
    q = []
    heapq.heappush(q, (0, s))
    while len(q) != 0:
        cost, index = heapq.heappop(q)
        if F[s][index] < cost:
            continue
        for i in range(len(D)):
            if cost + D[index][i] < F[s][i]:
                F[s][i] = cost + D[index][i]
                heapq.heappush(q, (F[s][i], i))
    return F


def Dijkstra(D):
    F = [[inf] * len(D) for _ in range(len(D))]
    for i in range(len(D)):
        F[i][i] = 0
        F = _dijkstra(D, i, F)
    return F



D = Dijkstra(D)


Min = inf
for e in permutations(r):
    s = 0
    for i in range(R - 1):
        s += D[e[i] - 1][e[i + 1] - 1]
    Min = min(s, Min)

print(Min)

Solution (Python):
from itertools import permutations
N,M,R=map(int,input().split())
r = [int(i) for i in input().split()]
inf=10**10

dp=[[[inf]*N for i in range(N)]for i in range(N+1)]
for i in range(M):
    a,b,c=map(int,input().split())
    dp[0][a-1][b-1]=c
    dp[0][b-1][a-1]=c
for k in range(1,N+1):
    for j in range(N):
        for i in range(N):
            dp[k][j][i]=min(dp[k-1][j][i],dp[k-1][j][k-1]+dp[k-1][k-1][i])

ans =inf
for elem in permutations(r, R):
    dis=0
    for i in range(R-1):
        dis+=dp[N][elem[i+1]-1][elem[i]-1]
    ans=min(ans,dis)
print(ans)

Solution (Python):

import itertools
import time

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

ROAD=[None]*M

for i in range(M):
    ROAD[i]=list(map(int,input().split()))




Dis=[None]*(N+1)
for i in range(1,N+1):
    Dis[i]=[100000000]*(N+1)

for i in range(M):
    Dis[ROAD[i][0]][ROAD[i][1]]=ROAD[i][2]
    Dis[ROAD[i][1]][ROAD[i][0]]=ROAD[i][2]





for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(i,N+1):
            length=Dis[i][k]+Dis[j][k]
            if Dis[i][j]>length:
                Dis[i][j]=length
                Dis[j][i]=length


  
PERM=list(itertools.permutations(r))



ANS=float("inf")
for i in range(len(PERM)):
    DIST=0
    for k in range(1,R):
        DIST+=Dis[PERM[i][k]][PERM[i][k-1]]
        if DIST>ANS:
            break
    if ANS>DIST:
        ANS=DIST

print(int(ANS))

Solution (Python):
from itertools import permutations

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
A = [0] * M
B = [0] * M
C = [0] * M
for i in range(M):
	A[i], B[i], C[i] = map(int, input().split())

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

for i in range(M):
	d[A[i] - 1][B[i] - 1] = C[i]
	d[B[i] - 1][A[i] - 1] = C[i]

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]
				d[j][i] = d[i][k] + d[k][j]

p = permutations(r)
ans = float("inf")
for route in p:
	l = 0
	for i in range(R - 1):
		l += d[route[i] - 1][route[i + 1] - 1]

	if l < ans:
		ans = l

print(ans)

Solution (Python):
def warshallfloyd(branch): 
	dist = [[10000000 for i in range(n)]for k in range(n)]
	for i in range(n):
		dist[i][i] = 0
		for k in range(len(branch[i+1])):
			dist[i][branch[i+1][k][0]-1] = branch[i+1][k][1]
	for i in range(n):
		for k in range(n):
			for e in range(n):
				newlength = dist[k][i] + dist[i][e]
				if newlength < dist[k][e]:
					dist[k][e] = newlength
	return dist

import itertools
n,m,r = map(int,input().split())
visit = list(map(int,input().split()))
branch = dict()
for i in range(1,n+1):
	branch[i] = []
for i in range(m):
	a,b,c = map(int,input().split())
	branch[a].append([b,c])
	branch[b].append([a,c])

distance = warshallfloyd(branch)

min = 1000000000
test = list(itertools.permutations(visit))
for i in range(len(test)):
	temp = 0
	for k in range(len(test[i])-1):
		temp += distance[test[i][k]-1][test[i][k+1]-1]
	if temp < min:
		min = temp
print(min)

Solution (Python):
from itertools import permutations

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

    for k in range(N):
        for i in range(N):
            for j in range(N):
                temp = d[i][k] + d[k][j]
                if d[i][j] > temp:
                    d[i][j] = temp

    ans = inf
    for i in permutations(r):
        temp = 0
        for j in range(len(i)-1):
            temp += d[i[j] - 1][i[j + 1] - 1]
            if temp > ans:
                break
        if ans > temp:
            ans = temp

    print(ans)


main()

Solution (Python):
def hoge():
  from itertools import permutations
  N, M, R = map(int, input().split())
  r = map(int, input().split())
  inf = float('inf')
  d = [[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())
      a -= 1
      b -= 1
      t = min(c, d[a][b])
      if d[a][b] > c:
          d[a][b], d[b][a] = t, t


  for k in range(N):
      for i in range(N):
          for j in range(N):
            t = d[i][k] + d[k][j]
            if d[i][j] > t:
              d[i][j] = t


  ans = inf
  for i in permutations(r):
      temp = 0
      for j in range(len(i)-1):
          temp += d[i[j]-1][i[j+1]-1]
          if temp > ans:
              break
      if ans > temp:
        ans = temp
      

  print(ans)
hoge()

Solution (Python):
from itertools import permutations

def input_list():
    return list(map(int, input().split()))

def main():
    n, m, r = input_list()
    rlist = input_list()
    rlist = [r-1 for r in rlist]
    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 = input_list()
        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):
                distance = d[i][k]+d[k][j]
                if d[i][j] > distance:
                    d[i][j] = distance

    ans = float('inf')
    for p in permutations(rlist):
        distance = 0
        for i in range(r-1):
            distance += d[p[i]][p[i+1]]

        if ans > distance:
            ans = distance

    print(ans)

main()

Solution (Python):
import itertools
N,M,R=map(int,input().split())
r=[int(i)-1 for i in input().split()]
P=[set() for i in range(N)]
for i in range(M):
    A,B,C=map(int,input().split())
    P[A-1].add((B-1,C))
    P[B-1].add((A-1,C))
p=[[0 for i in range(R)] for i in range(R)]
def dijkstra(s):
    d=[10**9 for i in range(N)]
    d[s]=0
    Q=set(range(N))
    while(len(Q)>0):
        u=list(Q)[0]
        for v in Q:
            if d[v]<d[u]:
                u=v
        Q-=set([u])
        for v in P[u]:
            if d[v[0]]>d[u]+v[1]:
                d[v[0]]=d[u]+v[1]
    return d
for i in range(R):
    L=dijkstra(r[i])
    for j in range(R):
        p[i][j]=L[r[j]]
S=list(itertools.permutations(range(R),R))
ans=10**9
for sg in S:
    tmp=0
    for i in range(R-1):
        tmp+=p[sg[i]][sg[i+1]]
    if tmp<ans:
        ans=tmp
print(ans)

Solution (Python):
from itertools import permutations
import gc
def read(): return list(map(int, input().split()))
 
 
INF = 114514810
 
 
def wf(d):
    N = len(d[0])
    for k in range(N):
        for i in range(N):
            for j in range(N):
                D = d[i][k] + d[k][j]
                if d[i][j] > D:
                    d[i][j] = D
    return d
 
 
def calc_dist(p, d):
    dist = 0
    for i in range(len(p) - 1):
        if d[p[i]][p[i + 1]] >= INF:
            return INF
        dist += d[p[i]][p[i + 1]]
    return dist
 
 
def main():
    N, M, R = read()
    r = map(lambda x: x - 1, sorted(read()))
    d = [[INF for i in range(N)] for j in range(N)]
 
    for i in range(M):
        a, b, c, = read()
        a -= 1
        b -= 1
        d[a][b] = d[b][a] = c
 
    d = wf(d)
 
    min_dist = INF
    for p in list(permutations(r)):
        min_dist = min(min_dist, calc_dist(p, d))
 
    print(min_dist)
 
 
if __name__ == '__main__':
    gc.disable()
    main()

Solution (Python):
from itertools import permutations
def read(): return list(map(int, input().split()))
 
 
INF = 114514810
 
 
def wf(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
 
 
def calc_dist(p, d):
    dist = 0
    for i in range(len(p) - 1):
        if d[p[i]][p[i + 1]] >= INF:
            return INF
        dist += d[p[i]][p[i + 1]]
    return dist
 
 
def main():
    N, M, R = read()
    r = map(lambda x: x - 1, sorted(read()))
    d = [[INF for i in range(N)] for j in range(N)]
 
    for i in range(M):
        a, b, c, = read()
        a -= 1
        b -= 1
        d[a][b] = d[b][a] = c
 
    d = wf(d)
 
    min_dist = INF
    for p in list(permutations(r)):
        min_dist = min(min_dist, calc_dist(p, d))
 
    print(min_dist)
 
 
if __name__ == '__main__':
    main()

Solution (Python):
from itertools import permutations
from heapq import heappop,heappush
def dijkstra(n,s,adj):
	dis = [float("inf") for i in range(n+1)]
	dis[s],q = 0,[[0,s]]
	while q:
		num2,num = heappop(q)
		for i,j in adj[num]:
			if dis[i]>num2+j:
				dis[i] = num2+j
				heappush(q,[dis[i],i])
	return dis
n,m,r = (int(i) for i in input().split())
rlist = [int(i) for i in input().split()]
x = [[int(i) for i in input().split()] for i in range(m)]
road,y,ans = [[] for i in range(n+1)],[[] for i in range(n+1)],float("inf")
for i,j,k in x:
	road[i].append([j,k])
	road[j].append([i,k])
for i in rlist: y[i] = dijkstra(n,i,road)
for i in permutations(rlist,r):
	num = 0
	for j in range(r-1): num+=y[i[j]][i[j+1]]
	ans = min(num,ans)
print(ans)

Solution (Python):
import heapq
import itertools

def solve():
    N, M, _ = list(map(int, input().split()))
    R = list(map(int, input().split()))
    R = map(lambda x: x-1, R)
    G = [[] for i in range(N)]

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


    def dijkstra(d):
        que = []

        tar = -1
        count = set()
        for i in range(len(d)):
            if d[i] == 1e+16:
                break
            if d[i] == 0:
                tar = i
            heapq.heappush(que, (d[i], i))
            count.add(i)

        checked = [False for i in range(N)]

        while len(que) != 0:
            dist, node = heapq.heappop(que)
            if checked[node]:
                continue
            count.add(node)
            if len(count) == N:
                break

            for (cost, to) in G[node]:
                if d[to] > d[node] + cost:
                    d[to] = d[node] + cost
                    heapq.heappush(que, (dist + cost, to))

            checked[node] = True

        return d


    ds = [[1e16 for i in range(N)] for j in range(N)]

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

    for i in range(N):
        ds[i] = dijkstra(ds[i])
        for j in range(N):
            ds[j][i] = ds[i][j]

    res = 1e16
    for r in list(itertools.permutations(R)):
        d = 0
        for i in range(len(r)-1):
            d += ds[r[i]][r[i+1]]
        res = min(res, d)

    return res

print(solve())

Solution (Python):
import heapq
import itertools

def solve():
    N, M, _ = list(map(int, input().split()))
    R = list(map(int, input().split()))
    R = map(lambda x: x-1, R)
    G = [[] for i in range(N)]

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


    def dijkstra(d):
        que = []

        tar = -1
        count = set()
        for i in range(len(d)):
            if d[i] == 1e+16:
                break
            if d[i] == 0:
                tar = i
            heapq.heappush(que, (d[i], i))
            count.add(i)

        checked = [False for i in range(N)]

        while len(que) != 0:
            dist, node = heapq.heappop(que)
            if checked[node]:
                continue
            count.add(node)
            if len(count) == N:
                break

            for (cost, to) in G[node]:
                if d[to] > d[node] + cost:
                    d[to] = d[node] + cost
                    heapq.heappush(que, (dist + cost, to))

            checked[node] = True

        return d


    ds = [[1e16 for i in range(N)] for j in range(N)]

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

    for i in range(N):
        ds[i] = dijkstra(ds[i])
        for j in range(N):
            ds[j][i] = ds[i][j]

    res = 1e16
    for r in list(itertools.permutations(R)):
        d = 0
        for i in range(len(r)-1):
            d += ds[r[i]][r[i+1]]
        res = min(res, d)

    return res

print(solve())