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):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby
    
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    

    inf = 10**17
    

    N,M,R = map(int, input().split())
    r = list(map(int, input().split()))
    for i in range(R):
        r[i] -= 1

    def dijkstra_heap(start,edge):
        
        d = [inf]*N
        used = [False]*N
        d[start] = 0
        used[start] = True
        edgelist = []
        
        for a,b in edge[start]:
            heappush(edgelist,a*(10**6)+b)

        while len(edgelist):
            
            minedge = heappop(edgelist)
            if used[minedge%(10**6)]:
                continue
            node = minedge%(10**6)
            d[node] = minedge//(10**6)
            used[node] = True

            for e in edge[node]:
                if not used[e[1]]:
                    heappush(edgelist,(e[0]+d[node])*(10**6)+e[1])
        return d

    edge = [[] for i in range(N)]
    
    for _ in range(M):
        x,y,z = map(int,input().split())
        edge[x-1].append((z,y-1))
        edge[y-1].append((z,x-1))

    kyori = []
    for i in r:
        kyori.append(dijkstra_heap(i,edge))
    
    res = inf
    for i in permutations(range(R), R):
        l = list(i)
        path = 0
        for j in range(R-1):
            path += kyori[l[j]][r[l[j+1]]]
        res = min(res, path)

    print(res)

if __name__ == '__main__':
    main()

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

int1 = lambda x: int(x) - 1

N, M, R = map(int, input().split())
T = sorted(list(map(int1, input().split())))
A = np.array([tuple(map(int, input().split())) for _ in range(M)]).T

matr = csr_matrix((A[2], (A[0] - 1, A[1] - 1)), shape=(N, N))
way = [dijkstra(matr, indices=t, directed=False)[T].astype(int).tolist() for t in T]

ans = float('inf')
for t in itertools.permutations(range(R)):
    tmp = 0
    for i in range(R - 1):
        tmp += way[t[i]][t[i + 1]]
    ans = min(ans, tmp)
print(ans)

Solution (Python):


from itertools import permutations
import numpy as np

HUGE = 10 ** 18

def main():
    n, m, r = map(int, input().split())
    togo = list(map(int, input().split()))
    adj_mat = [[HUGE for j in range(n)] for i in range(n)]
    for i in range(n):
        adj_mat[i][i] = HUGE
    for i in range(m):
        a, b, c = map(int, input().split())
        a0 = a - 1
        b0 = b - 1
        adj_mat[a0][b0] = c
        adj_mat[b0][a0] = c
    adj_mat = np.array(adj_mat)

    wf(adj_mat, n)

    res = HUGE
    for way in permutations(togo):
        assert len(way) > 1
        x = 0
        for i in range(len(way) - 1):
            x += adj_mat[way[i] - 1][way[i + 1] - 1]
        res = min(res, x)

    print(res)

def wf(adj_mat, n):
    for k in range(n):
        for i in range(n):
            adj_mat[i, :] = np.minimum(adj_mat[i, :], adj_mat[i][k] + adj_mat[k, :])

if __name__ == "__main__":
    main()

Solution (Python):
import copy

N,M,R=map(int,input().split())
r=list(map(int,input().split()))
d=[[10**15 for i in range(0,N+1)] for i in range(0,N+1)]
for i in range(0,M):
    a,b,c=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):
            if d[i][j]>d[i][k]+d[k][j]:
                d[i][j]=d[i][k]+d[k][j]

ans=10**15
def dfs(load,cost,last):
    global ans
    if len(load)==R:
        if ans>cost:
            ans=cost

    elif len(load)!=0:
        for city in r:
            if not city in load:
                a=copy.copy(load)
                a.add(city)
                dfs(a,cost+d[last][city],city)

    else:
        for city in r:
            dfs(set([city]),0,city)



dfs(set([]),0,0)

print(ans)

Solution (Python):
import itertools


N,M,R = map(int,input().split())
r = list(map(int,input().split()))
INF = float('inf')
D = [[INF]*(N+1) for _ in range(N+1)]
for i in range(1,N+1):
    D[i][i] = 0

for _ in range(M):
    a,b,c = 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])

loads = list(itertools.permutations(r))


ans = INF

for load in loads:
    temp = 0
    for i in range(R-1):
        temp += D[load[i]][load[i+1]]
    
    ans = min(temp,ans)
    
    
    

print(ans)

Solution (Python):

from heapq import heappop, heappush
from itertools import permutations

N,M,R=map(int,input().split())
town=list(map(int,input().split()))
INF=10**9
G=[[INF for i in range(N+1)] for j in range(N+1)]

for i in range(M):
    A,B,C=map(int,input().split())
    G[A][B]=C
    G[B][A]=C

d=[[INF*10 for i in range(N+1)] for j in range(R)]

for k in range(R):
    r=town[k]
    d[k][r]=0
    
    used=[False for i in range(N+1)]
    
    heap=[]
    heappush(heap,(d[k][r],r))
    
    while heap:
        d_u, u = heappop(heap)

        used[u] = True
        
        if d[k][u] < d_u:
            continue
        
        for v in range(N+1):
            if not(used[v]) and d_u + G[u][v] < d[k][v]:
                d[k][v] = d_u + G[u][v]
                heappush(heap,(d[k][v],v))

ans=INF

L=[i for i in range(R)]

for v in permutations(L,R):
    D=0
    for i in range(R-1):
        D+=d[v[i]][town[v[i+1]]]
    ans=min(ans,D)
    
print(ans)

Solution (Python):
import itertools

n,m,r=map(int,input().split())
D=[[10**10]*n for _ in range(n)]
for i in range(n):
    D[i][i]=0
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])

A=[]
for v in itertools.permutations(R,r):
    ans=0
    for i in range(r-1):
        ans+=D[v[i]-1][v[i+1]-1]
    A.append(ans)
print(min(A))

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






r = list(map(lambda x: int(x)-1, input().split()))
edge = [[10**9] * N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    a, b = a-1, b-1
    edge[a][b] = c
    edge[b][a] = c

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

ans = 10 ** 20
for per in permutations(r):
    tmp = 0
    for i in range(R-1):
        tmp += edge[per[i]][per[i+1]]
    ans = min(ans, tmp)

print(ans)

Solution (Python):



from itertools import permutations

def main():
  n, m, nr = map(int, input().split())
  lr = list(map(lambda x:int(x)-1, input().split()))
  edges = [[10**9]*n for _ in range(n)]
  for i in range(n):
    edges[i][i] = 0
  for _ in range(m):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    edges[a][b] = edges[b][a] = c
    
  def wf():
    for k in range(n):
      for i in range(n):
        for j in range(n):
          edges[i][j] = min(edges[i][j], edges[i][k] + edges[k][j])
  wf()
          
  def calc_cost(path):
    cost = 0
    for i in range(nr-1):
      cost += edges[path[i]][path[i+1]]
    return cost
  
  print(min([calc_cost(path) for path in permutations(lr)]))

if __name__=='__main__':
  main()

Solution (Python):
import itertools
n,m,r=map(int,input().split())
point=list(map(int,input().split()))
g=[[10**9]*n for i in range(n)]
for _ in range(m):
  u,v,c=map(int,input().split())
  g[u-1][v-1]=g[v-1][u-1]=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])
for i in range(n):
  g[i][i]=0
ans=10**18
for v in itertools.permutations(point):
  tmp=0
  for i in range(r-1):
    tmp+=g[v[i]-1][v[i+1]-1]
  ans=min(ans,tmp)
print(ans)

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

from itertools import permutations
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
cost = np.ones((n,n))*float('inf')
for i in range(m):
    a,b,c = map(int,input().split())
    cost[a-1][b-1]=cost[b-1][a-1]=c
d = floyd_warshall(cost)
def main():
    m = float('inf')

    for j in permutations(r):
        l = 0
        for i in range(len(j)-1):
            s,t = j[i],j[i+1]
            l += d[s-1][t-1]
        if l<m:
            m = l
    print(int(m))


if __name__ == "__main__":
    main()

Solution (Python):
import itertools
import sys

N, M, R = map(int, input().split())
r = [int(i) for i in input().split()]
r.sort()
a = [[sys.maxsize] * N for i in range(N)]
for i in range(M):
	A, B, C = map(int, input().split())
	a[A - 1][B - 1] = C
	a[B - 1][A - 1] = C
for i in range(N):
	a[i][i] = 0
for i in range(N):
	for j in range(N):
		if a[j][i] == sys.maxsize:
			continue
		for k in range(N):
			if a[i][k] == sys.maxsize:
				continue
			a[j][k] = min(a[i][k] + a[j][i], a[j][k])
ans = sys.maxsize
for i in itertools.permutations(r):
	b, j = 0, 1
	while j < R:
		b += a[i[j - 1] - 1][i[j] - 1]
		j += 1
	ans = min(b, ans)
print(ans)

Solution (Python):
from itertools import permutations

N, M, R = map(int, input().split())
T = list(map(int, input().split()))
grid = [[float('inf')] * N for _ in range(N)]

for i in range(N):
    grid[i][i] = 0
for i in range(M):
    A, B, C = map(int, input().split())
    A -= 1; B -= 1
    if grid[A][B] > C:
        grid[A][B] = C
        grid[B][A] = C

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

ans = float('inf')
for path in permutations(T):
    cnt = 0
    for i in range(R - 1):
        s = path[i] - 1
        g = path[i + 1] - 1
        cnt += grid[s][g]
    ans = min(ans, cnt)

print(ans)

Solution (Python):
import itertools


def warshall_floyd(G):
    import copy
    ret = copy.deepcopy(G)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                ret[i][j] = min(ret[i][j], ret[i][k] + ret[k][j])
    return ret


N, M, R = map(int, input().split())
r = list(map(int, input().split()))
G = [[10 ** 10] * N for _ in range(N)]
for _ in range(M):
    A, B, C = map(int, input().split())
    G[A - 1][B - 1] = C
    G[B - 1][A - 1] = C
W, ans = warshall_floyd(G), 10 ** 10
for p in itertools.permutations(r, R):
    ans = min(ans, sum([W[p[i] - 1][p[i + 1] - 1] for i in range(R - 1)]))
print(ans)

Solution (Python):
import heapq
import itertools
n, m, r = map(int, input().split())
r = list(map(lambda x:int(x)-1, input().split()))
d = [[float('inf')]*n for _ in range(n)]
for _ in range(m):
  a, b, t = map(int, input().split())
  a -= 1
  b -= 1
  d[a][b] = t
  d[b][a] = t
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):
import itertools
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
r = [x - 1 for x in r]
d = [[float("inf")] * N for i in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = c


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

warshall_floyd(d)

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

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

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

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

for _ in range(M):
    A, B, C = list(map(int, input().split()))
    A -= 1
    B -= 1
    T[A][B] = T[B][A] = min(C, T[A][B])
for i in range(N):
    T[i][i] = 0





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


warshall_floyd(T, N)


ans = float("inf")

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

print(ans)

Solution (Python):
from sys import stdin
from itertools import permutations
def main():
    N,M,R = map(int,stdin.readline().split())
    r = list(map(int,stdin.readline().split()))
    r = tuple(map(lambda x: x-1,r))
    dist = [[2**60]*N for _ in range(N)]
    for _ in range(M):
        A,B,C = map(int,stdin.readline().split())
        A -= 1
        B -= 1
        dist[A][B] = C
        dist[B][A] = 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])
    dist = tuple(map(lambda x: tuple(x),dist))
    ans = 2**60
    for t in tuple(permutations(r,R)):
        tmp = 0
        for i in range(R-1):
            tmp += dist[t[i]][t[i+1]] 
        ans = min(ans,tmp)
    
    print(ans)

if __name__ == "__main__":
    main()

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

input = sys.stdin.readline
ans = -1

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

wf = floyd_warshall(csr_matrix((C, (A, B)), shape = (n, n)), directed=False)

for pi in permutations(r):
    cand = 0
    for r1, r2 in zip(pi, pi[1:]):
        cand += int(wf[r1-1][r2-1])
    if ans < 0 or ans > cand:
        ans = cand

print(ans)

Solution (Python):
import time
import itertools

def main():
    N,M,R = tuple([int(x) for x in input().split()])

    r = [int(x)-1 for x in input().split()]
    
    w_e = [tuple([int(x)for x in input().split()]) for _ in [0]*M]
    w_e = [(a-1,b-1,w) for (a,b,w) in w_e]


    g = Graph(list(range(N)),w_e)

    minimums = {}
    for r_i in r:
        minimums[r_i] = g.dijkstra(r_i)[0]

    bf = itertools.permutations(r)

    candidates = []
    for bf_i in bf:
        distance = 0
        for i in range(R-1):
            distance += minimums[bf_i[i]][bf_i[i+1]]
        candidates.append(distance)

    print(min(candidates))

def speedtest(func,*args):
    b = time.perf_counter()
    res = func(*args)
    e = time.perf_counter()
    elapsed = e-b
    print("{} (sec)".format(elapsed))

    return res

class Graph:
    def __init__(self,w_v,w_e):
        super().__init__()
        self.size = len(w_v)
        self.w_v = [v_i for v_i in w_v]
        self.w_e = [{} for _ in [0]*self.size]

        self.neighbor = [[] for _ in [0]*self.size]
        for a_i,b_i,w_i in w_e:
            self.w_e[a_i][b_i] = w_i
            self.w_e[b_i][a_i] = w_i

            self.neighbor[a_i].append(b_i)
            self.neighbor[b_i].append(a_i)

    def dijkstra(self,v_n):
        d = [-1]*self.size
        temp_d = [(10**9,i)for i in range(self.size)]
        temp_d[v_n] = (0,v_n)
        prev = [-1]*self.size

        q = set(range(self.size))
        
        while len(q)>0:
            u = min([temp_d[q_i] for q_i in q])[1]
            d[u] = temp_d[u][0]
            q.discard(u)
            for v in self.neighbor[u]:
                temp = temp_d[u][0]+self.w_e[u][v]
                if temp_d[v][0]>temp:
                    temp_d[v] = temp,v
                    prev[v] = u

        return d,prev

if __name__ == "__main__":
    main()

Solution (Python):
import time
import itertools

def main():
    N,M,R = tuple([int(x) for x in input().split()])

    r = [int(x)-1 for x in input().split()]
    
    w_e = [tuple([int(x)for x in input().split()]) for _ in [0]*M]
    w_e = [(a-1,b-1,w) for (a,b,w) in w_e]


    g = Graph(list(range(N)),w_e)

    minimums = {}
    for r_i in r:
        minimums[r_i] = g.dijkstra(r_i)[0]

    bf = itertools.permutations(r)

    candidates = []
    for bf_i in bf:
        distance = 0
        for i in range(R-1):
            distance += minimums[bf_i[i]][bf_i[i+1]]
        candidates.append(distance)

    print(min(candidates))

def speedtest(func,*args):
    b = time.perf_counter()
    res = func(*args)
    e = time.perf_counter()
    elapsed = e-b
    print("{} (sec)".format(elapsed))

    return res

class Graph:
    def __init__(self,w_v,w_e):
        super().__init__()
        self.size = len(w_v)
        self.w_v = [v_i for v_i in w_v]
        self.w_e = [{} for _ in [0]*self.size]

        self.neighbor = [[] for _ in [0]*self.size]
        for a_i,b_i,w_i in w_e:
            self.w_e[a_i][b_i] = w_i
            self.w_e[b_i][a_i] = w_i

            self.neighbor[a_i].append(b_i)
            self.neighbor[b_i].append(a_i)

    def dijkstra(self,v_n):
        d = [-1]*self.size
        temp_d = [(10**9,i)for i in range(self.size)]
        temp_d[v_n] = (0,v_n)
        prev = [-1]*self.size

        q = set(range(self.size))
        
        while len(q)>0:
            u = min([temp_d[q_i] for q_i in q])[1]
            d[u] = temp_d[u][0]
            q.discard(u)
            for v in self.neighbor[u]:
                temp = temp_d[u][0]+self.w_e[u][v]
                if temp_d[v][0]>temp:
                    temp_d[v] = temp,v
                    prev[v] = u

        return d,prev

if __name__ == "__main__":
    main()

Solution (Python):
import itertools
def warshall_floyd(g):
    for k in range(len(g)):
        for i in range(len(g)):
            for j in range(len(g)):
                g[i][j] = min(g[i][j], g[i][k]+g[k][j])
    return g

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

res = float('inf')
for l in itertools.permutations(lst):
    cnt = 0
    for i in range(1, len(l)):
        cnt += d[l[i-1]-1][l[i]-1]
    res = min(res, cnt)
print(res)

Solution (Python):
import itertools

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

r = list(map(int,input().split()))
for i in range(R):
    r[i] -= 1

inf = 10 ** 12

dp = [[inf]*N for i in range(N)]
for i 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])

l = list(range(R))
m = inf

for x in itertools.permutations(l,R):
    count = 0
    for i in range(len(l)-1):
        count += dp[r[x[i]]][r[x[i+1]]]
    m = min(count,m)

print(m)

Solution (Python):
import itertools
n, m, r = map(int, input().split())
d = [[float('inf')]*n for _ in range(n)]
rs = list(map(int, input().split()))
for _ in range(m):
  a, b, t = map(int, input().split())
  a -= 1
  b -= 1
  d[a][b] = t
  d[b][a] = t
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 p in itertools.permutations(rs):
  tmp = 0
  for i in range(len(p)-1):
    tmp += d[p[i]-1][p[i+1]-1]
  ans = min(ans, tmp)

print(ans)

Solution (Python):
from itertools import permutations

n, m, r = map(int, input().split())
A = list(map(int, input().split()))
d = [[1e18]*n for i in range(n)]
for i in range(m):
        a, b, c = map(int, input().split())
        d[a-1][b-1] = 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 = 1e18
for x in permutations(A):
        l = 0
        for i in range(r-1):
                l += d[x[i]-1][x[i+1]-1]
        ans = min(ans, l)
print(ans)

Solution (Python):

from itertools import permutations
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, M: int, R: int, r: "List[int]", A: "List[int]", B: "List[int]", C: "List[int]"):
    inf = float("inf")
    md = [[inf] * N for _ in range(N)]
    for i in range(N):
        md[i][i] = 0
    for Ai, Bi, Ci in zip(A, B, C):
        Ai -= 1
        Bi -= 1
        md[Ai][Bi] = md[Bi][Ai] = Ci
    for k in range(N):
        for i in range(N):
            for j in range(N):
                md[i][j] = min(md[i][j], md[i][k] + md[k][j])

    def dist(path):
        return sum(md[p1 - 1][p2 - 1] for p1, p2 in zip(path, path[1:]))

    print(min(dist(path) for path 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))
    solve(N, M, R, r, A, B, C)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
INF = 10**20
MOD = 10**9 + 7
from itertools import permutations

def main():
    n,m,r = map(int,input().split())
    dest = [int(i) - 1 for i in input().split()]
    dist = [[INF] * n for _ in range(n)]

    for _ in range(m):
        a,b,c = map(int,input().split())
        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 = INF
    for ptr in permutations(range(r)):
        tmp = 0
        for i in range(r - 1):
            tmp += dist[dest[ptr[i]]][dest[ptr[i + 1]]]
        ans = min (ans, tmp)
    
    print(ans)

if __name__=='__main__':
    main()

Solution (Python):
import itertools
 
n,m,r_ = map(int, input().split( ))
 
r = list(map(int, input().split( )))
for i in range(r_):
  	r[i] -= 1
d = [[10**10 for _ in range(n)] for i in range(n)]
 
for i in range(m):
    ai,bi,ci = map(int, input().split( ))
    ai-=1
    bi-=1
    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][k]+d[k][j],d[i][j])
ans= 100000000000000
for l in itertools.permutations(r,r_):
    tmp = 0
    for i in range(r_-1):
        tmp += d[l[i]][l[i+1]]
    ans = min(ans, tmp)
 
print(ans)

Solution (Python):
import itertools

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

INF = 10**10

d = [[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())
    a -= 1
    b -= 1
    if d[a][b] > c:
        d[a][b] = c
        d[b][a] = c


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



warshall(d)


ans = INF
for p in itertools.permutations(r):
    dist = 0
    for i in range(R-1):
        dist += d[p[i]-1][p[i+1]-1]

    if ans > dist:
        ans = dist

print(int(ans))

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

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

INF = 10**10

d = [[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())
    a -= 1
    b -= 1
    if d[a][b] > c:
        d[a][b] = c
        d[b][a] = c


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



warshall(d)


ans = INF
for p in itertools.permutations(r):
    dist = 0
    for i in range(R-1):
        dist += d[p[i]-1][p[i+1]-1]

    if ans > dist:
        ans = dist

print(int(ans))

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

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

INF = 10**10

d = [[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())
    a -= 1
    b -= 1
    if d[a][b] > c:
        d[a][b] = c
        d[b][a] = c






d = floyd_warshall(d)


ans = INF
for p in itertools.permutations(r):
    dist = 0
    for i in range(R-1):
        dist += d[p[i]-1][p[i+1]-1]

    ans = min(ans, dist)

print(int(ans))

Solution (Python):
import itertools
import math

n , m , r = map(int , input().split())
rr = list(map(int,input().split()))
q = len(rr)
INF = 1145141919810364364334

p = list(itertools.permutations(rr))

d = [[INF] * n for _ in range(n)]

for i in range(n):
    d[i][i] = 0
    
for i in range(m):
    a,b,c = map(int , input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
    
for k in range(n):
    for i in range(n):
        for j in range(n):
            d[i][j] = min( d[i][j] , d[i][k] + d[k][j] )
            
ans = INF
for i in p:
    temp = 0
    for j in range(q-1):
        temp += d[i[j] - 1][i[j+1] - 1]
        
    ans = min(ans , temp)
    
print(ans)

Solution (Python):


import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from itertools import permutations

n, m, R = na()
r = na()
abc = nan(m)
adj = [[0 for _ in range(n)] for _ in range(n)]
for i in range(m):
    a, b, c = abc[i]
    a -= 1
    b -= 1
    adj[a][b] = c
    adj[b][a] = c

dist = [[inf for _ in range(n)] for _ in range(n)]
for i in range(n):
    for j in range(n):
        if i == j:
            dist[i][j] = 0
        elif adj[i][j]:
            dist[i][j] = adj[i][j]

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

ans = inf
for p in permutations(r):
    res = 0
    for i in range(R - 1):
        f, t = p[i] - 1, p[i + 1] - 1
        res += dist[f][t]
    ans = min(ans, res)

print(ans)

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
from itertools import permutations
N,M,R=map(int,input().split())
r=list(map(lambda x: int(x)-1,input().split()))
l=tuple(permutations(range(R)))
C=[[10**8]*N for i in range(N)]
for i in range(M):
    a,b,c=map(int,input().split())
    C[a-1][b-1]=c
    C[b-1][a-1]=c
for i in range(N):
    C[i][i]=0
for i in range(N):
    for j in range(N):
        for k in range(N):
            C[j][k] = min(C[j][k],C[j][i] + C[i][k])
a=10**8
for i in l:
    t=0
    for j in range(R-1):
        t+=C[r[i[j]]][r[i[j+1]]]
    if a>t:
        a=t
print(a)

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

def Washall_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()))
f_inf = float('inf')
dist = [[f_inf]*n for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    dist[a][b] = c
    dist[b][a] = c

Washall_Floyd(dist)

S = list(itertools.permutations(R, r))
cnt = f_inf
for s in S:
  tmp = 0
  for i in range(len(s)-1):
    tmp += dist[s[i]-1][s[i+1]-1]
  cnt = min(cnt, tmp)
print(cnt)

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

def Washall_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()))
f_inf = float('inf')
dist = [[f_inf]*n for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    dist[a][b] = c
    dist[b][a] = c

Washall_Floyd(dist)
S = [i for i in itertools.permutations(R, r)]
cnt = f_inf
for s in S:
  tmp = 0
  for i in range(len(s)-1):
    tmp += dist[s[i]-1][s[i+1]-1]
  cnt = min(cnt, tmp)
print(cnt)

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

inf = 10 ** 18
d = [[inf 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())
    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 = 10 ** 18
for a in itertools.permutations(v):
    dis = 0
    for i in range(r-1):
        dis += d[a[i+1]-1][a[i]-1]
    ans = min(ans, dis)
print(ans)

Solution (Python):
N,M,R = map(int,input().split())
rs = 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 a,b,c in ABC:
    a,b = a-1,b-1
    d[a][b] = d[b][a] = c
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
import itertools
for ptn in itertools.permutations(rs):
    tmp = 0
    for a,b in zip(ptn,ptn[1:]):
        a,b = a-1,b-1
        tmp += d[a][b]
    ans = min(ans, tmp)
print(ans)