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

Solution (Python):
import heapq
import itertools
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

N, M, _ = list(map(int, sys.stdin.readline().split()))
R = list(map(int, sys.stdin.readline().split()))
A, B, C = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(M)]))


def dijkstra(graph, start):
    """
    マイナスの辺があっちゃダメ
    scipy.sparse.csgraph.dijkstra は内部で使われてるフィボナッチヒープが一部のケースでめっちゃ遅いのであんまり使わないほうがよさげ
    https://atcoder.jp/contests/soundhound2018-summer-qual/submissions/5311823

    :param list of (list of (int, int)) graph:
        graph[from_index]: (to_index, weight)
    :param int start:
    :return:
    """
    dist = [float('inf') for _ in range(len(graph))]
    dist[start] = 0
    heap = []
    heapq.heappush(heap, (0, start))

    while len(heap) > 0:
        w, v = heapq.heappop(heap)
        if w > dist[v]:
            continue
        for u, dw in graph[v]:
            if w + dw < dist[u]:
                dist[u] = w + dw
                heapq.heappush(heap, (w + dw, u))
    return dist



graph = [[] for _ in range(N + 1)]
for a, b, c in zip(A, B, C):
    graph[a].append((b, c))
    graph[b].append((a, c))

dists = []
for r in R:
    dists.append(dijkstra(graph, r))

ans = INF
for indices in itertools.permutations(range(len(R))):
    s = 0
    for i, j in zip(indices[:-1], indices[1:]):
        s += dists[i][R[j]]
    ans = min(ans, s)
print(ans)

Solution (Python):
from itertools import permutations
from heapq import *

N,M,R=map(int,input().split())
r=list(map(int,input().split()))
INF=float("inf")
G=[[INF]*N for i in range(N)]
for i in range(M):
    A,B,C=map(int,input().split())
    A,B=A-1,B-1
    G[A][B]=C
    G[B][A]=C
def distance(a,b):
    stack=[(G[a][i],i) for i in range(N) if G[a][i]!=INF]
    heapify(stack)
    reached=[0]*N
    reached[0]=1
    dis=[INF]*N
    dis[0]=0
    while(stack):
        c,i=heappop(stack)
        if reached[i]==1:
            continue
        if dis[i]<=c:
            continue
        dis[i]=c
        if i==b:
            return c
        reached[i]=1
        for j in range(N):
            if G[i][j]!=INF and reached[j]==0:
                heappush(stack,(G[i][j]+dis[i],j))
D=[[0]*N for i in range(N)]
for i in r:
    for j in r:
        if i>=j:
            continue
        D[i-1][j-1]=distance(i-1,j-1)
        D[j-1][i-1]=D[i-1][j-1]
ans=10**9
for r_ in permutations(r):
    res=0
    for i in range(R-1):
        res+=D[r_[i]-1][r_[i+1]-1]
    ans=min(ans,res)
print(ans)

Solution (Python):
N,M,R=map(int, input().split())
r=list(map(int, input().split()))
ABC=[list(map(int,input().split())) for i in range(M)]
c=[[10**9]*N for i in range(N)]
for i,j,w in ABC:
    c[i-1][j-1]=w
    c[j-1][i-1]=w
mat=[]
for start in r:
    start-=1
    d=[10**9]*N
    d[start]=0
    prev=[-1]*N
    from heapq import heappop,heappush
    q=[]
    heappush(q,(0,start))
    while len(q)>0:
        u=heappop(q)[1]
        for v in range(N):
            if c[u][v]<10**9:
                temp=d[u]+c[u][v]
                if d[v]>temp:
                    d[v]=temp
                    prev[v]=u
                    heappush(q,(d[v],v))
    m=[]
    for i in range(R):
        m.append(d[r[i]-1])
    mat.append(m)
from itertools import permutations
ans=10**9
for i in permutations(range(R),R):
    a=0
    for j in range(R-1):
        a+=mat[i[j]][i[j+1]]
    ans=min(ans,a)
print(ans)

Solution (Python):
import itertools
def warshall_floyd(d):
    
    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])
    return d

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

inf = 10**9
d = [[inf for i in range(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 i in range(1, N+1):
    d[i][i] = 0 
warshall_floyd(d)
ans = inf
for v in itertools.permutations(rs, R):
    dist = 0
    for i in range(R-1):
        dist += d[v[i]][v[i+1]]
    if dist <= ans:
        ans = dist
print(ans)

Solution (Python):
import sys
import itertools

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

d=[  [ float("inf") for j in range(N+1) ]  for i in range(N+1) ]

r=map(int, sys.stdin.readline().split())

for _ in range(M):
	a,b,c=map(int, sys.stdin.readline().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])


C=list(itertools.permutations(r))


ans=float("inf")
for x in C:
	tmp_ans=0
	for i in range(R-1):
		fro=x[i]
		to=x[i+1]
		tmp_ans+=d[fro][to]
	ans=min(ans, tmp_ans)

print ans

Solution (Python):
import sys
import itertools

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

d=[  [ float("inf") for j in range(N+1) ]  for i in range(N+1) ]

r=map(int, sys.stdin.readline().split())

for _ in range(M):
	a,b,c=map(int, sys.stdin.readline().split())
	d[a][b]=c
	d[b][a]=c


for _ in range(3):
	for i in range(1,N+1):
		for j in range(1,N+1):
			for k in range(1,N+1):
				d[i][j]=min(d[i][j], d[i][k]+d[k][j])


C=list(itertools.permutations(r))


ans=float("inf")
for x in C:
	tmp_ans=0
	for i in range(R-1):
		fro=x[i]
		to=x[i+1]
		tmp_ans+=d[fro][to]
	ans=min(ans, tmp_ans)

print ans

Solution (Python):
import sys
import itertools

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

d=[  [ float("inf") for j in range(N+1) ]  for i in range(N+1) ]
for i in range(N+1):
	d[i][i]=0

r=map(int, sys.stdin.readline().split())

for _ in range(M):
	a,b,c=map(int, sys.stdin.readline().split())
	d[a][b]=c
	d[b][a]=c


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

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


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


C=list(itertools.permutations(r))


ans=float("inf")
for x in C:
	tmp_ans=0
	for i in range(R-1):
		fro=x[i]
		to=x[i+1]
		tmp_ans+=d[fro][to]
	ans=min(ans, tmp_ans)

print ans

Solution (Python):
import itertools
def w_f(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())
LR = map(int,input().split())
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 

D = w_f(d)
lr = list(itertools.permutations(LR))
ans = float("inf")
for li in lr:
    jd = 0
    for i in range(r-1):
        jd += D[li[i]-1][li[i+1]-1]
    
    if jd < ans:
        ans = jd
print(ans)

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

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


edge = np.zeros((N+1,N+1))
for _ in range(M):
  A,B,C = map(int,input().split())
  edge[A,B] = C
  
dist = shortest_path(edge, directed = False).astype(int)


answer = 10**18
for visit in itertools.permutations(r):
  p = 0
  prev = visit[0]
  for x in visit[1:]:
    if prev != None:
      p += dist[prev,x]
    prev = x
  answer = min(answer,p)
  
print(answer)

Solution (Python):
n,m,r = map(int,input().split())
r = list(map(int,input().split()))
node = [list(map(int,input().split())) for _ in range(m)]
dp = [[float('inf')]*(n+1) for _ in range(n+1)]
for x,y,z in node:
    dp[x][y] = z
    dp[y][x] = z
for i in range(n+1):
    dp[i][i] = 0
def wf(d,n):
    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
dp = wf(dp,n+1)
import copy
import sys
rest = set(r[:])
def dfs(cost,pre,rest):
    if 0==len(rest):
        return cost
    ret = sys.maxsize
    for i in rest:
        if pre==None:
            next_cost = 0
        else:
            next_cost = cost + dp[pre][i]
        next_rest = copy.copy(rest)
        next_rest.remove(i)
        tmp_ret = dfs(next_cost, i, next_rest)
        ret = min(ret,tmp_ret)
    return ret
print(dfs(0,None,rest))

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

n,m,l=map(int,input().split())
arr=list(map(int,input().split()))
d=[[10**10 for i in range(n)] for j in range(n)]
for i in range(m):
  u,v,w=map(int,input().split())
  d[u-1][v-1]=w
  d[v-1][u-1]=w
for i in range(n):
  d[i][i]=0
d=floyd_warshall(d,directed=False)
c=list(itertools.permutations(arr,min(8,l)))
ans=10**10
for i in c:
  tmp=0
  for j in range(min(8,l)-1):
    tmp+=d[i[j]-1][i[j+1]-1]
  ans=min(tmp,ans)
print(int(ans))

Solution (Python):
N,M,R = [ int(it) for it in input().split() ]
ri = [ int(it) for it in input().split() ]
edge = [ [ int(it) for it in input().split() ]  for i in range(M) ]

li = [ [10000000]*N for i in range(N) ]
for a,b,c in edge:
  li[a-1][b-1]=c
  li[b-1][a-1]=c

for p in range(10000):
  Flag = True
  for i in range(N):
    for j in range(N):
      for k in range(N):
        li_ikj =  li[i][k]+li[k][j]
        if ( li[i][j] > li_ikj ):
          Flag = False
          li[i][j] = li_ikj
  if Flag:
    break

import itertools as ite
ms = 100000000000000000000000000000000000
for route in ite.permutations( ri ):
  s = 0
  for i in range( len(route)-1 ):
    s += li[route[i]-1][route[i+1]-1]
  ms = min(s,ms)
print ( ms )

Solution (Python):
N, M, R = map(int, input().split())
R_LIST = list(map(int, input().split()))
ABC = []
for _ in range(M):
    a,b,c = map(int, input().split())
    ABC.append((a,b,c))
    

    
edges = ABC[:]


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


graph = [[float("inf") for i in range(N+1)] for i in range(N+1)] 
for x,y,z in edges:
    graph[x][y] = z
    graph[y][x] = z
for i in range(N+1):
    graph[i][i] = 0 


shortest =  warshall_floyd(graph, N+1)
    

import sys
INT_MAX = sys.maxsize 
ans = INT_MAX

import queue

rest = set(R_LIST[:])

import copy  
def dfs(cost,pre,rest):
    if len(rest) == 0:
        return cost
    
    ret = INT_MAX
    for r in rest:
        if pre == None:
            next_cost = 0
        else:
            next_cost = cost + shortest[pre][r]
        next_rest = copy.copy(rest)
        next_rest.remove(r)
        
        tmp_ret = dfs(next_cost, r, next_rest)
        ret = min(ret, tmp_ret)
        
    return ret
        
    

print(dfs(0, None, rest))

Solution (Python):
N, M, R = map(int, input().split())
R_LIST = list(map(int, input().split()))
ABC = []
for _ in range(M):
    a,b,c = map(int, input().split())
    ABC.append((a,b,c))
    

    
edges = ABC[:]


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


graph = [[float("inf") for i in range(N+1)] for i in range(N+1)] 
for x,y,z in edges:
    graph[x][y] = z
    graph[y][x] = z
for i in range(N+1):
    graph[i][i] = 0 


shortest =  warshall_floyd(graph, N+1)
    

import sys
INT_MAX = sys.maxsize 
ans = INT_MAX

import queue

rest = set(R_LIST[:])

import copy  
def dfs(cost,pre,rest):
    if len(rest) == 0:
        return cost
    
    ret = INT_MAX
    for r in rest:
        if pre == None:
            next_cost = 0
        else:
            next_cost = cost + shortest[pre][r]
        next_rest = copy.copy(rest)
        next_rest.remove(r)
        
        tmp_ret = dfs(next_cost, r, next_rest)
        ret = min(ret, tmp_ret)
        
    return ret
        
    

print(dfs(0, None, rest))

Solution (Python):
N, M, R = map(int, input().split())
R_LIST = list(map(int, input().split()))
ABC = []
for _ in range(M):
    a,b,c = map(int, input().split())
    ABC.append((a,b,c))
    
    

    
edges = ABC[:]


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


graph = [[float("inf") for i in range(N+1)] for i in range(N+1)] 
for x,y,z in edges:
    graph[x][y] = z
    graph[y][x] = z
for i in range(N+1):
    graph[i][i] = 0 


shortest =  warshall_floyd(graph, N+1)
    

import sys
INT_MAX = sys.maxsize 
ans = INT_MAX

import queue

rest = set(R_LIST[:])

import copy  
def dfs(cost,pre,rest):
    if len(rest) == 0:
        return cost
    
    ret = INT_MAX
    for r in rest:
        if pre == None:
            next_cost = 0
        else:
            next_cost = cost + shortest[pre][r]
        next_rest = copy.copy(rest)
        next_rest.remove(r)
        
        tmp_ret = dfs(next_cost, r, next_rest)
        ret = min(ret, tmp_ret)
        
    return ret
        
    

print(dfs(0, None, rest))

Solution (Python):
N, M, R = map(int, input().split())
R_LIST = list(map(int, input().split()))
ABC = []
for _ in range(M):
    a,b,c = map(int, input().split())
    ABC.append((a,b,c))
    
    
edges = ABC[:]


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


graph = [[float("inf") for i in range(N+1)] for i in range(N+1)] 
for x,y,z in edges:
    graph[x][y] = z
    graph[y][x] = z
for i in range(N+1):
    graph[i][i] = 0 


shortest =  warshall_floyd(graph, N+1)
    

import sys
INT_MAX = sys.maxsize 
ans = INT_MAX

import queue

rest = set(R_LIST[:])

import copy  
def dfs(cost,pre,rest):
    if len(rest) == 0:
        return cost
    
    ret = INT_MAX
    for r in rest:
        if pre == None:
            next_cost = 0
        else:
            next_cost = cost + shortest[pre][r]
        next_rest = copy.copy(rest)
        next_rest.remove(r)
        
        tmp_ret = dfs(next_cost, r, next_rest)
        ret = min(ret, tmp_ret)
        
    return ret
        
    

print(dfs(0, None, rest))

Solution (Python):
from itertools import permutations
from scipy.sparse.csgraph import floyd_warshall
n,m,r=map(int,input().split())
*R,=map(int,input().split())
table=[[0]*n for i in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    table[a-1][b-1]=c
    table[b-1][a-1]=c
d=floyd_warshall(csgraph=table, directed=False, return_predecessors=False)
cost=[sum(d[i[j]-1][i[j+1]-1]for j in range(r-1))for i in permutations(R)]
print(int(min(cost)))

Solution (Python):
import itertools

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

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

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

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

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

ans = inf

for i in range(r):
    v[i]-=1

s = list(itertools.permutations(v))

for i in range(len(s)):
    a = 0
    for j in range(r-1):
        a += l[s[i][j]][s[i][j+1]]
    ans = min(ans, a)

print(ans)

Solution (Python):
from itertools import permutations

N, M, R = map(int,input().split())
r = [i - 1 for i in map(int,input().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,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):
            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)

Solution (Python):
INF = float('inf')

N,M,RR = map(int,input().split(" "))
R = list(map(lambda x:int(x)-1,input().split(" ")))
G = [[] for i in range(N)]
sq = [[0 for x in range(RR)] for y in range(RR)]
for i in range(M):
    a,b,c = map(int,input().split(" "))
    a -= 1
    b -= 1
    G[a].append((b,c))
    G[b].append((a,c))

for i in range(RR):
    E = [INF]*N
    F = [1]*N
    E[R[i]] = 0
    F[R[i]] = 0
    q = R[i]
    c = 1
    while c != N:
        for a,b in G[q]:
            if F[a]:
                E[a] = min(E[a],E[q] + b)
        a = [x for x in range(N) if F[x]]
        q = min(a,key=lambda x:E[x])
        F[q] = 0
        c += 1
    for j in range(RR):
        sq[i][j] = E[R[j]]

q = [[[],0,0]]
s = []
while len(q):
    a,b,c = q.pop()
    if b == RR:
        s.append(c)
        continue
    for i in range(RR):
        if i in a:
            continue
        d = c
        d += b and sq[a[-1]][i]
        q.append([a+[i],b+1,d])

print(min(s))

Solution (Python):
INF = float('inf')

N,M,RR = map(int,input().split(" "))
R = list(map(lambda x:int(x)-1,input().split(" ")))
G = [[] for i in range(N)]
sq = [[(x==y)-1 for x in range(RR)] for y in range(RR)]
for i in range(M):
    a,b,c = map(int,input().split(" "))
    a -= 1
    b -= 1
    G[a].append((b,c))
    G[b].append((a,c))

for i in range(RR):
    E = [INF]*N
    F = [1]*N
    E[R[i]] = 0
    F[R[i]] = 0
    q = R[i]
    c = 1
    while c != N:
        for a,b in G[q]:
            if F[a]:
                E[a] = min(E[a],E[q] + b)
        a = [x for x in range(N) if F[x]]
        q = min(a,key=lambda x:E[x])
        F[q] = 0
        c += 1
    for j in range(RR):
        sq[i][j] = E[R[j]]

q = [[[],0,0]]
s = []
while len(q):
    a,b,c = q.pop()
    if b == RR:
        s.append(c)
        continue
    for i in range(RR):
        if i in a:
            continue
        d = c
        d += b and sq[a[-1]][i]
        q.append([a+[i],b+1,d])

print(min(s))

Solution (Python):
INF = float('inf')

N,M,RR = map(int,input().split(" "))
R = list(map(lambda x:int(x)-1,input().split(" ")))
G = [[] for i in range(N)]
sq = [[(x==y)-1 for x in range(RR)] for y in range(RR)]
for i in range(M):
    a,b,c = map(int,input().split(" "))
    a -= 1
    b -= 1
    G[a].append((b,c))
    G[b].append((a,c))

for i in range(RR):
    E = [INF]*N
    F = [1]*N
    E[R[i]] = 0
    F[R[i]] = 0
    q = R[i]
    c = 1
    while c != N:
        for a,b in G[q]:
            if F[a]:
                E[a] = min(E[a],E[q] + b)
        a = [x for x in range(N) if F[x]]
        q = min(a,key=lambda x:E[x])
        F[q] = 0
        c += 1
    for j in range(RR):
        sq[i][j] = E[R[j]]

q = [[[],0,0]]
s = []
while len(q):
    a,b,c = q.pop()
    if b == RR:
        s.append(c)
        continue
    for i in range(RR):
        if i in a:
            continue
        d = c
        d += b and sq[a[-1]][i]
        q.append([a+[i],b+1,d])

print(min(s))

Solution (Python):
INF = float('inf')

N,M,RR = map(int,input().split(" "))
R = list(map(lambda x:int(x)-1,input().split(" ")))
G = [[] for i in range(N)]
sq = [[(x==y)-1 for x in range(RR)] for y in range(RR)]
for i in range(M):
    a,b,c = map(int,input().split(" "))
    a -= 1
    b -= 1
    G[a].append((b,c))
    G[b].append((a,c))

for i in range(RR):
    E = [INF for x in range(N)]
    F = [0 for x in range(N)]
    E[R[i]] = 0
    F[R[i]] = 1
    q = R[i]
    c = 1
    while c != N:
        for a,b in G[q]:
            if F[a]:
                continue
            if E[a] == -1:
                E[a] = E[q] + b
            else:
                E[a] = min(E[a],E[q] + b)
        a = [x for x in range(N) if not(F[x]) and E[x] != -1]
        q = min(a,key=lambda x:E[x])
        F[q] = 1
        c += 1
    for j in range(RR):
        sq[i][j] = E[R[j]]

q = [[[],0,0]]
s = []
while len(q):
    a,b,c = q.pop()
    if b == RR:
        s.append(c)
        continue
    for i in range(RR):
        if i in a:
            continue
        if b == 0:
            q.append([a+[i],b+1,0])
        else:
            q.append([a+[i],b+1,c+sq[a[-1]][i]])

print(min(s))

Solution (Python):
N,M,RR = map(int,input().split(" "))
R = list(map(lambda x:int(x)-1,input().split(" ")))
G = [[] for i in range(N)]
sq = [[(x==y)-1 for x in range(RR)] for y in range(RR)]
for i in range(M):
    a,b,c = map(int,input().split(" "))
    a -= 1
    b -= 1
    G[a].append((b,c))
    G[b].append((a,c))

for i in range(RR):
    E = [-1 for x in range(N)]
    F = [0 for x in range(N)]
    E[R[i]] = 0
    F[R[i]] = 1
    q = R[i]
    c = 1
    while c != N:
        for a,b in G[q]:
            if F[a]:
                continue
            if E[a] == -1:
                E[a] = E[q] + b
            else:
                E[a] = min(E[a],E[q] + b)
        a = [x for x in range(N) if not(F[x]) and E[x] != -1]
        q = min(a,key=lambda x:E[x])
        F[q] = 1
        c += 1
    for j in range(RR):
        sq[i][j] = E[R[j]]

q = [[[],0,0]]
s = []
while len(q):
    a,b,c = q.pop()
    if b == RR:
        s.append(c)
        continue
    for i in range(RR):
        if i in a:
            continue
        if b == 0:
            q.append([a+[i],b+1,0])
        else:
            q.append([a+[i],b+1,c+sq[a[-1]][i]])

print(min(s))

Solution (Python):
from itertools import permutations

N, M, R = (int(i) for i in input().split())


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


dist=[[float('inf') for i in range(201)] for j in range(201)]
for i in range(201):
    dist[i][i] = 0

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

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

dict0=float('inf')
mylist=list(permutations(r,len(r)))


for i in mylist:
  tmp=0
  for j in range(len(i)-1):
    tmp+=dist[i[j]][i[j+1]]
  if tmp < dict0:
    dict0=tmp

print(dict0)

Solution (Python):
from itertools import permutations

N, M, R = (int(i) for i in input().split())


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


dist=[[float('inf') for i in range(201)] for j in range(201)]
for i in range(201):
    dist[i][i] = 0

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

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

dict0=float('inf')
mylist=list(permutations(r,len(r)))


for i in range(len(mylist)):
    tmp=0
    for j in range(len(mylist[i])-1):
        x=mylist[i][j]
        y=mylist[i][j+1]
        tmp+=dist[x][y]
    if tmp < dict0:
      dict0=tmp

print(dict0)

Solution (Python):
import heapq

N,M,R = map(int,input().split())
r = list(map(int,input().split()))
r = [a-1 for a in r]
paper = set()
T = [[] for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    T[a].append((c,b))
    T[b].append((c,a))

inf = 1 << 60
memo = {}
def distance(a,b):
    
    if (a,b) in memo.keys():
        
        return memo[(a,b)]
    d = [inf] * N
    d[a] = 0
    q = []
    heapq.heappush(q, (0,a))
    try:
        while True:
            c, t = heapq.heappop(q)
            if t == b:
                memo[(a,b)] = c
                memo[(b,a)] = c
                
                return c
            for i in T[t]:
                if d[i[1]] > c + i[0]:
                    d[i[1]] = c + i[0]
                    heapq.heappush(q, (c + i[0], i[1]))

    except IndexError:
        pass

arrived = [False] * R
ans = inf

def calc(src, rest, total):
    global ans
    if total >= ans:
        return
    if rest == 0:
        ans = min(ans,total)
        return

    for i in range(R):
        if not arrived[i]:
            arrived[i] = True
            calc(r[i], rest-1, total + distance(src,r[i]))
            arrived[i] = False

for i in range(R):
    arrived[i] = True
    calc(r[i], R-1, 0)
    arrived[i] = False

print(ans)

Solution (Python):


import itertools
from scipy.sparse import csr_matrix, coo_matrix
from scipy.sparse.csgraph import dijkstra, bellman_ford


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

rows = []
cols = []
weights = []

for _ in range(M):
    
    u, v, a = [int(i) for i in input().split()]
    rows.append(u-1)
    cols.append(v-1)
    weights.append(a)

graph = coo_matrix((weights, (rows, cols)), shape=(N, N)).tocsr()
d1 = dijkstra(graph, directed=False, unweighted=False)

ans = float("inf")
for i in list(itertools.permutations(r)):
    dist = 0
    for j in range(R-1):
        dist += d1[i[j]-1][i[j+1]-1]
    ans = min(ans, dist)

print(int(ans))

Solution (Python):
import itertools as o,scipy.sparse as s;_,r,*t=[map(int,i.split())for i in open(0)];a,b,c=zip(*t);l=s.csgraph.dijkstra(s.csr_matrix((c,(a,b)),[201]*2),0);print(min(sum(int(l[i][j])for i,j in zip(a,a[1:]))for a in o.permutations(r)))

Solution (Python):
from itertools import*
from scipy.sparse.csgraph import floyd_warshall
n,m,r=map(int,input().split())
*R,=map(int,input().split())

table=[[0]*n for i in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    table[a-1][b-1]=c
    table[b-1][a-1]=c
d,p=floyd_warshall(csgraph=table, directed=False, return_predecessors=True)
cost=[sum(d[i[j]-1][i[j+1]-1]for j in range(r-1))for i in permutations(R)]
print(int(min(cost)))

Solution (Python):
from itertools import product, permutations

INF=1145141919810

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

road=[[0 if x==y else INF for y in range(N+1)] for x in range(N+1)]

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

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

print(min(sum(road[p[i-1]][p[i]] for i in range(1, R)) for p in permutations(r)))

Solution (Python):
from itertools import product, permutations

INF=1145141919810

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

road=[[0 if x==y else INF for y in range(N+1)] for x in range(N+1)]

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

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

print(min(sum(road[p[i-1]][p[i]] for i in range(1, R)) for p in permutations(r)))

Solution (Python):
import itertools
N, M, R = map(int, input().split())
INF = 2 ** 63 - 1
d = [[INF for i in range(N+1)] for j in range(N+1)]
r = list(map(int, input().split()))
r = list(itertools.permutations(r))
for i in range(M):
    a, b, c = map(int, input().split())
    d[a][b] = c
    d[b][a] = c
for i in range(N+1):
    d[i][i] = 0


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

ans = INF
for path in r:
    anstemp = 0
    for i in range(R-1):
        anstemp += d[path[i]][path[i+1]]
    ans = min(anstemp, ans)
print(ans)

Solution (Python):
import heapq

N,M,R = map(int,input().split())
r = list(map(int,input().split()))
r = [a-1 for a in r]
paper = set()
T = [[] for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    T[a].append((c,b))
    T[b].append((c,a))

inf = 1 << 60
memo = {}
def distance(a,b):
    
    if (a,b) in memo.keys():
        
        return memo[(a,b)]
    d = [inf] * N
    d[a] = 0
    q = []
    heapq.heappush(q, (0,a))
    try:
        while True:
            c, t = heapq.heappop(q)
            if t == b:
                memo[(a,b)] = c
                memo[(b,a)] = c
                
                return c
            for i in T[t]:
                if d[i[1]] > c + i[0]:
                    d[i[1]] = c + i[0]
                    heapq.heappush(q, (c + i[0], i[1]))

    except IndexError:
        pass

arrived = [False] * R
ans = inf

def calc(src, rest, total):
    global ans
    if total >= ans:
        return
    if rest == 0:
        ans = min(ans,total)
        return

    for i in range(R):
        if not arrived[i]:
            arrived[i] = True
            calc(r[i], rest-1, total + distance(src,r[i]))
            arrived[i] = False

for i in range(R):
    arrived[i] = True
    calc(r[i], R-1, 0)
    arrived[i] = False

print(ans)

Solution (Python):
from itertools import permutations
n,m,rl=map(int,input().split());r=list(map(int,input().split()))
d=[[float("inf")for _ in range(n)]for _ in range(n)]
for i in range(m):
  x,y,z=map(int,input().split())
  d[x-1][y-1],d[y-1][x-1]=z,z
for i in range(n):d[i][i]=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])
a=float("inf")
for i in permutations(r,rl):
  aa=0
  for j in range(rl-1):aa+=d[i[j]-1][i[j+1]-1]
  a=min(a,aa)
print(a)

Solution (Python):
import itertools

N,M,R = map(int,input().split())
r = list(map(lambda x:int(x)-1,input().split()))
ABC = [list(map(int,input().split())) for _ in range(M)]
INF = 10**7
d = [[INF]*N for _ in range(N)]

for A,B,C in ABC:
    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(i+1,N):
            d[i][j] = min(d[i][j],d[i][k]+d[k][j])
            d[j][i] = d[i][j]
ans = INF * M
for r in itertools.permutations(r):
    S = 0
    for i,ri in enumerate(r[:-1]):
        S += d[ri][r[i+1]]
    ans = min(ans,S)
print(ans)