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
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
    
adj = [[INF]*N for _ in range(N)]
perm_list = []

def make_permutation(l,R):
    if R == 0:
        perm_list.append(l)
    else:
        for a in r:
            if a not in l:
                make_permutation(l+[a],R-1)

def main():
    for _ in range(M):
        A, B, C = map(int, input().split())
        adj[A-1][B-1] = C
        adj[B-1][A-1] = C
    
    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                adj[i][j] = min(adj[i][j], adj[i][k]+adj[k][j])

    make_permutation([],R)
    ans = INF
    for ps in perm_list:
        tmp = 0
        for i in range(R-1):
            tmp += adj[ps[i]-1][ps[i+1]-1]
        ans = min(ans,tmp)
    print(ans)
    

if __name__ == "__main__":
    main()

Solution (Python):
n,m,r = map(int,input().split())
v = list(map(int,input().split()))
for i in range(r):
    v[i] -= 1
INF = float("inf")
g = [[INF]*n for _ in range(n)]
for i in range(m):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    g[a][b] = c
    g[b][a] = c
for i in range(n): g[i][i] = 0
for k in range(n):
    for i in range(n):
        for j in range(n):
            g[i][j] = min(g[i][j],g[i][k]+g[k][j])


dp = [[INF]*r for i in range(2**r)]
for i in range(r):
    dp[2**i][i] = 0


for i in range(1,2**r):
    for j in range(r):
        if dp[i][j] == INF:
            continue
        for k in range(r):
            nxt = i | 2**k
            dp[nxt][k] = min(dp[nxt][k],dp[i][j]+g[v[j]][v[k]])

print(min(dp[-1]))

Solution (Python):
from itertools import permutations as per
n,m,r = map(int,input().split())
v = list(map(int,input().split()))
for i in range(r):
    v[i] -= 1
INF = float("inf")
g = [[INF]*n for _ in range(n)]
for i in range(m):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    g[a][b] = c
    g[b][a] = c
for i in range(n): g[i][i] = 0
for k in range(n):
    for i in range(n):
        for j in range(n):
            g[i][j] = min(g[i][j],g[i][k]+g[k][j])

ans = INF
for l in per(range(r)):
    t = 0
    for i in range(r-1):
        t += g[v[l[i]]][v[l[i+1]]]
    ans = min(ans,t)
print(ans)

Solution (Python):
import sys
from itertools import permutations
def input(): return sys.stdin.readline().strip()


def main():
    N, M, num = map(int, input().split())
    R = list(map(int, input().split()))

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

    
    ans = 10**18
    for r in list(permutations(R)):
        d = 0
        for i in range(num - 1):
            d += path[r[i] - 1][r[i + 1] - 1]
        ans = min(ans, d)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import defaultdict
from heapq import heapify,heappush,heappop
readline=sys.stdin.readline

def main():
    N,M,R=map(int,readline().split())
    r=list(map(int,readline().split()))
    ew=[tuple(map(int,readline().split())) for _ in range(M)]
    edges=defaultdict(list)
    wt=defaultdict(int)
    for e in ew:
        edges[e[0]].append(e[1])
        edges[e[1]].append(e[0])
        wt[(e[0],e[1])]=e[2]
        wt[(e[1],e[0])]=e[2]
    inf=float('inf')
    def dijkstra(v):
        dist=[inf]*(N+1)
        dist[v]=0
        vw=[(0,v)]
        heapify(vw)
        while vw:
            cvw=heappop(vw)
            if cvw[0]>dist[cvw[1]]:
                continue
            for w in edges[cvw[1]]:
                cand=cvw[0]+wt[(cvw[1],w)]
                if dist[w]>cand:
                    dist[w]=cand
                    heappush(vw,(cand,w))
        return dist
    distdict=dict((v,dijkstra(v)) for v in r)
    mindist=inf
    def permlist(lst):
        tmp=[]
        if not lst:
            return [[]]
        for i,x in enumerate(lst):
            lstx=lst[:i]+lst[i+1:]
            ret=permlist(lstx)
            for e in ret:
                e.append(x)
            tmp.extend(ret)
        return tmp
    
    pathlist=[sum([distdict[v][w] for v,w in zip(lst,lst[1:])]) for lst in permlist(r)]
    print(min(pathlist))

if __name__=='__main__':
    main()

Solution (Python):
import sys
from itertools import permutations

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, R = map(int, readline().split())
    city = [int(s) - 1 for s in readline().split()]
    ABC = map(int, read().split())

    G = [[INF] * N for _ in range(N)]
    for a, b, c in zip(*[iter(ABC)] * 3):
        G[a - 1][b - 1] = G[b - 1][a - 1] = c

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

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

    ans = INF
    for plan in permutations(city):
        res = 0
        for i in range(R - 1):
            res += G[plan[i]][plan[i + 1]]
        if ans > res:
            ans = res

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import permutations as perm
n, m, r = map(int, input().split())
rs = list(map(int, input().split()))
grid = [[float('inf')]*n for _ in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    grid[a-1][b-1] = c
    grid[b-1][a-1] = c
for i in range(n):
    for j in range(n):
        if i == j:
            grid[i][j] = 0
for k in range(n):
    for i in range(n):
        for j in range(n):
            grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j])

perms = rs
res = float('inf')
for p in perm(perms):
    tmp = 0
    for i in range(1,r):
        tmp += grid[p[i]-1][p[i-1]-1]
    res = min(res,tmp)
print(res)

Solution (Python):
def abc073_d():
    from scipy.sparse import lil_matrix
    from scipy.sparse.csgraph import floyd_warshall
    from itertools import permutations

    n, m, r = map(int, input().split())
    R = list(map(lambda x: int(x)-1, input().split()))
    graph = lil_matrix((n, n), dtype=int)
    for _ in range(m):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        graph[a, b] = c
        graph[b, a] = c

    dist = floyd_warshall(csgraph=graph)
    

    ans = 10**18
    for route in permutations(R, r):
        tmp = 0
        for i in range(r-1):
            s = route[i]
            t = route[i+1]
            tmp += dist[s][t]
            if tmp > ans: break
        ans = min(ans, tmp)
        

    print(int(ans))

if __name__ == '__main__':
    abc073_d()

Solution (Python):
import sys
import heapq
import itertools

INF = 10**18

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def dijkstra(N, s0, edge):

    d = [INF] * N
    pre_v = [-1] * N
    used = [False] * N
    edgelist = [(0, s0, -1)]
    heapq.heapify(edgelist)

    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if used[minedge[1]]:
            continue

        v = minedge[1]
        d[v] = minedge[0]
        used[v] = True
        pre_v[v] = minedge[2]

        for e in edge[v]:
            if d[e[1]] <= (e[0] + d[v]) or used[e[1]]:
                continue
            heapq.heappush(edgelist, (e[0] + d[v], e[1], v))
    return d, pre_v


def main():

    N, M, R = in_nn()
    r = in_nl()
    r = [t - 1 for t in r]
    edge = [[] for _ in range(N)]

    for i in range(M):
        a, b, c = in_nn()
        a, b = a - 1, b - 1
        edge[a].append((c, b))
        edge[b].append((c, a))

    dis = [[-1] * N for _ in range(N)]
    for i in range(R):
        s = r[i]
        d, pre_v = dijkstra(N, s, edge)

        for j in range(R):
            e = r[j]
            dis[s][e] = d[e]

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

            e = r[j]
            tr = set(r) - {e} - {s}
            while e != -1:
                t = pre_v[e]
                if t in tr:
                    dis[s][e] = -1
                    break
                else:
                    e = t

    perm = itertools.permutations(r, R)

    ans = INF
    for per in perm:

        td = 0
        for i in range(R - 1):
            s, e = per[i], per[i + 1]
            if dis[s][e] == -1:
                break
            else:
                td += dis[s][e]
        else:
            ans = min(ans, td)

    
    print(ans)


if __name__ == '__main__':
    main()

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

N,M,R = map(int, input().split())
rs = np.array(list(map(int, input().split()))) -1

nodes = np.full((N,N), np.inf) 
for i in range(M):
  a,b,c = map(int, input().split())
  nodes[a-1,b-1] = nodes[b-1,a-1] = c
min_ds = shortest_path(nodes)
res = float('inf')
for p in itertools.permutations(rs):
  prev = p[0]
  tmp = 0
  for next in p[1:]:
    tmp += min_ds[prev,next]
    prev = next
  res = min(res, tmp)

print(int(res))

Solution (Python):
from itertools import permutations
INFTY = 10**8
N,M,R = map(int,input().split())
r = list(map(int,input().split()))
G = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b,c = map(int,input().split())
    G[a].append((b,c))
    G[b].append((a,c))
dist = [[INFTY for _ in range(N+1)] for _ in range(N+1)]
for i in range(1,N+1):
    dist[i][i] = 0
for i in range(1,N+1):
    for j,d in G[i]:
        dist[i][j] = d
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j])
dmin = 10**8
for x in permutations(range(R),R):
    d = 0
    for k in range(1,R):
        d += dist[r[x[k]]][r[x[k-1]]]
    dmin = min(dmin,d)
print(dmin)

Solution (Python):
n, m, r = map(int, input().split())
R = list(map(int, input().split()))
R = [x-1 for x in R]

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

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

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

d = warshal_floyd(d)
import itertools
ans = float('inf')
for p in itertools.permutations(R):
    temp = 0
    for i in range(r-1):
        temp += d[p[i]][p[i+1]]
    ans = min(temp, ans)
print(ans)

Solution (Python):
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
d = [[float('inf')]*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 = float('inf')
for p in permutations(r,R):
  cnt = 0
  for i in range(1,R):
    cnt += d[p[i-1]-1][p[i]-1]
  ans = min(ans,cnt)
print(ans)

Solution (Python):
import sys
import itertools

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

N, M, R = map(int, sys.stdin.readline().split())
r = list(map(int, sys.stdin.readline().split()))


d = [[float("inf")]*N for i in range(N)] 
for _ in range(M):
	a, b, c = map(int, sys.stdin.readline().split())
	d[a-1][b-1] = c
	d[b-1][a-1] = c

d = warshall_floyd(d, N)



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

print(ans)

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

N,M,R = map(int, input().split())
r_list = np.array(list(map(int, input().split()))) -1 

nodes = np.full((N,N), np.inf) 
for i in range(M):
    a,b,c = map(int, input().split())
    nodes[a-1,b-1] = nodes[b-1,a-1] = c
min_ds = shortest_path(nodes)
res = 10**9
for cmb in itertools.permutations(r_list):
    prev = cmb[0]
    tmpres = 0
    for to in cmb[1:]:
        tmpres += min_ds[prev,to]
        prev = to
    res = min(res, tmpres)

print(int(res))

Solution (Python):
from collections import deque

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

mp = [[float('inf')]*(N+1) for _ in range(N+1)]

for i in range(1,N+1):
  mp[i][i] = 0

for _ in range(M):
  a,b,c = map(int, input().split())
  mp[a][b] = c
  mp[b][a] = c
  
for k in range(1,N+1):
  for i in range(1,N+1):
    for j in range(1,N+1):
      mp[i][j] = min(mp[i][j], mp[i][k]+mp[k][j])

rlt = float('inf')
h = deque([])
for r in Rs:
  h.append([r])
  
while h:
  t = h.pop()
  if len(t) == R:
    tmp = 0
    for i in range(R-1):
      tmp += mp[t[i]][t[i+1]]
    rlt = min(rlt, tmp)
  else:
    for r in Rs:
      if r not in t:
        u = t + [r]
        h.append(u)

print(rlt)

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

Solution (Python):
N, M, R = map(int, input().split())
*r, = map(lambda x:int(x)-1, 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])

import itertools
ans = float('inf')
for s in itertools.permutations(r, R):
    tot = [D[s[i]][s[i+1]] for i in range(R-1)]
    tot = sum(tot)
    ans = min(ans, tot)

print(ans)

Solution (Python):
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
from operator import mul

INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)



class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def dijkstra_heap(s, edge, n):
    
    d = [10**20] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


def combinations_count(n, r):
    if n < r:
        return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


def lcm(x, y):
    return (x * y) // gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm, numbers, 1)


def gcd_list(numbers):
    return reduce(gcd, numbers)


def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True



def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P


def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]




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

d = [[INF for j in range(n)] for i in range(n)]
for i in range(m):
    d[a[i]][b[i]] = c[i]
    d[b[i]][a[i]] = c[i]
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])

ans = INF
for i in permutations(cities):
    total = 0
    for j in range(1, r):
        total += d[i[j] - 1][i[j - 1] - 1]
    ans = min(ans, total)
print(ans)

Solution (Python):
from itertools import permutations

n,m,r=list(map(int,input().split()))
rlst=list(map(int,input().split()))
inf=10**20

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

for _ in range(m):
    a,b,c=list(map(int,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):
            d[i][j]=min(d[i][j],d[i][k]+d[k][j])
ans=inf
for comb in permutations(rlst,r):
    i=0
    tans=0

    while i+1<r:
        tans+=d[comb[i]][comb[i+1]]
        i+=1
    
    ans=min(ans,tans)

print(ans)

Solution (Python):
n, m, r = map(int, input().split())
R = tuple(map(lambda x: int(x)-1, input().split()))
INF = 10**9
dp = [[INF]*n for _ in range(n)]

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

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

Solution (Python):
import itertools

INF = 10**10
N, M, R = map(int, input().split())
*r, = map(int, input().split())
r = [v-1 for v in r]

g = [[INF]*N for _ in range(N)]
for i in range(N):
    g[i][i] = 0

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

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

ans = INF
for rs in itertools.permutations(r):
    cost = 0
    for i in range(len(rs)-1):
        cost += g[rs[i]][rs[i+1]]
    if cost < ans:
        ans = cost

print(ans)

Solution (Python):
n, m, r = map(int, input().split())
R = tuple(map(lambda x: int(x)-1, input().split()))
INF = 10**9
dp = [[INF]*n for _ in range(n)]

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

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

Solution (Python):
N,M,R = map(int,input().split())
R = 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] = min(dp[a][b],c)
    dp[b][a] = min(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][k],dp[j][i]+dp[i][k])

def dfs(p,n,path,cost):
    path.add(n)
    cost += dp[p][n]
    
    if len(path) == len(R):
        return cost
    else:
        res = float("INF")
        for r in R:
            if r not in path:
                res = min(res,dfs(n,r,path,cost))
                path.remove(r)
        return res
ans = float("INF")
for r in R:
    ans = min(ans,dfs(r,r,set(),0))
print(ans)

Solution (Python):
from collections import defaultdict
from itertools import permutations
import heapq

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

Adj_list = defaultdict(set)

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


def dijkstra(x, vertex):
    d = [INF] * x
    d[vertex] = 0
    hq = [(0, vertex)]
    
    while hq:
        u = heapq.heappop(hq)[1]
        for (v, c) in Adj_list[u]:
            if d[v] > d[u] + c:
                d[v] = d[u] + c
                heapq.heappush(hq, (d[u]+c, v))

    return d

ans = INF
t_dis = 0

table = {}
for i in r:
    table[i-1] = dijkstra(N, i-1)

for each in permutations(r):
    t_dis = 0
    for i in range(R-1):
        t_dis += table[each[i]-1][each[i+1]-1]

    ans = min(ans, t_dis)

print(ans)

Solution (Python):
n, m, r = map(int, input().split())  
r_list = list(map(int, input().split()))
graph = [[float('inf')]*n for i in range(n)]
for _ in range(m):
    u, v, w = map(int, input().split())
    graph[u-1][v-1] = w
    graph[v-1][u-1] = w
for i in range(n):
    graph[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


from itertools import permutations

adj_m=warshall_floyd(graph)
ans=float('inf')
for path in permutations(r_list):
    tmp_dist=0
    for i in range(r-1):
        tmp_dist+=adj_m[path[i]-1][path[i+1]-1]
    ans=min(ans, tmp_dist)
print(ans)

Solution (Python):
import itertools

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

N, M ,R = map(int, input().split())
r = list(map(int, input().split()))
rr = list(itertools.permutations(r, R))
ab = [[10 ** 10] * N for i in range(N)]
for i in range(N):
  ab[i][i] = 0
  
for i in range(M):
  a, b, c = list(map(int, input().split()))
  ab[a - 1][b - 1] = c
  ab[b - 1][a - 1] = c
  
ans = warshall_floyd(ab)  



answer = 10 ** 12
for i in rr:
  now = 0
  
  for j in range(R - 1):
    now += ans[i[j] - 1][i[j + 1] - 1]
    
  answer = min(answer, now)  
  
print(answer)

Solution (Python):


from itertools import permutations
from collections import defaultdict

N, M, R = map(int, input().split())
G = defaultdict(list)
d =[ [float("inf")] * N for i in range(N)]
listR = list(map(int, input().split()))
for _ in range(M):
    ai, bi, ci = map(int, input().split())
    ai, bi = ai - 1, bi - 1
    G[ai].append((bi, ci))
    G[bi].append((ai, ci))
    d[ai][bi] = d[bi][ai] = ci


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 = float("inf")
for perm in permutations(listR):
    cost_perm = 0
    for i in range(len(perm) - 1):
        pi, pj = perm[i] - 1, perm[i + 1] - 1
        cost_perm += d[pi][pj]
    ans = min(ans, cost_perm)
print(ans)

Solution (Python):
import itertools

N, M, R = map(int, input().split())
r = map(int, input().split())
A = [[1 << 64]*N for _ in range(N)]
for i in range(N):
    A[i][i] = 0
for _ in range(M):
    a, b, c = map(int, input().split())
    A[a-1][b-1] = A[b-1][a-1] = c


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

res = 1 << 64
for perm in itertools.permutations([x-1 for x in r]):
    cost = 0
    for i in range(R-1):
        cost += A[perm[i]][perm[i+1]]
    if cost < res:
        res = cost

print(res)

Solution (Python):
from itertools import permutations
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
r = permutations(r, len(r))
INF = 10**10
dist = [[INF]*N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    dist[a-1][b-1] = dist[b-1][a-1] = c
for k in range(N):
    for i in range(N):
        for j in range(N):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] =  dist[j][i] = dist[i][k] + dist[k][j]
ans = INF
for i in r:
    tmp = 0
    for j in range(len(i)-1):
        tmp += dist[i[j]-1][i[j+1]-1]
    ans = min(ans, tmp)
print(ans)

Solution (Python):
from itertools import permutations

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

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

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

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

for j in range(N):
    road[j][j] = 0

road = warshall_floyd(road)


ans = float("inf")

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

print(ans)

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from itertools import permutations

    n, m, q = map(int, readline().split())
    r_ = list(map(int, readline().split()))
    r = [i-1 for i in r_]

    dist = [[10 ** 18] * n for _ in range(n)]

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

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

    ans = 10 ** 18
    for per in permutations(range(q)):
        score = 0
        for i in range(q - 1):
            score += dist[r[per[i]]][r[per[i + 1]]]
        ans = min(ans, score)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import permutations
n, m, r = map(int, input().split())
goals = list(map(int, input().split()))
goals = [g-1 for g in goals]

g = [[pow(10, 16)] * n for i in range(n)]

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

for i in range(n):
    for s in range(n):
        for t in range(n):
            g[s][t] = min(g[s][t], g[s][i] + g[i][t])

ans = float('inf')
for p in permutations(goals):
    cost = 0
    for s,t in zip(p[:-1], p[1:]):
        cost += g[s][t]
    ans = min(ans, cost)
print(ans)

Solution (Python):
from itertools import permutations

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


n,m,r= map(int,input().split())
moku = list(map(int,input().split()))
d = [[float("inf")]*n for i in range(n)] 

for i in range(m):
    x,y,z = map(int,input().split())
    d[x-1][y-1] = z
    d[y-1][x-1] = z
for i in range(n):
    d[i][i] = 0 
p = warshall_floyd(d)

a = [i for i in range(r)]
zyun = list(permutations(a))

ans = 10**9
for i in zyun:
    cou = 0
    for j in range(r-1):
        cou += p[moku[i[j]]-1][moku[i[j+1]]-1]
    ans = min(ans,cou)
print(ans)