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

Solution (Python):
class Digraph:
    
    def __init__(self,vertex=[]):
        self.vertex=set(vertex)

        self.edge_number=0
        self.vertex_number=len(vertex)

        self.adjacent_out={v:{} for v in vertex} 
        self.adjacent_in={v:{} for v in vertex} 

    
    def add_vertex(self,*adder):
        for v in adder:
            if v not in self.vertex:
                self.adjacent_in[v]={}
                self.adjacent_out[v]={}

                self.vertex_number+=1
                self.vertex.add(v)

    
    def add_edge(self,From,To,weight=1):
        for v in [From,To]:
            if v not in self.vertex:
                self.add_vertex(v)

        if To not in self.adjacent_in[From]:
            self.edge_number+=1

        self.adjacent_out[From][To]=weight
        self.adjacent_in[To][From]=weight

    
    def remove_edge(self,From,To):
        for v in [From,To]:
            if v not in self.vertex:
                self.add_vertex(v)

        if To in self.adjacent_out[From]:
            del self.adjacent_out[From][To]
            del self.adjacent_in[To][From]
            self.edge_number-=1

    
    def remove_vertex(self,*vertexes):
        for  v in vertexes:
            if v in self.vertex:
                self.vertex_number-=1

                for u in self.adjacent_out[v]:
                    del self.adjacent_in[u][v]
                    self.edge_number-=1
                del self.adjacent_out[v]

                for u in self.adjacent_in[v]:
                    del self.adjacent_out[u][v]
                    self.edge_number-=1
                del self.adjacent_in[v]

    
    def add_walk(self,*walk):
        pass

    
    def add_cycle(self,*cycle):
        pass

    
    def __vertex_swap(self,p,q):
        self.vertex.sort()

    
    def vertex_exist(self,v):
        return v in self.vertex

    
    def edge_exist(self,From,To):
        if not(self.vertex_exist(From) and self.vertex_exist(To)):
            return False
        return To in self.adjacent_out[From]

    
    def neighbohood(self,v):
        if not self.vertex_exist(v):
            return []
        return list(self.adjacent[v])

    
    def out_degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent_out[v])

    
    def in_degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent_in[v])

    
    def degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return self.out_degree(v)-self.in_degree(v)

    
    def vertex_count(self):
        return len(self.vertex)

    
    def edge_count(self):
        return self.edge_number

    
    def connected_component(self,v):
        pass


def Warshall_Floyd(D):
    """Warshall–Floyd法を用いて,全点間距離を求める.

    D:負Cycleを含まない有向グラフ
    """
    T={v:{} for v in D.vertex} 
    for u in D.vertex:
        for v in D.vertex:
            if v==u:
                T[u][v]=0
            elif v in D.adjacent_out[u]:
                T[u][v]=D.adjacent_out[u][v]
            else:
                T[u][v]=float("inf")

    for u in D.vertex:
        for v in D.vertex:
            for w in D.vertex:
                T[v][w]=min(T[v][w],T[v][u]+T[u][w])

    return T

from itertools import permutations
N,M,R=map(int,input().split())
Y=list(map(int,input().split()))
D=Digraph(list(range(1,N+1)))
for _ in range(M):
    a,b,c=map(int,input().split())
    D.add_edge(a,b,c)
    D.add_edge(b,a,c)

Dist=Warshall_Floyd(D)

Z=float("inf")
for P in permutations(Y):
    X=0
    for i in range(R-1):
        X+=Dist[P[i]][P[i+1]]
    Z=min(Z,X)
print(Z)

Solution (Python):
n,m,r = map(int, input().split())
INF = 1 << 40
edges = [[INF]*n for i in range(n)]
rs  = list(map(int, input().split()))
rs = [r-1 for r in rs]
for i in range(m):
    a,b,c = map(int, input().split())
    a -= 1
    b -= 1
    edges[a][b] = c
    edges[b][a] = c

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

from itertools import permutations

ans = 1 << 50
for perm in permutations(rs):
    dist = 0
    for i in range(1,len(perm)):
        f = perm[i-1]
        t = perm[i]
        dist += edges[f][t]
    ans = min(ans, dist)
print(ans)

Solution (Python):
"""ABC073D joisino's travel
"""
from itertools import permutations
N,M,R=map(int, input().split())
r = list(map(lambda x: int(x)-1, input().split()))
INF = float("inf")
D = [[INF]*(N) for _ in range(N)]
for _ in range(M):
    a,b,c=map(int, input().split())
    D[a-1][b-1]=c
    D[b-1][a-1]=c
    
def warshall_floyd(adj_mat: list):
    """
    ワーシャルフロイド
    隣接行列を受け取る(隣接していないノードはINF、自身へのコストは0)
    全点の間の最短距離をあらわす行列を返す(V * V)
    O(|V|**3)
    ネスト深くならないバージョン
    """
    V = len(adj_mat)
    for k in range(V): 
        for i in range(V): 
            for j in range(V): 
                adj_mat[i][j] = min(
                    adj_mat[i][j],
                    adj_mat[i][k] + adj_mat[k][j]
                )
    return adj_mat
D = warshall_floyd(D)
ans = INF
for tpl in permutations(r, len(r)):
    tmp = 0
    for i in range(len(tpl)-1):
        tmp += D[tpl[i]][tpl[i+1]]
    ans = min(ans, tmp)
print(ans)

Solution (Python):
import sys
import math
from collections import defaultdict
from collections import deque
from itertools import permutations

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    N, M, R = NMI()
    targets = NLI()
    targets = [t-1 for t in targets]
    dist = [[10**9] * N for _ in range(N)]
    for _ in range(M):
        a, b, c = NMI()
        dist[a-1][b-1] = c
        dist[b-1][a-1] = c
    for i in range(N):
        dist[i][i] = 0

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

    ans = 10**9
    for case in permutations(targets, R):
        now = case[0]
        cost = 0
        for goto in case[1:]:
            cost += dist[now][goto]
            now = goto
        ans = min(ans, cost)
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
from itertools import*
n,m,r=map(int,input().split())
rc=list(map(int,input().split()))
INF=10**18
d=[[INF]*n for _ in range(n)]
for _ in range(m):
  a,b,c=map(int,input().split())
  d[a-1][b-1]=c
  d[b-1][a-1]=c
for k in range(n):
  for i in range(n):
    for j in range(n):
      d[i][j]=min(d[i][j],d[i][k]+d[k][j])
ans=INF
for i in permutations(rc):
  a=0
  i=list(i)
  for j in range(r-1):
    a+=d[i[j]-1][i[j+1]-1]
  ans=min(a,ans)
print(ans)

Solution (Python):
from itertools import permutations
N, M, R = map(int, input().split())
r = [int(i)-1 for i in input().split()]
inf = float("inf")
mat = [[inf]*N for _ in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    if mat[a-1][b-1] > c:
        mat[a-1][b-1] = mat[b-1][a-1] = c

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


ans = inf
for p in list(permutations(r)):
    dist = 0
    for i in range(1, len(p)):
        dist += mat[p[i]][p[i-1]]
    ans = min(ans, dist)

print(ans)

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

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

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
d = [[10**18]*N for _ in range(N)]

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

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

warshall_floyd()
ans = 10**18

for p in permutations(r):
    now = p[0]-1
    cand = 0

    for i in range(1, R):
        cand += d[now][p[i]-1]
        now = p[i]-1

    ans = min(ans, cand)

print(ans)

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



d = [[10**9 for _ in range(N)] for _ in range(N)]


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


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


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

ans = 10**9


for p in itertools.permutations(r_list):
    tmp = 0
    for i in range(R - 1):
        x = p[i] - 1
        y = p[i + 1] - 1
        tmp += d[x][y]
    ans = min(ans, tmp)

print(ans)

Solution (Python):
n,m,R=list(map(int,input().split()))
r=list(map(int,input().split()))
dp=[[float("INF")]*n for i in range(n)]
for i in range(m):
  a,b,c=list(map(int,input().split()))
  dp[a-1][b-1]=c
  dp[b-1][a-1]=c
for i in range(n):
  dp[i][i]=0
for k in range(n):
  for i in range(n):
    for j in range(n):
      dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
from itertools import permutations
per=list(permutations(r,R))
ans=float("INF")
for tup in per:
  ans_kouho=0
  for i in range(R-1):
    ans_kouho=ans_kouho+dp[tup[i]-1][tup[i+1]-1]
  ans=min(ans,ans_kouho)
print(ans)

Solution (Python):
from collections import deque
INF = 10**12+7
N,M,R = map(int,input().split())
r = list(map(str,input().split()))
d = [[INF]*(N+1) for _ in range(N+1)]
for _ 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
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
que = deque([])
for i in r:
    que.append([i])
while len(que) != 0:
    p = que.popleft()
    if len(p) == R:
        
        val = 0
        for i in range(1,R):
            val += d[ int(p[i-1])][int(p[i])]
        ans = min(ans,val)
    else:
        for i in r:
            if not i in p:
                que.append(p+[i])
print(ans)

Solution (Python):
from collections import deque
import itertools
INF = 10**12+7
N,M,R = map(int,input().split())
r = list(map(int,input().split()))
d = [[INF]*(N+1) for _ in range(N+1)]
for _ 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
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 i in itertools.permutations(r,len(r)):
    val = 0
    for j in range(1,len(r)):
        val += d[i[j-1]][i[j]]
    ans = min(ans,val)
print(ans)

Solution (Python):
N, M, r = map(int, input().split())
R = list(map(lambda x:int(x)-1, input().split()))
d = [[1<<30]*N for _ in range(N)]
for i in range(M): 
  a,b,t = map(int, input().split())
  d[a-1][b-1] = t
  d[b-1][a-1] = t

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])
from itertools import groupby, accumulate, product, permutations, combinations
ans = 1<<30
for per in permutations(R,r):
  cnt = 0
  for i in range(r-1):
    cnt += d[per[i]][per[i+1]]
  ans = min(ans, cnt)
print(ans)

Solution (Python):
import itertools

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

dis = [[float("inf") for i in range(n)] for j in range(n)]
for i in range(n):
    dis[i][i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    dis[a-1][b-1] = c
    dis[b-1][a-1] = c

def warshall_floyd(dis):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
    return dis

data = warshall_floyd(dis)
ans = float("inf")
for i in itertools.permutations(r, R):
    num = 0
    for j in range(R - 1):
        num += data[i[j] - 1][i[j + 1] - 1]
    ans = min(ans, num)
print(ans)

Solution (Python):
from itertools import *
from scipy.sparse.csgraph import *
import numpy as np
N,M,R = map(int,input().split())
T = list(map(int,input().split()))
E = [list(map(int,input().split())) for m in range(M)]
G = np.zeros((N,N))
A = []

for a,b,c in E:
  G[a-1][b-1] = c
  G[b-1][a-1] = c

F = floyd_warshall(G)

for P in permutations(T):
  A+=[sum(F[P[r]-1][P[r+1]-1] for r in range(R-1))]

print(int(min(A)))

Solution (Python):
from itertools import permutations
n_node, n_edge, R = map(int,input().split())
r_ls = list(map(int,input().split()))
for i in range(R):
    r_ls[i] -= 1
ad_mat = [[float('inf')]*n_node for _ in range(n_node)]
for i in range(n_node):
    ad_mat[i][i] = 0
for i in range(n_edge):
    a,b,c = map(int,input().split())
    ad_mat[a-1][b-1] = c
    ad_mat[b-1][a-1] = c


for stop in range(n_node):
    for start in range(n_node):
        for end in range(n_node):
            ad_mat[start][end] = min(ad_mat[start][end],ad_mat[start][stop]+ad_mat[stop][end])

ans = float('inf')
for path in permutations(r_ls):
    cost = 0
    for i in range(R-1):
        cost += ad_mat[path[i]][path[i+1]]
    ans = min(ans,cost)
print(ans)

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

dist = [[10e8 for _ in range(N)] for _ in range(N)]
for i in range(N): dist[i][i] = 0
for _ in range(M):
    a, b, c = (int(x) for x in input().split())
    dist[a-1][b-1] = dist[b-1][a-1] = c 
del a, b, c, K

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

def mindist(x, X):
    global dist
    Y = X.copy()
    Y.remove(x)
    if len(Y) == 0: return 0
    return min([dist[x][y] + mindist(y,Y) for y in Y])

ans = min([mindist(r, R) for r in R])
print(ans)

Solution (Python):
N,M,R = map(int,input().split())
R = list(map(int,input().split()))
ABC = [tuple(map(int,input().split())) for i in range(M)]

INF = float('inf')
d = [[INF]*N for _ in range(N)]
for i in range(N):
    d[i][i] = 0
for a,b,c in ABC:
    a,b = a-1,b-1
    d[a][b] = d[b][a] = c

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

ans = INF
import itertools
for ptn in itertools.permutations(R):
    tmp = 0
    for a,b in zip(ptn,ptn[1:]):
        tmp += d[a-1][b-1]
    ans = min(ans, tmp)
print(ans)

Solution (Python):
from collections import deque
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
import itertools

n, m, r = map(int,input().split())
rlist = list(map(int,input().split()))
for i in range(r):
    rlist[i] -= 1
e = np.zeros((n,n), dtype=int)

for i in range(m):
    a, b, c = map(int,input().split())
    a -= 1
    b -= 1
    e[a][b] = c
    e[b][a] = c
csr = csr_matrix(e)
f = floyd_warshall(csr)

ans = 10**18
for v in itertools.permutations(rlist,r):
    d = 0
    for i in range(r-1):
        d += f[v[i]][v[i+1]]
    ans = min(ans, d)
print(int(ans))

Solution (Python):

import sys 
from itertools import permutations
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
INF = 10**31

N, M, R = map(int, readline().split())
r = list(map(int,readline().split()))
len_r = len(r)
cost = [[INF]*(N+1) for i in range(N+1)]

for i in range(M):
    s, t, d = map(int,readline().split())
    cost[s][t] = d
    cost[t][s] = d
  
for i in range(N+1):
    cost[i][i] = 0

for k in range(N+1):
    for i in range(N+1):
        for j in range(N+1):
            if cost[i][k] != INF and cost[k][j] != INF: 
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])

ans = INF
for A in permutations(r,len_r):
    total = 0
    for i in range(len_r-1):
        s = A[i]
        t = A[i+1]        
        total += cost[s][t]
    ans = min(total,ans)
print(ans)

Solution (Python):
from itertools import permutations
n,m,r=map(int, input().split())
r_l=[int(i)-1 for i in input().split()]
town = [[float("INF")]*n for _ in range(n)]
for i in range(m):
    a,b,c=map(int, input().split())
    town[a-1][b-1]=c
    town[b-1][a-1]=c

for k in range(n):
    for i in range(n):
        for j in range(n):
            town[i][j] = min(town[i][j],town[i][k]+town[k][j])
res = float("INF")
for root in list(permutations(r_l)):
    tmp = 0
    for i in range(1,r):
        tmp += town[root[i]][root[i-1]]
    res = min(tmp,res)

print(res)

Solution (Python):
import itertools
N, M, R = map(int, input().split())
r = list(map(lambda x:int(x)-1, input().split()))
graph = [[] for _ in range(N)]
d = [[float('inf')]*N for _ in range(N)]
for _ in range(M):
  a, b, c = map(int, input().split())
  a -= 1
  b -= 1
  graph[a] += [[b, c]]
  graph[b] += [[c, a]]
  d[a][b] = c
  d[b][a] = c

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

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

d = warshall_floyd(d)
ans = float('inf')
for v in itertools.permutations(r):
  tmp = 0
  for i in range(len(v)-1):
    tmp += d[v[i]][v[i+1]]
  ans = min(ans, tmp)
print(ans)

Solution (Python):
INF = 10**10

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

dp = [[INF]*(N+1) for i in range(N+1)]
for i in range(N+1):
    dp[i][i]=0

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

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

ans = INF
import itertools
for it in itertools.permutations(r):
    tmpans = 0
    for i in range(1,R):
        tmpans+=dp[it[i-1]][it[i]]
    ans = min(ans,tmpans)
print(ans)

Solution (Python):
'''
自宅用PCでの解答
'''
import math

import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n,m,r = map(int,ipt().split())
    tgt = [int(i)-1 for i in ipt().split()]
    dt = [[10**18]*n for i in range(n)]
    for i in range(n):
        dt[i][i] = 0
    for i in range(m):
        a,b,c = map(int,ipt().split())
        a -= 1
        b -= 1
        dt[a][b] = c
        dt[b][a] = c

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

    mi = 10**18
    for i in itertools.permutations(range(r)):
        nm = 0
        for j in range(r-1):
            nm += dt[tgt[i[j]]][tgt[i[j+1]]]
        if mi > nm:
            mi = nm

    print(mi)

    return None

if __name__ == '__main__':
    main()

Solution (Python):
import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict, OrderedDict


input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  
  
from functools import lru_cache






n,m,r=map(int,input().split())
R=[i-1 for i in list(map(int,input().split()))]
G=[[] for i in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    a-=1;b-=1
    G[a].append([c,b])
    G[b].append([c,a])  


def dijkstra(s):
    dist=[inf for i in range(n)] 
    dist[s]=0
    mirai=[True for i in range(n)] 
    mirai[s]=False

    queue=[] 
    for kyori,to in G[s]:
        heapq.heappush(queue , kyori*10**6+to)  
    while queue:
        minedge= heapq.heappop(queue)
        
        if not mirai[minedge%(10**6)]: continue
        
        v=minedge%(10**6) 
        dist[v] = minedge//(10**6) 
        mirai[v]=False
        for kyori,to in G[v]:
            if mirai[to]:
                heapq.heappush(queue, (kyori+dist[v])*(10**6)+to)
                
    return dist


from itertools import permutations as per
ans=inf
P=[dijkstra(i) for i in range(n)]
for l in per(R):
    now=0
    for i in range(r-1):
        now+=P[l[i]][l[i+1]]
    ans=min(ans,now)

print(ans)

Solution (Python):
import itertools
def warshall_floyd():
    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])
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
d = [[float('inf') if i != j else 0 for j in range(N+1)]for i in range(N+1)]

for m in range(M):
    A, B, C = map(int, input().split())
    d[A][B] = C
    d[B][A] = C
warshall_floyd()
ans = float('inf')
for p in itertools.permutations(r):
    tmp = 0
    for i in range(len(p)-1):
        tmp += d[p[i]][p[i+1]]
    ans = min(tmp, ans)
print(ans)

Solution (Python):
from itertools import permutations
N,M,R = map(int,input().split())
RList = list(map(int,input().split()))
dp = [[float("INF")]*(N+1) for _ in range(N+1)]
for i in range(N+1):
    dp[i][i] = 0
for _ in range(M):
    a,b,c = map(int,input().split())
    dp[a][b] = c
    dp[b][a] = c

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

ans = float("INF")
RList = list(permutations(RList))
for Rs in RList:
    tmp = 0
    for i in range(1,R):
        a = Rs[i-1]
        b = Rs[i]
        tmp += dp[a][b]
    ans = min(ans,tmp)
print(ans)

Solution (Python):

import sys

def solve(N: int, M: int, R: int, r: "List[int]", A: "List[int]", B: "List[int]", C: "List[int]"):
    from scipy.sparse import coo_matrix    
    from scipy.sparse.csgraph import floyd_warshall
    from itertools import permutations
    from functools import reduce
    
    mat = floyd_warshall(coo_matrix((C, (A, B)), shape=(N+1, N+1)).tocsr(), directed=False)
    f = lambda a, b: (a[0]+mat[a[1]][b], b)
    return int(min(reduce(f, q, (0, s))[0] for s, *q in permutations(r)))


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

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    
    main()

Solution (Python):

import sys

def solve(N: int, M: int, R: int, r: "List[int]", A: "List[int]", B: "List[int]", C: "List[int]"):
    import numpy as np    
    from scipy.sparse import coo_matrix    
    from scipy.sparse.csgraph import floyd_warshall
    from itertools import permutations, islice
    from functools import reduce
    
    mat = floyd_warshall(coo_matrix((C, (A, B)), shape=(N+1, N+1), dtype=np.int32).tocsr(), directed=False)
    f = lambda a, b: (a[0]+mat[a[1]][b], b)
    return int(min(reduce(f, q, (0, s))[0] for s, *q in permutations(r)))


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

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    
    main()

Solution (Python):
import itertools
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
N, M, R = map(int, input().split())
r = [int(i) for i in input().split()]

G = [[10**8]*(N+1) for _ in range(N+1)]
for _ in range(M):
    A, B, C = map(int, input().split())
    G[A][B] = C
    G[B][A] = C

DG = csgraph_from_dense(G, null_value=10**8)
d = floyd_warshall(DG)

ans = 10**8
for route in itertools.permutations(r):
    c = 0
    for i in range(len(route)-1):
        c += d[route[i]][route[i+1]]
    ans = min(ans, c)
print(int(ans))

Solution (Python):
import heapq
from itertools import permutations
n, m, r = map(int, input().split())
R = list(map(lambda x: int(x)-1, input().split()))
edges = [[]for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append((c, b))
    edges[b].append((c, a))


def dijkstra(init_v):
    next_v = [(0, init_v)]
    INF = 10**18
    dist = [INF]*n
    dist[init_v] = 0
    while next_v:
        d, v = heapq.heappop(next_v)
        if dist[v] < d:
            continue
        for d, v2 in edges[v]:
            if dist[v2] <= dist[v]+d:
                continue
            dist[v2] = dist[v]+d
            heapq.heappush(next_v, (dist[v2], v2))
    return dist


dists = []
for x in R:
    dist = dijkstra(x)
    dists.append(dist)

INF = 10**18
ans = INF
for subset in permutations(range(r)):
    d = 0
    for v, v2 in zip(subset, subset[1:]):
        d += dists[v][R[v2]]
    if d < ans:
        ans = d

print(ans)

Solution (Python):
from itertools import permutations
n, m, r = map(int, input().split())
R = list(map(lambda x: int(x)-1, input().split()))
INF = 10**18
dist = [[INF]*n for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    dist[a-1][b-1] = c
    dist[b-1][a-1] = c

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

ans = INF
for subset in permutations(R):
    d = 0
    for v, v2 in zip(subset, subset[1:]):
        d += dist[v][v2]
    if d < ans:
        ans = d
print(ans)

Solution (Python):
from itertools import permutations

def warshall_floyd(A, INF=10**20):
    d = [[INF for i in range(len(A))] for j in range(len(A))]
    for i in range(len(A)):
        d[i][i] = 0
        for j in A[i].keys():
          d[i][j] = A[i][j]

    for k in range(len(A)):
        for i in range(len(A)):
            for j in range(len(A)):
                d[i][j] = min(d[i][j], d[i][k]+d[k][j])
    
    return d
  
N,M,R=map(int,input().split())
r = list(map(int,input().split()))
r2 = []
for i in range(len(r)):
  r2.append(r[i]-1)
r = r2
G=[{} for _ in range(N)]
for i in range(M):
  a,b,c=map(int,input().split())
  a -= 1
  b -= 1
  G[a][b] = G[b][a] = c

d = warshall_floyd(G)

if R==2:
  print(d[r[0]][r[1]])
  exit()
  
ans = 10**20
for p in permutations(r):
  dist=0
  for i in range(R-1):
    dist += d[p[i]][p[i+1]]
  ans = min(ans,dist)
  
print(ans)

Solution (Python):
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
import itertools
I = [int(_) for _ in open(0).read().split()]
N, M, R = I[:3]
r = np.array(I[3:3 + R])
ABC = I[3 + R:]
F = floyd_warshall(csr_matrix((ABC[2::3], (ABC[::3], ABC[1::3])), (N + 1, N + 1)), 0).astype(np.int64)
ans = float('inf')
for root in itertools.permutations(r, R):
    ans = min(ans, sum(F[i,j] for i, j in zip(root, root[1:])))
print(ans)

Solution (Python):
from itertools import permutations

def warshall_floyd():
    '''
    すべての頂点間の最短距離を求める (重み付き有向グラフ)
    '''
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    return dist


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

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

warshall_floyd()

res = float('inf')
for l in permutations(range(r), r):
    d = 0
    for i in range(r-1):
        d += dist[city[l[i]]-1][city[l[i+1]]-1]
    res = min(res, d)

print(res)

Solution (Python):
from itertools import permutations
n,m,r = map(int,input().split())
route = list(map(int,input().split()))

dp = [[0 for _ in range(n)] for _ in range(n)]
INF = 10**18
for i in range(n):
    for j in range(n):
        if i!=j:
            dp[i][j] = INF
for _ in range(m):
    a,b,c = map(int,input().split())
    dp[a-1][b-1] = c
    dp[b-1][a-1] = c



for chu in range(n):
    for fir in range(n):
        for la in range(n):
            dp[fir][la] = min(dp[fir][la] , dp[fir][chu] +  dp[chu][la])

ans = 10**10
for j in permutations(route, r):
    a = 0
    for q,w in zip(j[:-1], j[1:]):
        a += dp[q-1][w-1]
        
    ans = min(ans,a)
print(ans)

Solution (Python):
import heapq
from itertools import permutations
n, m, r = map(int, input().split())
R = list(map(lambda x: int(x)-1, input().split()))
edges = [[]for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append((c, b))
    edges[b].append((c, a))


def dijkstra(init_v):
    next_v = [(0, init_v)]
    INF = 10**18
    dist = [INF]*n
    dist[init_v] = 0
    while next_v:
        d, v = heapq.heappop(next_v)
        if dist[v] < d:
            continue
        for d, v2 in edges[v]:
            if dist[v2] <= dist[v]+d:
                continue
            dist[v2] = dist[v]+d
            heapq.heappush(next_v, (dist[v2], v2))
    return dist


dists = []
for x in R:
    dist = dijkstra(x)
    dists.append(dist)

INF = 10**18
ans = INF
for subset in permutations(range(r)):
    d = 0
    for v, v2 in zip(subset, subset[1:]):
        d += dists[v][R[v2]]
    if d < ans:
        ans = d

print(ans)