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

Solution (Python):
n,m,r=map(int,input().split())
r=list(map(int,input().split()))
r=[t-1 for t in r]
abc=[list(map(int,input().split())) for _ in range(m)]
d=[[2**30 for _ in range(n)] for _ in range(n)]
for t in abc:
    d[t[0]-1][t[1]-1]=t[2]
    d[t[1]-1][t[0]-1]=t[2]
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
res=[]
for t in permutations(r):
    ans=0
    for i in range(1,len(r)):
        ans+=d[t[i-1]][t[i]]
    res.append(ans)
print(min(res))

Solution (Python):
from scipy.sparse.csgraph import floyd_warshall as fw
import numpy as np
N,M,R = map(int,input().split())
r = list(map(int,input().split()))
edge = [[np.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())
    edge[A][B] = C
    edge[B][A] = C
cost = fw(edge)
cd = {}
for r_ in r:
    cd[r_] = {}
for r_ in r:
    for r__ in r:
        cd[r_][r__] = cost[r_][r__]
import itertools
ans = np.inf
for rp in itertools.permutations(r):
    c = 0
    for i in range(R-1):
        c += cd[rp[i]][rp[i+1]]
    if c < ans:
        ans = c
print(int(ans))

Solution (Python):
import itertools
import heapq
N, M, R = map(int, input().split())
Visit = [int(i) for i in input().split()]
for i in range(R):
    Visit[i] -= 1
P = [[] for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    P[a-1].append((c, b-1))
    P[b-1].append((c, a-1))

def Dijk(i):
    Fin = [False for i in range(N)]
    Cost = [float("inf") for i in range(N)]
    Cost[i] = 0
    Q = [(0, i)]
    heapq.heapify(Q)
    while Q:
        cost, node = heapq.heappop(Q)
        if Fin[node] == False:
            Fin[node] = True
            for next in P[node]:
                if Fin[next[1]] == False:
                    if next[0] + cost < Cost[next[1]]:
                        Cost[next[1]] = next[0] + cost
                        heapq.heappush(Q, (Cost[next[1]], next[1]))
    return Cost

E = []
for i in range(N):
    E.append(Dijk(i))

ans = float("inf")
for Order in itertools.permutations(Visit):
    temp = 0
    for i in range(R-1):
        temp += E[Order[i]][Order[i+1]]
    if temp < ans:
        ans = temp
print(ans)

Solution (Python):
import itertools

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

d = [[1 << 60 for j in range(N)] for i in range(N)]
for i in range(M):
    a, b, c = [int(i) for i in 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 = 1 << 60
for plan in itertools.permutations(rr):
    cnt = 0
    for i in range(R - 1):
        cnt += d[plan[i] - 1][plan[i + 1] - 1]
    ans = min(ans, cnt)

print(ans)

Solution (Python):
from itertools import permutations
from scipy.sparse import csgraph, csr_matrix
N, M, R = map(int, input().split())
r = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(M)]
a, b, c = zip(*edges)
graph = csgraph.dijkstra(csr_matrix((c, (a, b)), shape=(N + 1, N + 1)),
                         directed=False)
ans = 10 ** 18
for p in permutations(r):
    ans = min(ans, sum(int(graph[i][j]) for i, j in zip(p, p[1:])))
print(ans)

Solution (Python):
def ABC073D():
    N, M, R = map(int, input().split())
    r = list(map(int, input().split()))
    ABC = [list(map(int, input().split())) for i in range(M)]
    root = [[1000000000 for i in range(N)] for j in range(N)]
    for i, j, k in ABC:
        root[i - 1][j - 1] = k
        root[j - 1][i - 1] = k

    import itertools
    def kumiawase(list_name):  
        return itertools.permutations(list_name)


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

    a = kumiawase(r)
    ans = float("inf")
    for i in a:
        key = 0
        for j in range(len(i) - 1):
            key += root[i[j] - 1][i[j + 1] - 1]
        if ans > key:
            ans = int(key)
    
    print(ans)
ABC073D()

Solution (Python):

"""
Created on Sun Oct  7 22:06:12 2018
ABC073D
@author: maezawa
"""
import itertools as itr
import sys
input = sys.stdin.readline

def wf(graph):
    """ Warshall-Floyd Algorithm """
    for k in range(len(adjmatrix)):
        for i in range(len(adjmatrix)):
            for j in range(len(adjmatrix[i])):
                if adjmatrix[i][j] > adjmatrix[i][k] + adjmatrix[k][j]:
                    adjmatrix[i][j] = adjmatrix[i][k] + adjmatrix[k][j]
                    adjmatrix[j][i] = adjmatrix[i][k] + adjmatrix[k][j]				
    

n, m, r = list(map(int, input().split()))
rarray = list(map(int, input().split()))
adjmatrix = [[float("inf")]*n for _ in range(n)]



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




wf(adjmatrix)
        

    

mincnt = float("inf")
for route in itr.permutations(rarray):
    cnt = 0
    for i in range(len(route)-1):
        cnt += adjmatrix[route[i]-1][route[i+1]-1]
    if cnt < mincnt:
        mincnt = cnt

print(mincnt)

Solution (Python):

"""
Created on Sun Oct  7 22:06:12 2018
ABC073D
@author: maezawa
"""
import itertools as itr
import sys
input = sys.stdin.readline

def wf(graph):
    """ Warshall-Floyd Algorithm """
    for k in range(len(adjmatrix)):
        for i in range(len(adjmatrix)):
            for j in range(len(adjmatrix[i])):
                if adjmatrix[i][j] > adjmatrix[i][k] + adjmatrix[k][j]:
                    adjmatrix[i][j] = adjmatrix[i][k] + adjmatrix[k][j]
                    adjmatrix[j][i] = adjmatrix[i][k] + adjmatrix[k][j]				
    return graph

n, m, r = list(map(int, input().split()))
rarray = list(map(int, input().split()))
adjmatrix = [[float("inf")]*n for _ in range(n)]



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



costmatrix = wf(adjmatrix)
        

    

mincnt = float("inf")
for route in itr.permutations(rarray):
    cnt = 0
    for i in range(len(route)-1):
        cnt += costmatrix[route[i]-1][route[i+1]-1]
    if cnt < mincnt:
        mincnt = cnt

print(mincnt)

Solution (Python):

"""
Created on Mon Oct  8 10:17:39 2018

@author: maezawa
"""

from itertools import permutations


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

"""
Created on Mon Oct  8 10:17:39 2018

@author: maezawa
"""

import math
from itertools import permutations


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

INF = float('inf')
graph = [[INF for i in range(N)] for j in range(N)]
for i in range(M):
    A, B, C = map(int, input().split())
    graph[A-1][B-1] = C
    graph[B-1][A-1] = C

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

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

ans = 10**9
for p in permutations(r, len(r)):
    dist = 0
    flag = 0
    for i in range(len(r) - 1):
        if graph[p[i]-1][p[i+1]-1] == INF:
            flag = 1
            continue
        dist += graph[p[i]-1][p[i+1]-1]
    if flag == 0:
        ans = min(ans, dist)

print(ans)

Solution (Python):
from itertools import permutations

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

INF = float('inf')
graph = [[INF for i in range(N)] for j in range(N)]
for i in range(M):
    A, B, C = map(int, input().split())
    graph[A-1][B-1] = C
    graph[B-1][A-1] = C

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

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

ans = 10**9
for p in permutations(r, len(r)):
    dist = 0
    flag = 0
    for i in range(len(r) - 1):
        if graph[p[i]-1][p[i+1]-1] == INF:
            flag = 1
            continue
        dist += graph[p[i]-1][p[i+1]-1]
    if flag == 0:
        ans = min(ans, dist)

print(ans)

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

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import permutations
from heapq import heappush, heappop

def dijkstra(graph:list, node:int, start:int) -> list:
    
    INF = float("inf")
    dist = [INF]*node
    
    
    dist[start] = 0
    heap = [(0,start)]
    searched = [False for _ in range(node)]
    
    
    while heap:
        cost, cur_node = heappop(heap)
        
        if searched[cur_node] or cost > dist[cur_node]:
            continue
        
        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heappush(heap, (dist[nex_node], nex_node))
    
        searched[cur_node] = True
        
        if sum(searched) == node:
            break
    
    return dist

n,m,r = li()
r = list(li_())
graph = [[] for _ in range(n)]
for _ in range(m):
    a,b,c = li()
    a -= 1
    b -= 1
    graph[a].append((c,b))
    graph[b].append((c,a))
    
dists = []
for i in range(n):
    dists.append(dijkstra(graph, n, i))

ans = 2**64-1
for route in permutations(r):
    temp = 0
    for i in range(len(route)-1):
        temp += dists[route[i]][route[i+1]]
        
    ans = min(ans,temp)
    
print(ans)

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

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import permutations
from heapq import heappush, heappop

def dijkstra(graph:list, node:int, start:int) -> list:
    
    INF = float("inf")
    dist = [INF]*node
    
    
    dist[start] = 0
    heap = [(0,start)]
    searched = [False for _ in range(node)]
    
    
    while heap:
        cost, cur_node = heappop(heap)
        
        if searched[cur_node] or cost > dist[cur_node]:
            continue
        
        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heappush(heap, (dist[nex_node], nex_node))
    
        searched[cur_node] = True
        
        if sum(searched) == node:
            break
    
    return dist

n,m,r = li()
r = list(li_())
graph = [[] for _ in range(n)]
for _ in range(m):
    a,b,c = li()
    a -= 1
    b -= 1
    graph[a].append((c,b))
    graph[b].append((c,a))
    
dists = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    dists[i] = dijkstra(graph, n, i)

routes = list(permutations(r))

ans = 2**64-1
for route in routes:
    temp = 0
    for i in range(len(route)-1):
        temp += dists[route[i]][route[i+1]]
        
    ans = min(ans,temp)
    
print(ans)

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

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import permutations
from scipy.sparse.csgraph import floyd_warshall
import numpy as np

n,m,r = li()
r = list(li_())
abc = []
graph = np.zeros((n,n))
for _ in range(m):
    a,b,c = li()
    a -= 1
    b -= 1
    graph[a][b] = c
    graph[b][a] = c
    
floyd_warshall(graph, directed=False, overwrite=True)

routes = list(permutations(r))

ans = float("inf")
for route in routes:
    cand = 0
    for i in range(len(route)-1):
        cand += graph[route[i]][route[i+1]]
        
    ans = min(ans, cand)
        
print(int(ans))

Solution (Python):
import itertools
N,M,R = map(int,input().split())
towns = list(map(lambda x:int(x)-1,input().split()))
INF = float('inf')
es = [[INF]*N for i in range(N)]
for i in range(N):
    es[i][i] = 0
for i in range(M):
    a,b,c = map(int,input().split())
    a,b = a-1,b-1
    es[a][b] = es[b][a] = c

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

ans = INF
for ptn in itertools.permutations(range(R)):
    tmp = 0
    for a,b in zip(ptn, ptn[1:]):
        t1,t2 = towns[a],towns[b]
        tmp += es[t1][t2]
    ans = min(ans, tmp)
print(ans)

Solution (Python):


import itertools

INF = float('inf')


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


def dijkstra(graph, start):
    MAX_SIZE = len(graph)
    visited = [False for _ in range(MAX_SIZE)]
    cost = [INF for _ in range(MAX_SIZE)]
    prev = [None for _ in range(MAX_SIZE)]

    cost[start] = 0
    prev[start] = start
    path = [start + 1]
    while True:
        min_cost = INF
        next = -1
        visited[start] = True
        
        for i in range(MAX_SIZE):
            if visited[i]: continue  
            if graph[start][i]:  
                dist = cost[start] + graph[start][i]
                if dist < cost[i]:
                    cost[i] = dist
                    prev[i] = start

            if cost[i] < min_cost:
                min_cost = cost[i]
                next = i

        start = next
        path.append(next + 1)
        if next == -1: break

    
    
    return cost


def main():
    N, M, R = inpl()
    r = inpl()

    G = [[None for _ in range(N)] for _ in range(N)]
    for i in range(M):
        a, b, c = inpl()
        G[a - 1][b - 1] = c
        G[b - 1][a - 1] = c

    min_cost = {}
    for s in r:
        min_cost[str(s)] = dijkstra(G, s - 1)

    ans = INF
    for root in itertools.permutations(r, R):
        dist = 0
        for i in range(R - 1):
            s = str(root[i])
            dist += min_cost[s][root[i + 1] - 1]
        ans = min(ans, dist)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

import itertools

N, M, R = map(int,input().split())
s = list(map(int,input().split()))
D = [[10**9+7 for k in range(N)] for l in range(N)]
for k in range(N):
    D[k][k] = 0
for k in range(M):
    A, B, C = map(int,input().split())
    A -= 1
    B -= 1
    D[A][B] = C
    D[B][A] = C

for p in range(N):
    for q in range(N):
        for r in range(N):
            D[q][r] = min(D[q][r], D[q][p]+D[p][r])

cities = list(itertools.permutations(s))
ans = 10**9+7
for p in cities:
    t = 0
    for k in range(R-1):
        t += D[p[k]-1][p[k+1]-1]
    ans = min(ans,t)

print(ans)

Solution (Python):
fn = lambda: map(int, 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

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
from itertools import permutations

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

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

Solution (Python):
import sys
from itertools import permutations

from scipy.sparse.csgraph import floyd_warshall

input = sys.stdin.readline

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

g = [[float('inf')] * N for _ in range(N)]
for i in range(M):
    A, B, C = map(int, input().split())
    g[A - 1][B - 1] = C
    g[B - 1][A - 1] = C

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

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

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

d = [[float('inf')] * N for _ in range(N)]
for i in range(N):
    d[i][i] = 0
for _ in range(M):
    A, B, C = map(int, input().split())
    d[A - 1][B - 1] = C
    d[B - 1][A - 1] = C



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

c = [[d[dest[i] - 1][dest[j] - 1] for j in range(R)] for i in range(R)]

dp_memo = [[float('inf')] * R for _ in range(1 << R)]

def TSP(T, v):
    

    if dp_memo[T][v] != float('inf'):
        return dp_memo[T][v]

    elif T == (1 << R) - 1 :
        
        dp_memo[T][v] = 0
        return 0
    else:
        res = float('inf')
        for u in range(R):
            if (T >> u) & 1 == 0:
                res = min(res, TSP(T | (1 << u), u) + c[v][u])
        dp_memo[T][v] = res
        return res

ans = float('inf')
for i in  range(R):
    ans = min(ans, TSP(0, i))
print(ans)

Solution (Python):
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, factorial
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


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

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

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

    for m in range(N):
        for s in range(N):
            for e in range(N):
                if matrix[s][m] != INF and matrix[m][e] != INF:
                    matrix[s][e] = min(matrix[s][e], matrix[s][m] + matrix[m][e])

    ans = INF
    for r in permutations(R):
        tmp = 0
        for i in range(len(r) - 1):
            tmp += matrix[r[i]][r[i + 1]]
        ans = min(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import permutations
N,M,R = map(int,input().split())
r = list(map(int,input().split()))

d = [[float('inf') for _ in range(N)] for _ in range(N)]
for _ in range(M):
    a,b,c = map(int,input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
for i in range(N):
    d[i][i]=0
from scipy.sparse import csgraph
d = csgraph.floyd_warshall(d)
ans = float('inf')
for seq in permutations(r):
    s = 0
    for j in range(R-1):
        s += d[seq[j]-1][seq[j+1]-1]
    ans = min(ans,s)
print(int(ans))

Solution (Python):
from itertools import permutations
import heapq

INF = float('inf')
n, m, R = list(map(int, input().split()))
r = list(map(int, input().split()))

cost = {}
for i in range(m):
    a, b, c = list(map(int, input().split()))
    if not a in cost.keys():
        cost[a] = [(b, c)]
    else:
        cost[a].append((b, c))
    if not b in cost.keys():
        cost[b] = [(a, c)]
    else:
        cost[b].append((a, c))
        
dist = [[INF]*(n+1) for _ in range(n+1)]
for st in r:
    d = [INF]*(n+1)
    d[st] = 0
    path = [(0, st)]
    heapq.heapify(path)
    while len(path) > 0:
        c, node = heapq.heappop(path)
        if d[node] < c:
            continue
        d[node] = c
        for node_next, c_next in cost[node]:
            if d[node_next] < INF:
                continue
            heapq.heappush(path, (d[node]+c_next, node_next))
    dist[st] = d


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

Solution (Python):
from itertools import permutations
import heapq

INF = float('inf')
n, m, R = list(map(int, input().split()))
r = list(map(int, input().split()))

cost = {}
for i in range(m):
    a, b, c = list(map(int, input().split()))
    if not a in cost.keys():
        cost[a] = [(b, c)]
    else:
        cost[a].append((b, c))
    if not b in cost.keys():
        cost[b] = [(a, c)]
    else:
        cost[b].append((a, c))
        
dist = [[INF]*(n+1) for _ in range(n+1)]
for st in r:
    d = [INF]*(n+1)
    d[st] = 0
    path = [(0, st)]
    heapq.heapify(path)
    while len(path) > 0:
        c, node = heapq.heappop(path)
        if d[node] < c:
            continue
        d[node] = c
        for node_next, c_next in cost[node]:
            if d[node]+c_next < d[node_next]:
                heapq.heappush(path, (d[node]+c_next, node_next))
    dist[st] = d


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

Solution (Python):
from itertools import permutations

INF = float('inf')
n, m, R = list(map(int, input().split()))
r = list(map(int, input().split()))
dist = [[INF]*(n+1) for _ in range(n+1)]
for i in range(1, n+1):
    dist[i][i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    dist[a][b] = c
    dist[b][a] = c

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






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

Solution (Python):
from itertools import permutations as p
N,M,R=map(int,input().split())
r=map(int,input().split())
inf=float("inf")
l=[[inf if i!=j else 0 for i in range(N)] for j in range(N)]

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

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

Solution (Python):
"""
atcoder workspace
"""
from itertools import permutations

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

Dmat = [[1e9] * N for i in range(N)]

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

for i in range(M):
    f, t, c = map(int, input().split())
    Dmat[f-1][t-1] = c
    Dmat[t-1][f-1] = c

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

ans = 1e9
for p in permutations(Rlist):
    ans = min(ans, sum([Dmat[p[i]-1][p[i+1]-1] for i in range(R-1)]))

print(ans)

Solution (Python):
def d_joisino_travel(N, M, R, Route, Road):
    
    
    
    
    
    from itertools import permutations
    from scipy.sparse import csgraph

    graph = [[float('inf')] * N for j in range(N)]  
    for i in range(N):
        graph[i][i] = 0
    for m, n, c in Road:
        graph[m - 1][n - 1] = c
        graph[n - 1][m - 1] = c
    dist = csgraph.floyd_warshall(graph)

    ans = float('inf')
    for route in permutations([x - 1 for x in Route]):
        cost = 0
        for j in range(R - 1):  
            cost += dist[route[j]][route[j + 1]]
        ans = min(ans, cost)
    return int(ans)

N, M, R = [int(i) for i in input().split()]
Route = [int(i) for i in input().split()]
Road = [[int(i) for i in input().split()] for j in range(M)]
print(d_joisino_travel(N, M, R, Route, Road))

Solution (Python):
import itertools
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())
    G[a - 1][b - 1] = c
    G[b - 1][a - 1] = c

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

num = INF
for per in itertools.permutations(r):
    rec = 0
    pre = per[0] - 1
    for j in range(1, len(r)):
        rec += G[pre][per[j] - 1]
        pre = per[j] - 1
        if rec > num:
            break

    num = min(rec, num)

print(num)

Solution (Python):
INF = int(1e9)
N, M, K = list(map(int, input().split()))
R = list(map(lambda x: int(x) - 1, input().split()))

G = [[INF] * N for i in range(N)]
for i in range(N):
    G[i][i] = 0
            
for i in range(M):
    a, b, c = list(map(int, input().split()))
    a = a - 1
    b = b - 1
    G[a][b] = G[b][a] = c
    
ls = range(N)
for k in ls:
    for i in ls:
        for j in range(i+1,N):
            x = G[i][k] + G[k][j]
            if x < G[i][j]:
                G[i][j] = G[j][i] = x

dp = [[INF] * (1<<K) for i in range(K)]
for i in range(K):
    dp[i][1<<i] = 0

for bit in range(1<<K):
    for pre in range(K):
        if (bit >> pre) & 1 == 0:
            continue
        for to in range(K):
            if (bit >> to) & 1 == 1:
                continue
            cost = dp[pre][bit] + G[R[pre]][R[to]]
            nbit = bit | (1<<to)
            if dp[to][nbit] > cost:
                dp[to][nbit] = cost

ans = INF     
for pre in range(K):
    ans = min(ans, dp[pre][(1<<K) - 1])
print (ans)

Solution (Python):
import itertools
def Warshall_Floyd(edges,N):
  for k in range(N):
    for i in range(N):
      for j in range(N):
        edges[i][j]=min(edges[i][j],edges[i][k]+edges[k][j])
  return edges
n,m,r = map(int,input().split())
a = list(map(int,input().split()))
b = [list(map(int,input().split())) for l in range(m)]
d = [[float("inf")]*n for i in range(n)]
for i in range(m):
  d[b[i][0]-1][b[i][1]-1] = min(b[i][2],d[b[i][0]-1][b[i][1]-1])
  d[b[i][1]-1][b[i][0]-1] = min(b[i][2],d[b[i][1]-1][b[i][0]-1])
d = Warshall_Floyd(d,n)
kumi = list(itertools.permutations(a, r))
kota = float("inf")
for i in kumi:
  ans = 0
  for j in range(1,r):
    ans += d[i[j-1]-1][i[j]-1]
  kota = min(ans,kota)
print(kota)

Solution (Python):
from itertools import permutations, product
from collections import defaultdict
from heapq import heappop, heappush

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


class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


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

        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0
        self.prev = defaultdict(lambda: None)

        Q = []
        heappush(Q, (self.dist[start], start))

        while Q:
            dist_u, u = heappop(Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(Q, (alt, v))

    def shortest_distance(self, goal):
        return self.dist[goal]

    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


g = Graph()
for a, b, c in abc:
    g.add_edge(a - 1, b - 1, c)
    g.add_edge(b - 1, a - 1, c)

D = dict()
for ri in r:
    D[ri - 1] = Dijkstra(g, ri - 1)

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(D[s].shortest_distance(g))
    ans = min(ans, d)
print(ans)