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 sys
import numpy as np
from itertools import permutations as  P
from operator import itemgetter
from scipy.sparse.csgraph import floyd_warshall as wf

input = sys.stdin.readline

N, M, R = map(int, input().split())
r = list(map(int,input().split()))
edges = [list(map(int,input().split())) for _ in range(M)]
edges.sort(key=itemgetter(2),reverse=True)

G = np.full((N, N), np.inf)
for a, b, c in edges:
    G[a-1, b-1] = c
    G[b-1, a-1] = c
G = wf(G,directed=False)

def cost(G, path):
    ret = 0
    for i in range(len(path) - 1):
        ret += G[path[i] - 1, path[i + 1] - 1]
    return ret

ans = np.inf
for path in P(r):
    ans = min(ans, cost(G, path))

print(int(ans))

Solution (Python):
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
abcs = [list(map(int, input().split())) for i in range(M)]
INF = 10**9
dist_list = [[INF if i != j else 0 for j in range(N)] for i in range(N)]


for abc in abcs:
    a = abc[0]-1
    b = abc[1]-1
    c = abc[2]
    if c < dist_list[a][b]:
        dist_list[a][b] = c
        dist_list[b][a] = c

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


result = []


def permutation(data, res):
    global result
    if len(data) == 0:
        result.append(res)
        return

    for i in data:
        _res = res[::]
        _res.append(i)
        _data = data[::]
        _data.remove(i)
        permutation(_data, _res)


permutation(r, [])
min_distance = INF
for res in result:
    distance = 0
    for i in range(1, len(res)):
        x = res[i]-1
        y = res[i-1]-1
        distance += dist_list[x][y]
    if distance < min_distance:
        min_distance = distance
print(min_distance)

Solution (Python):
import sys
from heapq import heappush, heappop
from collections import deque
from itertools import permutations
input = sys.stdin.readline

def dijkstra(N, start, adj_dict):
    distance = [float('inf')] * N
    distance[start] = 0
    priority_queue = []
    
    for i in range(N):
        heappush(priority_queue, (distance[i], i))
        
    while len(priority_queue) > 0:
        (current_dist, current_node) = heappop(priority_queue)
        if distance[current_node] < current_dist:
            continue
        for next_node, w in adj_dict[current_node]:
            if distance[next_node] >= distance[current_node] + w:
                distance[next_node] = distance[current_node] + w
                heappush(priority_queue, (distance[next_node], next_node))
    
    return distance

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
adj_dict = {i: deque([]) for i in range(N)}

for _ in range(M):
    a_i, b_i, c_i = map(int, input().split())
    adj_dict[a_i-1].append((b_i-1, c_i))
    adj_dict[b_i-1].append((a_i-1, c_i))

distance_map = [dijkstra(N, start, adj_dict) for start in range(N)]
ans = 1000000000

for route in permutations(r):
    ans_cand = 0
    
    for i in range(len(route)-1):
        ans_cand += distance_map[route[i]-1][route[i+1]-1]
    
    ans = min([ans, ans_cand])

print(ans)

Solution (Python):
import sys
from heapq import heappush, heappop
from collections import deque
from itertools import permutations
input = sys.stdin.readline

def dijkstra(N, start, adj_dict):
    distance = [float('inf')] * N
    distance[start] = 0
    priority_queue = []
    
    for i in range(N):
        heappush(priority_queue, (distance[i], i))
        
    while len(priority_queue) > 0:
        (current_dist, current_node) = heappop(priority_queue)
        if distance[current_node] < current_dist:
            continue
        for next_node, w in adj_dict[current_node]:
            if distance[next_node] >= distance[current_node] + w:
                distance[next_node] = distance[current_node] + w
                heappush(priority_queue, (distance[next_node], next_node))
    
    return distance

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
adj_dict = {i: deque([]) for i in range(N)}

for _ in range(M):
    a_i, b_i, c_i = map(int, input().split())
    adj_dict[a_i-1].append((b_i-1, c_i))
    adj_dict[b_i-1].append((a_i-1, c_i))

distance_map = [dijkstra(N, start, adj_dict) for start in range(N)]
ans = 1000000000

for route in permutations(r):
    ans_cand = 0
    
    for i in range(len(route)-1):
        ans_cand += distance_map[route[i]-1][route[i+1]-1]
    
    ans = min([ans, ans_cand])

print(ans)

Solution (Python):
from itertools import permutations
N,M,R=map(int,input().split())
INF=10**9
d=[[INF]*N for i in range(N)]
r=list(map(int,input().split()))
for i in range(M):
  A,B,C=map(int,input().split())
  d[A-1][B-1]=C
  d[B-1][A-1]=C
for k in range(N):
  for i in range(N):
    for j in range(N):
      d[i][j]=min(d[i][j],d[i][k]+d[k][j])
ans=10**9
for L in permutations(r):
  temp=0
  for j in range(R-1):
    temp+=d[L[j]-1][L[j+1]-1]
  ans=min(temp,ans)
print(ans)

Solution (Python):
N, M, R = map(int, input().split())
T = list(map(int, input().split()))
D = [[float('INF')] * N for _ in range(N)]
V = [False] * R
for _ in range(M):
    A, B, C = map(int, input().split())
    A -= 1
    B -= 1
    if D[A][B] > C:
        D[A][B] = C
        D[B][A] = C
ans = float('INF')


def dfs(c, s, d):
    global ans
    if c == R + 1:
        if ans > d:
            ans = d
            return

    for i in range(R):
        if V[i] is True:
            continue
        V[i] = True
        if s == -1:
            dfs(c + 1, i, 0)
        else:
            dfs(c + 1, i, d + D[T[s] - 1][T[i] - 1])
        V[i] = False


def main():
    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])
    dfs(1, -1, 0)
    print(ans)


main()

Solution (Python):
n, m, R = list(map(int, input().split()))
dist = [[float("INF") if i!=j else 0 for i in range(n)] for j in range(n)]
r = list(map(int, input().split()))
for i in range(m):
  a, b, c = list(map(int, input().split()))
  a, b = a-1, b-1
  dist[a][b] = c
  dist[b][a] = c
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])

from itertools import permutations
ans = float("INF")
for e in permutations(r):
  cur = 0
  for i in range(R-1):
    cur += dist[e[i]-1][e[i+1]-1]
  ans = min(ans, cur)
print(ans)

Solution (Python):


inf = float('inf')

n, m, r = map(int, input().split())
rs = [r-1 for r in list(map(int, input().split()))]


ds = [[inf] * n for _ in range(n)]
for i in range(n):
  ds[i][i] = 0

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


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


















import itertools
dds = []
for i in itertools.permutations(rs, len(rs)):
  d = 0
  for j in range(len(rs)-1):
    dd = ds[i[j]][i[j+1]]
    d += dd
    
  dds.append(d)
print(min(dds))

Solution (Python):
from collections import defaultdict
import itertools

def main():
    node_num, edge_num, visit_num = map(int, input().split())
    visit_place = list(map(int, input().split()))
    data = [list(map(int, input().split())) for i in range(edge_num)]

    hashi_set = defaultdict(set)
    kyori_data = [defaultdict(int) for i in range(node_num + 1)]

    saitan_data = [[10 ** 10 for i in range(node_num + 1)] for j in range(node_num + 1)]

    for i in range(edge_num):
        a, b, c = data[i]
        hashi_set[a].add(b)
        hashi_set[b].add(a)
        kyori_data[a][b] = c
        kyori_data[b][a] = c
        saitan_data[a][b] = c
        saitan_data[b][a] = c


    for k in range(1, node_num + 1):
        for i in range(1, node_num + 1):
            for j in range(1, node_num + 1):
                if i == j:
                    saitan_data[i][j] = 0
                    continue
                saitan_data[i][j] = min(saitan_data[i][j], saitan_data[i][k] + saitan_data[k][j])

    ans = 10 ** 10
    for ikikata in list(itertools.permutations(visit_place, visit_num)):
        kari = 0
        for i in range(visit_num - 1):
            kari += saitan_data[ikikata[i]][ikikata[i + 1]]
        if kari < ans:
            ans = kari
    print(ans)





if __name__ == '__main__':
    main()

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

class Route:
    def __init__(self, B, C):
        self.next = points[B]
        self.distance = C
class Point:
    def __init__(self, id):
        self.id = id
        self.neighbors = []
        self.clear()
    def clear(self):
        self.distances = [-1] * 2
    def set(self, cur):
        self.distances[cur.srcid] = cur.distance
        return self.isWent(0) and self.isWent(1)
    def isWent(self, n):
        return self.distances[n] >= 0
    def addNeighbor(self, B, C):
        self.neighbors.append(Route(B, C))
    def optimize(self):
        self.neighbors = sorted(self.neighbors, key=lambda obj:obj.distance)

class MeetInfo:
    def __init__(self):
        self.clear()
    def clear(self):
        self.distance = -1
    def isMet(self):
        return self.distance >= 0

class Cursor:
    def __init__(self, ri, pt, meetinfo, dist=0):
        self.srcid = ri
        self.point = pt
        self.cur_route = 0
        self.distance = dist
        self.meetinfo = meetinfo
        if self.point.set(self):
            meetinfo.distance = self.point.distances[0] + self.point.distances[1]

    def cost(self):
        while self.cur_route < len(self.point.neighbors):
            rt = self.point.neighbors[self.cur_route]
            if not rt.next.isWent(self.srcid):
                break
            self.cur_route+= 1
        else:
            return None

        return self.distance + rt.distance

    def progress(self):
        nextrt = self.point.neighbors[self.cur_route]
        addcursor(Cursor(self.srcid, nextrt.next, self.meetinfo, self.distance + nextrt.distance))
        self.cur_route += 1
        addcursor(self)
    def __lt__(self, other):
        return True
points = [Point(i) for i in range(N+1)]

in_r = [ri for ri in map(int, input().split())]
for A, B, C in (map(int, input().split()) for _ in range(M)):
    points[A].addNeighbor(B, C)
    points[B].addNeighbor(A, C)

for x in points:
    x.optimize()

def addcursor(cur):
    c = cur.cost()
    if not c is None:
        heapq.heappush(hq, (c, cur))

def getRs(rs = None, cnt = -1, ret = None):
    if rs is None:
        rs = [False] * R
        ret = []
        cnt = R

    if cnt <= 0:
        yield ret
        return

    cnt -= 1

    for i in range(R):
        if not rs[i]:
            rs[i] = True
            ret.append(i)
            yield from getRs(rs, cnt, ret)
            ret.pop()
            rs[i] = False

Rmatrix = [[-1 for _ in range(R)] for _ in range(R) ]

for i in range(R):
    for j in range(R):
        if i >= j:
            continue

        meetinfo = MeetInfo()
        for x in points:
            x.clear()
        rs = [Cursor(i, points[ri], meetinfo)  for i, ri in enumerate((in_r[i], in_r[j]))]
        hq = []
        addcursor(rs[0])

        while not meetinfo.isMet():
            cost, cursor = heapq.heappop(hq)
            cursor.progress()

        Rmatrix[i][j] = meetinfo.distance
        Rmatrix[j][i] = meetinfo.distance

M = 10 ** 9
for r in getRs():
    
    w = 0
    for i in range(R-1):
        w += Rmatrix[r[i]][r[i+1]]    
    M = min(M, w)

print(M)

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

n, m, r = [ int(v) for v in input().split() ]
town_list = [ int(v)-1 for v in input().split() ]

road_matrix = [ [ 10**9 for j in range(n) ] for i in range(n) ]


for i in range(m):
	s, e, d = [ int(v) - 1 for v in input().split() ]
	road_matrix[s][e] = d + 1
	road_matrix[e][s] = d + 1


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


mindist = 10**9
for i in itertools.permutations(town_list,r):
	dist = 0
	for j in range(r-1):
		dist += road_matrix[i[j]][i[j+1]]

	mindist = min(mindist,dist)
print(mindist)

Solution (Python):
from itertools import permutations
from scipy.sparse.csgraph import dijkstra as di
N,M,R=map(int,input().split())
r=list(map(int,input().split()))
dp=[[0 for _ in range(N)] for _ in range(N)]
 
for _ in range(M):
  A,B,C=map(int,input().split())
  if dp[A-1][B-1]==0 or dp[A-1][B-1]>C:
    dp[A-1][B-1]=C
    dp[B-1][A-1]=C
distance=di(dp)
'''
def get_target_min_index(min_index, distance, unsearched_nodes):
    start = 0
    while True:
        index = distance.index(min_index, start)
        found = index in unsearched_nodes
        if found:
            return index
        else:
            start = index + 1
 
 
distance = [[100001]*N] * N 
 
 
for i in range(R):
  for j in range(i+1,R):
    dist=[100001]*N
    dist[r[i]]=0
    unsearched_nodes = list(range(N)) 
    previous_nodes = [-1] * N 
    while(len(unsearched_nodes) != 0): 
    
      posible_min_distance = 100001 
      for node_index in unsearched_nodes: 
          if posible_min_distance > dist[node_index]: 
              posible_min_distance = dist[node_index] 
      target_min_index = get_target_min_index(posible_min_distance, dist, unsearched_nodes) 
      unsearched_nodes.remove(target_min_index) 
 
      target_edge = dp[target_min_index] 
      for index, route_dis in enumerate(target_edge):
          if route_dis != 0:
              if dist[index] > (dist[ target_min_index] + route_dis):
                  dist[index] = dist[ target_min_index] + route_dis 
                  previous_nodes[index] =  target_min_index 
    
    previous_node = r[j]
    while previous_node != -1:
      if previous_node !=i:
        
      else:
        
      previous_node = previous_nodes[previous_node]
 
    
    
    distance[i][j]=dist[j]
    distance[j][i]=dist[j]
'''
 
ans=10**11
for tmp in permutations(r):
  tmpans=0
  for i in range(len(tmp)-1):
    tmpans+=distance[tmp[i]-1][tmp[i+1]-1]
  if ans>tmpans:
    ans=tmpans
print(int(ans))

Solution (Python):
n,m,rrr = map(int,input().split())
R = tuple(map(int,input().split()))
ABC = [list(map(int,input().split())) for _ in range(m)]
inf = 1000000000

edge = [[inf]*(n+1) for _ in range(n+1)]

for a,b,c in ABC:
    edge[a][b] = c
    edge[b][a] = c
    
def dijkstra(start,e,N):
    for _ in range(3):
        for v in range(1,N+1):
            for g in range(1,N+1):
                e[start][g] = min(e[start][g],e[start][v] + e[v][g])
                e[g][start] = e[start][g]
    return e[start]

dic = {}
for rr in R:
    dic[rr] = dijkstra(rr,edge,n)

from itertools import permutations as pm

temp = list(pm(R))

ans = 10000000000
for RR in temp:
    cost = 0
    for i in range(rrr-1):
        cost += dic[RR[i]][RR[i+1]]
    if cost < ans:
        ans = cost
print(ans)

Solution (Python):
import sys
from itertools import permutations
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
MOD = 1000000007
def POW(x, y): return pow(x, y, MOD)
def INV(x, m=MOD): return pow(x, m - 2, m)
def DIV(x, y, m=MOD): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LLI(n): return [[int(x) for x in input().split()] for _ in range(n)]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


N,M,R = LI()
RS=LI()
mp = [[10**10]*(N+1) for _ in range(N+1)]
for a,b,c in LLI(M):
    mp[a][b] = c
    mp[b][a] = c

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

res = INTMAX
for l in permutations(RS):
    sc = 0
    for i in range(R-1): 
        sc += mp[l[i]][l[i+1]]
    res = min(res,sc)
print(res)

Solution (Python):

import sys
from itertools import permutations
 
def warshall_floyd(conn):
    n = len(conn)
    dp = [[v for v in A] for A in conn]
    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])
    return dp
 
 
def solve(N: int, M: int, R: int, r: "List[int]", A: "List[int]", B: "List[int]", C: "List[int]"):
    conn = [[float('inf') for _ in range(N)] for _ in range(N)]
    for i in range(N):
        conn[i][i] = 0
    for j in range(M):
        a = A[j] - 1
        b = B[j] - 1
        conn[a][b] = min(conn[a][b], C[j])
        conn[b][a] = min(conn[b][a], C[j])
    dp = warshall_floyd(conn)
    
    ret = float('inf')
    perms = list(permutations(list(range(R))))
    for order in perms:
        tmp = 0
        for i in range(R - 1):
            s = r[order[i]] - 1
            t = r[order[i + 1]] - 1
            
            tmp += dp[s][t]
        ret = min(ret, tmp)
    print(ret)
    return
 
 
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))
    solve(N, M, R, r, A, B, C)
 
if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter
from collections import deque
from functools import reduce
from pprint import pprint
import itertools
import bisect
import copy
import fractions
import math
import random
import sys
import time
import queue
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers): return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers): return reduce(LCM, numbers)
def LCM(m, n): return (m * n // fractions.gcd(m, n))
def warshall_floyd(n):
    
    for i in range(n):  
        for j in range(n):  
            for k in range(n):  
                graph[j][k] = min(graph[j][k], graph[j][i] + graph[i][k])


N, M, R = MI()
r = LI()
road = [LI() for _ in range(M)]
graph = [[INF] * N for _ in range(N)]

distance = [[INF] * N for _ in range(N)]
for a, b, c in road:
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c
for i in range(N):
    graph[i][i] = 0

q = queue.PriorityQueue()














for begin in r:
    begin -= 1
    q.put((0, begin))  
    while not q.empty():
        cost, v = q.get()
        if distance[begin][v] < cost:
            continue
        distance[begin][v] = cost

        for next_v in range(N):
            if graph[v][next_v] == 0:
                continue
            q.put((distance[begin][v] + graph[v][next_v], next_v))

mini = INF
for permutation in itertools.permutations(r):
    tmp = 0
    
    for i in range(R-1):
        tmp += distance[permutation[i]-1][permutation[i+1]-1]
    mini = min(mini, tmp)

print(mini)

Solution (Python):
import itertools
n,m,r=map(int,input().split())
R=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(m)]

distance=[[99999999 for i in range(n)] for j in range(n)]
for i in range(n):
  distance[i][i]=0
for i in range(m):
  distance[l[i][0]-1][l[i][1]-1]=l[i][2]
  distance[l[i][1]-1][l[i][0]-1]=l[i][2]

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

ans=99999999
for i in itertools.permutations(R):
  L=list(i)
  ct=0
  for j in range(r-1):
    ct+=distance[L[j]-1][L[j+1]-1]
  ans=min(ans,ct)
print(ans)

Solution (Python):
from itertools import permutations

INF = 1e+9
N, M, R = map(int, input().split())
rlist = list(map(int, input().split()))

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

def warshall_floyd(G):
    V = len(G)
    for k in range(V):
        for i in range(V):
            for j in range(V):
                G[i][j] = min(G[i][j], G[i][k] + G[k][j])
    return G

G = warshall_floyd(G)
sum_list = []
for tmp in permutations(rlist):
    t_sum = 0
    for i in range(len(tmp)-1):
        t_sum += G[tmp[i]-1][tmp[i+1]-1]
    sum_list.append(t_sum)

print(min(sum_list))

Solution (Python):
from itertools import permutations

INF = 1e+9
N, M, R = map(int, input().split())
rlist = list(map(int, input().split()))

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

def warshall_floyd(G):
    V = len(G)
    for k in range(V):
        for i in range(V):
            for j in range(V):
                G[i][j] = min(G[i][j], G[i][k] + G[k][j])
    return G

G = warshall_floyd(G)
sum_list = []
for tmp in permutations(rlist):
    t_sum = 0
    for i in range(len(tmp)-1):
        t_sum += G[tmp[i]-1][tmp[i+1]-1]
    sum_list.append(t_sum)

print(min(sum_list))

Solution (Python):
from scipy.sparse.csgraph import dijkstra as di
from itertools import permutations
N,M,R = map(int, input().split())
r = list(map(int, input().split()))

route = [[0 for i in range(N)] for j in range(N)]
for i in range(M):
    a,b,c = map(int, input().split())
    route[a-1][b-1] = route[b-1][a-1] = c




p_route = di(route)


mn = float('INF')
for tmp in permutations(r):
    t_sum = 0
    for i in range(len(tmp)-1):
        t_sum += p_route[tmp[i]-1][tmp[i+1]-1]
    if t_sum < mn:
        mn = t_sum

print(int(mn))

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

n, m, r = map(int, input().split())
v = list(map(int, input().split()))
v = [i - 1 for i in v]


graph = [[float('inf') for i in range(n)] for i 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

tip_graph = floyd_warshall(csgraph = graph, directed = False, return_predecessors = False)

ans = 10 ** 9
tmp = 0

for i in list(itertools.permutations(v,r)):
    tmp = 0
    for j in range(r-1):
        tmp += tip_graph[i[j]][i[j+1]]
    ans = min(ans, tmp)
print(int(ans))

Solution (Python):











import sys
input=sys.stdin.readline
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [input() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    from itertools import permutations
    N, M, R = MI()
    r = LI_()
    d=[[float("inf")] * N for i in range(N)]
    for i in range(N):
        d[i][i]=0
    for _ in range(M):
        a, b, c = MI_()
        c += 1
        d[a][b] = c
        d[b][a] = c
    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])


    warshall_floyd(d, N)

    ans=inf
    for p in permutations(r):
        prev = p[0]
        cost = 0
        for to in p[1:]:
            cost += d[prev][to]
            prev = to
        ans=min(cost,ans)
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):


from collections import* 
from fractions import gcd
from functools import* 
from itertools import* 
from operator import mul
from bisect import* 
from heapq import* 
from math import factorial
from copy import deepcopy
import sys
from scipy.sparse.csgraph import floyd_warshall


sys.setrecursionlimit(10**6)


def main():
    n,m,r=map(int,input().split())
    grid=[[0]*n for i in range(n)]
    *R,=map(int,input().split())
    for i in range(m):
        a,b,c=map(int,input().split())
        grid[a-1][b-1]=c
        grid[b-1][a-1]=c

    d,p=floyd_warshall(csgraph=grid, directed=False, return_predecessors=True)


    print(int(min(sum(d[i[j]-1][i[j+1]-1]for j in range(len(i)-1))for i in permutations(R))))
    
if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter
from collections import deque
from functools import reduce
from pprint import pprint
import itertools
import bisect
import copy
import fractions
import math
import random
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers): return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers): return reduce(LCM, numbers)
def LCM(m, n): return (m * n // fractions.gcd(m, n))
def warshall_floyd(n):
    for i in range(n):  
        for j in range(n):  
            for k in range(n):  
                graph[j][k] = min(graph[j][k], graph[j][i] + graph[i][k])


N, M, R = MI()
r = LI()
road = [LI() for _ in range(M)]
graph = [[INF] * N for _ in range(N)]


for a, b, c in road:
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c
for i in range(N):
    graph[i][i] = 0


warshall_floyd(N)









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

Solution (Python):

import itertools

N,M,R=map(int,raw_input().split())
R=map(int,raw_input().split())
D=[[1145141919810]*300 for _ in range(300)]
for i in range(M):
    a,b,c=map(int,raw_input().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):
            if D[i][j]>D[i][k]+D[k][j]:
                D[i][j]=D[i][k]+D[k][j]
ans=1145141919810
for P in itertools.permutations(R):
    s=P[0]
    l=0
    for t in P[1:]:
       l+=D[s][t]
       s=t
    ans=min(ans,l)
print(ans)

Solution (Python):
from itertools import permutations


def warshall_floyd(v_count: int, matrix: list) -> list:
    """ ワーシャルフロイド
    v_count: 頂点数
    matrix: 隣接行列(到達不能はfloat("inf"))
    """
    for i in range(v_count):
        for j, c2 in enumerate(row[i] for row in matrix):
            for k, (c1, c3) in enumerate(zip(matrix[j], matrix[i])):
                if c1 > c2+c3:
                    matrix[j][k] = c2+c3
    return matrix


INF = 10 ** 9
N, M, R = map(int, input().split())
m = [[INF for i in range(N)] for j in range(N)]
for i in range(N):
    m[i][i] = 0
r = list(map(lambda x: int(x) - 1, input().split()))
for i in range(M):
    a, b, c = map(int, input().split())
    m[a - 1][b - 1] = c
    m[b - 1][a - 1] = c
m = warshall_floyd(N, m)
ans = INF
for path in permutations(r, R):
    tmp = 0
    for i in range(len(path) - 1):
        tmp += m[path[i + 1]][path[i]]
    ans = min(ans, tmp)
print(ans)

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

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




import heapq
r_dis_list = []
for i in range(len(r)):
    vi = r[i]-1
    min_d_list = [10**27 for i in range(N)]
    min_d_list[vi] = 0
    prev_list = [-1 for i in range(N)]
    q = []
    for i in range(N):
        heapq.heappush(q,[min_d_list[i],i])

    while len(q)>0:
        d,v = heapq.heappop(q)
        for e in e_list[v]:
            v1,d1=e
            if min_d_list[v1]>d+d1:
                min_d_list[v1]=d+d1
                prev_list[v1]=v
                heapq.heappush(q,[d+d1,v1])

    r_dis_list.append([min_d_list[r[i]-1] for i in range(len(r))])

import itertools
min_ans = 10**27
for i in itertools.permutations(range(len(r))):
    ans = 0
    for j in range(len(r)-1):
        ans+=r_dis_list[i[j+1]][i[j]]
    min_ans=min(ans,min_ans)

print(min_ans)

Solution (Python):
import itertools

N, M, R = map(int, input().split())
r = list(map(lambda x: int(x) - 1, input().split()))
A = [0] * M
B = [0] * M
C = [0] * M
for i in range(M):
    A[i], B[i], C[i] = map(int, input().split())
MAX = 10 ** 10
dist = [[MAX] * N for _ in range(N)]

for i in range(M):
    dist[A[i]-1][B[i]-1] = C[i]
    dist[B[i]-1][A[i]-1] = C[i]
    
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 ** 10
for per in itertools.permutations(r, R):
    cost = 0
    for i in range(R-1):
        cost += dist[per[i]][per[i+1]]
    ans = min(ans, cost)

print(ans)