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 heapq
import itertools

def solve():
    N, M, _ = list(map(int, input().split()))
    R = list(map(int, input().split()))
    R = map(lambda x: x-1, R)
    G = [[] for i in range(N)]

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


    def dijkstra(d):
        que = []

        tar = -1
        for i in range(len(d)):
            if d[i] == -1:
                break
            if d[i] == 0:
                tar = i
            heapq.heappush(que, (d[i], i))

        while len(que) != 0:
            dist, node = heapq.heappop(que)
            for (cost, to) in G[node]:
                if d[to] > d[node] + cost:
                    d[to] = d[node] + cost
                    heapq.heappush(que, (dist + cost, to))

        return d


    ds = [[1e16 for i in range(N)] for j in range(N)]

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

    for i in range(N):
        ds[i] = dijkstra(ds[i])
        for j in range(N):
            ds[j][i] = ds[i][j]

    res = 1e16
    for r in list(itertools.permutations(R)):
        d = 0
        for i in range(len(r)-1):
            d += ds[r[i]][r[i+1]]
        res = min(res, d)

    return res

print(solve())

Solution (Python):
from itertools import permutations
N,M,R = map(int,input().split())
r = list(map(int,input().split()))
Ans = 10**10
A = [[10**10 for _ in range(N)] for _ in range(N)]
for _ in range(M):
    a,b,c = map(int,input().split())
    A[a-1][b-1] = c
    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])
P = list(permutations(r))
for p in P:
    d = 0
    for i in range(R-1):
        d += A[p[i]-1][p[i+1]-1]
    Ans = min(Ans,d)
print(Ans)

Solution (Python):
INF = 10**9

N, M, R = list(map(int, input().split()))
r = list(map(int, input().split()))
W = [[INF for _ in range(N+1)] for __ in range(N+1)]
for i in range(1, N+1):
    W[i][i] = 0

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

import heapq

for i in range(1, N+1):
    heap = []
    checked = [False for _ in range(N+1)]
    for j in range(1, i+1):
        heapq.heappush(heap, (W[i][j], j))
    while len(heap) > 0:
        wij, j = heapq.heappop(heap)
        if checked[j]:
            continue
        for k in range(i+1, N+1):
            wik = wij + W[j][k]
            if wik <= W[i][k]:
                W[i][k] = wik
                W[k][i] = wik
                heapq.heappush(heap, (wik, k))
        checked[j] = True

from itertools import permutations

ans = INF
for r_ in permutations(r):
    count = 0
    for i in range(R-1):
        x = W[r_[i]][r_[i+1]]
        if x >= INF:
            break
        count += x
        if count >= ans:
            break
    else:
        ans = count
print(ans)

Solution (Python):

from itertools import permutations
def inpl(): return tuple(map(int, input().split()))
 
INF = float("inf")
 
N, M, _ = inpl()
R = inpl()
G = [[INF]*(N+1) for _ in range(N+1)]

for _ in range(M):
    s, t, d = inpl()
    G[s][t] = d
    G[t][s] = d

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

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

G = WarshallFloyd(G)

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

Solution (Python):
from itertools import permutations

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
ARSP = [[float('inf')] * (N+1) for i in range(N+1)]
for i in range(M):
    a, b, c = map(int, input().split())
    ARSP[a][b] = c
    ARSP[b][a] = c


def warshall_floyd(adj_array):
    for k in range(len(adj_array)):
        for i in range(len(adj_array)):
            for j in range(len(adj_array)):
                if adj_array[i][k] + adj_array[k][j] < adj_array[i][j]:
                    adj_array[i][j] = min(adj_array[i][j], adj_array[i][k] + adj_array[k][j])
    return adj_array


ARSP = warshall_floyd(ARSP)


journey = list(permutations(r))

ans = float('inf')
for j in journey:
    cost = 0
    for i in range(1, R):
        if ARSP[j[i]][j[i-1]] == float('inf'):
            break
        cost += ARSP[j[i]][j[i-1]]
        if cost >= ans:
            break
    else:
        ans = cost

print(ans)

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

inf = float("inf")

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

vertices = [i for i in range(1, N+1)]
edge_costs = {i: defaultdict(int) for i in range(N+1)}

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

def dijkstra(s):
    dist = [inf for _ in range(N+1)]
    dist[s] = 0
    searched = [False for _ in range(N+1)]
    
    q = [] 
    heappush(q, (0, s))
    
    while len(q) != 0:
        d, v = heappop(q)
        
        
        if searched[v] or d > dist[v]:
            continue
            
        for u, c in edge_costs[v].items():
            temp = d + c
            if temp < dist[u]:
                dist[u] = temp
                heappush(q, (dist[u], u))
        
        searched[v] = True
        
        if sum(searched) == N: 
            break
    
    return [dist[t] for t in towns]

D = [dijkstra(t) for t in towns]

ans = min([sum([D[perm[i]][perm[i+1]] for i in range(R-1)]) for perm in itertools.permutations(range(R))])
print(ans)

Solution (Python):



import numpy as np
import itertools

def main():
    N, M, R = map(int, input().split())
    rs = list(map(int, input().split()))
    inf = float('inf')
    cost = [[inf]*N for _ in range(N)]

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

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

    
    ans = inf
    for route in itertools.permutations(rs):
        d = 0
        for i in range(R-1):
            d += cost[route[i]-1][route[i+1]-1]
            if d > ans:
                break
        ans = min(ans, d)
    
    print(int(ans))


if __name__=='__main__':
    main()

Solution (Python):


from itertools import permutations
import Queue

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

G = [[] for _ in xrange(N)]

for i in range(M):
    A, B, C = map(int, raw_input().split())
    A -= 1; B -= 1;
    G[A].append((B, C))
    G[B].append((A, C))


def dijkstra(s):
    d = [float("inf") for _ in xrange(N)]
    que = Queue.PriorityQueue()
    d[s] = 0
    que.put([0, s])

    while not que.empty():
        p = que.get()
        v = p[1]
        if d[v] < p[0]:
            continue
        for i, j in G[v]:
            if d[i] > d[v] + j:
                d[i] = d[v] + j
                que.put([d[i], i])
    return d

table = {}

for i in r:
    table[i] = dijkstra(i)

ans = float('inf')

for i in permutations(r):
    ans = min(ans, sum([table[i[j]][i[j+1]] for j in xrange(R-1)]))

print ans

Solution (Python):
from itertools import permutations
from heapq import heappush, heappop
def inpl(): return tuple(map(int, input().split()))
N, M, R = inpl()
inf = float("inf")
G = {n: {} for n in range(N+1)}
Des = inpl()

for _ in range(M):
    a, b, c = inpl()
    G[a][b] = c
    G[b][a] = c

def dijkstra(s):
    D = [inf for _ in range(N+1)]
    D[s] = 0
    HQ = [(0, s)]
    checked = [False for _ in range(N+1)]
    while HQ:
        c1, a = heappop(HQ)
        if D[a] < c1 or checked[a]: continue
        for b, c2 in G[a].items():
            if c1 + c2 < D[b]:
                D[b] = c1 + c2
                heappush(HQ, (D[b], b))
        checked[a] = True
    return [D[des] for des in Des]

C = []
for s in Des:
    C.append(dijkstra(s))

res = inf
for E in permutations(range(len(Des)), len(Des)):
    res = min(res, sum([C[E[i]][E[i+1]] for i in range(len(Des)-1)]))

print(res)

Solution (Python):
from itertools import permutations
from heapq import heappush, heappop
def inpl(): return tuple(map(int, input().split()))
N, M, R = inpl()
inf = float("inf")
G = {n: {} for n in range(N+1)}
Des = inpl()

for _ in range(M):
    a, b, c = inpl()
    G[a][b] = c
    G[b][a] = c

def dijkstra(s):
    D = [inf for _ in range(N+1)]
    D[s] = 0
    HQ = [(0, s)]
    checked = [False for _ in range(N+1)]
    n = N + 1
    while HQ:
        c1, a = heappop(HQ)
        if D[a] < c1 or checked[a]: continue
        for b, c2 in G[a].items():
            if c1 + c2 < D[b]:
                D[b] = c1 + c2
                heappush(HQ, (D[b], b))
        checked[a] = True
        n -= 1
        if not n: break
    return [D[des] for des in Des]

C = []
for s in Des:
    C.append(dijkstra(s))

res = inf
for E in permutations(range(len(Des)), len(Des)):
    res = min(res, sum([C[E[i]][E[i+1]] for i in range(len(Des)-1)]))

print(res)

Solution (Python):
from itertools import permutations
from heapq import heappush, heappop
def inpl(): return tuple(map(int, input().split()))
N, M, R = inpl()
inf = float("inf")
G = {n: {} for n in range(N+1)}
Des = inpl()

for _ in range(M):
    a, b, c = inpl()
    G[a][b] = c
    G[b][a] = c

def dijkstra(s):
    D = [inf for _ in range(N+1)]
    D[s] = 0
    HQ = [(0, s)]
    checked = [False for _ in range(N+1)]
    n = N + 1
    while HQ:
        c1, a = heappop(HQ)
        if D[a] < c1 or checked[a]: continue
        for b, c2 in G[a].items():
            if c1 + c2 < D[b]:
                D[b] = c1 + c2
                heappush(HQ, (D[b], b))
        checked[a] = True
        n -= 1
        if not n: break
    return [D[des] for des in Des]

C = []
for s in Des:
    C.append(dijkstra(s))

res = inf
for E in permutations(range(len(Des)), len(Des)):
    res = min(res, sum([C[E[i]][E[i+1]] for i in range(len(Des)-1)]))

print(res)

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

cost=[ [ float("inf") for i in range(N+1)] for i in range(N+1) ]
nl=[ [] for i in range(N+1) ]

for i in range(M):
	A,B,C=map(int, raw_input().split())
	cost[A][B]=C
	cost[B][A]=C
	nl[A].append(B)
	nl[B].append(A)


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


def Dij(start):

	
	d=[float("inf") for i in range(N+1)]
	d[start]=0
	q=[]
	heapq.heappush(q,(0,start))
	
	while len(q)!=0:
		tmp=heapq.heappop(q)
		u=tmp[1]

		for v in nl[u]:
			alt=d[u]+cost[u][v]
			if d[v]>alt:
				d[v]=alt
				heapq.heappush(q,(alt,v))
	return d


l=list(itertools.permutations(r))

C={}
for i in r:
	C[i]=Dij(i)


ans=float("inf")


for i in l:
	dist=0
	for j in range(R):
		if j==0:
			prev=i[j]
			continue
		cur=i[j]
		dist+=C[prev][cur]
		prev=cur
	ans=min(ans,dist)

print ans

Solution (Python):

from itertools import permutations, product
from heapq import heappush, heappop
def inpl(): return tuple(map(int, input().split()))
N, M, R = inpl()
inf = float("inf")
G = {n: {} for n in range(N+1)}
Des = inpl() 

for _ in range(M):
    a, b, c = inpl()
    G[a][b] = c
    G[b][a] = c

def dijkstra(s):
    D = [inf for _ in range(N+1)]
    D[s] = 0
    HQ = [(0, s)]
    checked = [False for _ in range(N+1)]
    while HQ:
        pc, a = heappop(HQ)
        if D[a] < pc or checked[a]:
            continue
        for b, c in G[a].items():
            if pc + c < D[b]:
                D[b] = pc + c
                heappush(HQ, (D[b], b))

        checked[a] = True
    return [D[des] for des in Des]

C = []
for s in Des:
    C.append(dijkstra(s))

res = inf
for E in permutations(range(len(Des)), len(Des)):
    res = min(res, sum([C[E[i]][E[i+1]] for i in range(len(Des)-1)]))            
        
print(res)

Solution (Python):

from itertools import permutations, product
def inpl(): return tuple(map(int, input().split()))
N, M, R = inpl()
inf = float("inf")
G = [[inf for _ in range(N+1)] for _ in range(N+1)]
D = inpl() 

for _ in range(M):
    a, b, c = inpl()
    G[a][b] = c
    G[b][a] = c

for n in range(N+1):
    G[n][n] = 0

for i ,j, k in product(range(1, N+1), repeat=3):
    G[j][k] = min(G[j][k], G[j][i] + G[i][k])

res = inf
for C in permutations(D, len(D)):
    res = min(res, sum([G[C[i]][C[i+1]] for i in range(len(D)-1)]))

print(res)

Solution (Python):
def Warshall_Floyd(edges,N):
  for k in range(N):
    for i in range(N):
      for j in range(N):
        edges[i][j]=min(edges[i][j],edges[i][k]+edges[k][j])
  return edges

import itertools
N, M, R = map(int,input().split())
r = list(map(int,input().split()))
A=[[float("inf") for i in range(N)] for j in range(N)]
for m in range(M):
  a, b, c = map(int,input().split())
  A[a-1][b-1] = c
  A[b-1][a-1] = c
A = Warshall_Floyd(A,N)

ans = float("inf")
for road in list(itertools.permutations(r)):
  length = 0
  for i in range(R-1):
    length += A[road[i]-1][road[i+1]-1]
  ans = min(ans, length)
print(ans)

Solution (Python):
import sys

import heapq
from collections import defaultdict, deque
import itertools

import itertools
from heapq import heappop, heappush
N, M, R = map(int, input().split())

r = [int(i) for i in input().split()]
mp = defaultdict(lambda:defaultdict(list))
for _ in range(M):
    a, b, c= map(int, input().split())
    mp[a][b] = c
    mp[b][a] = c

v = [[float('inf')] * (N + 1) for _ in [0] * (N + 1)]
def dijkstra(start):
    q = []
    global v
    heapq.heappush(q, (0, start))
    vv = v[start]
    vv[start] = 0
    while(q):
        vc, vs = heapq.heappop(q)
        for i in mp[vs]:
            vsc = mp[vs][i]
            cost = vv[i]
            newcost = vsc + vc
            if cost > newcost:
                vv[i] = newcost
                heapq.heappush(q, (newcost, i))

for i in r:
    dijkstra(i)

ans = float('inf')
for i in itertools.permutations(r):
    t_ans = 0
    for j in range(R - 1):
        t_ans += v[i[j]][i[j + 1]]
    if ans > t_ans:
        ans = t_ans
print(ans)

Solution (Python):
import numpy as np
import sys
import itertools

def read_data():
    try:
        LOCAL_FLAG
        import codecs
        import os

        lines = []
        file_path = os.path.join(os.path.dirname(__file__), 'data073.dat')
        with codecs.open(file_path, 'r', 'utf-8') as f:
            lines.append(f.readline().rstrip("\r\n"))
            N, M, R = list(map(int, lines[0].split()))
            for i in range(M+1):
                lines.append(f.readline().rstrip("\r\n"))


    except NameError:
        lines = []
        lines.append(input())
        N, M, R = list(map(int, lines[0].split()))
        for i in range(M+1):
            lines.append(input())

    return lines

def dis(D, town_list):
    total = 0
    for i in range(len(town_list)-1):
        total += D[town_list[i]][town_list[i+1]]
    return total


def Travel():

    raw_data = read_data()
    N, M, R = list(map(int, raw_data[0].split()))
    town_list = list(map(int, raw_data[1].split()))
    road_set = set([])

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


    for i in range(2, M+2):
        a, b, c = list(map(int, raw_data[i].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):
                dis_two_node = D[i][k] + D[k][j]
                if dis_two_node < D[i][j]:
                    D[i][j] = dis_two_node
                    D[j][i] = dis_two_node

   
    min_dis = float('inf')
    for each in itertools.permutations(town_list):
        min_dis = min(dis(D, each), min_dis)

    print(min_dis)




Travel()

Solution (Python):
from itertools import permutations

N, M, R = [int(n) for n in input().split()]
r = [int(n)-1 for n in input().split()]
d = [[100000000]*N for n in range(N)]

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

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

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

res = 1000000000
for perm in permutations(range(R)):
  s = 0
  for i in range(R-1):
    s += d[r[perm[i]]][r[perm[i+1]]]
  res = min(s, res)

print(res)

Solution (Python):
import itertools

def main():
    N, M, R = map(int, input().split())
    RR = tuple(map(int, input().split()))
    ABC = {tuple(map(int, input().split())) for _ in range(M)}

    dist = [[float('inf')] * (N + 1) for j in range(N + 1)]
    for a, b, c in ABC:
        dist[a][b] = dist[b][a] = c
        dist[a][a] = dist[b][b] = 0
    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])

    ans = float('inf')
    for r in itertools.permutations(RR):
        move = 0
        for i in range(R - 1):
            a = r[i]
            b = r[i+1]
            move += dist[a][b]
        ans = min(ans, move)

    print(ans)

main()

Solution (Python):
n, m, r = map(int, input().split())
*R, = map(int, input().split())
E = [[10**18]*n for i in range(n)]
for i in range(n):
    E[i][i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    E[a-1][b-1] = E[b-1][a-1] = c
for k in range(n):
    for i in range(n):
        for j in range(n):
            E[i][j] = min(E[i][j], E[i][k] + E[k][j])

memo = {}
ALL = 2**r-1
def dfs(state, pos):
    if (state, pos) in memo:
        return memo[state, pos]
    if state == ALL:
        return 0
    res = 10**18
    for i in range(r):
        if state & (1 << i) == 0:
            res = min(res, dfs(state | (1 << i), R[i]-1) + E[pos][R[i]-1])
    memo[state, pos] = res
    return res
print(min(dfs(0, i) for i in range(n)))

Solution (Python):


import sys

p=[0]*10000;mp=[];inf=65530060;v=[0]*1000;t=[0]*1000
 
 
ans=100000000

 
n,m,r=map(int,sys.stdin.readline().split(" "))



s=sys.stdin.readline().replace("\n","")

p=map(int,s.split(" "))


def dsss(x,now):
	global ans,v,p,t,mp
	if x==r+1:
		ans=min(ans,now)
		return 
	else :
		for i in range(r):
			if v[p[i]]==0 :
				v[p[i]]=1
				t[x]=p[i]
				if x==1:
					dsss(x+1,now)
				else :
					dsss(x+1,now+mp[p[i]-1][t[x-1]-1])
				v[p[i]]=0
	return 
 
 
for i in range(n+5):
	mp.append(range(n+5))
 
 
for i in range(n+5):
    for j in range(n+5):
            mp[i][j]=inf


for i in range(m):
	a,b,c=map(lambda x: int(x),sys.stdin.readline().split(" ",3))
	a-=1;b-=1;
	mp[a][b]=min(mp[a][b],c)
	mp[b][a]=min(mp[b][a],c)


for i in xrange(n):
	for j in xrange(n):
		for k in xrange(n):
			if mp[j][i]+mp[i][k]<mp[j][k]:
			    mp[j][k]=mp[j][i]+mp[i][k]

dsss(1,0)
 
print ans

Solution (Python):
import itertools

def main() :
    N, M, R = map(int, input().split())
    r = [a-1 for a in list(map(int, input().split()))]
    d = [[float('inf')]*N for _ in range(N)]

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

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

    for k in range(N):
        for i in range(N):
            for j in range(N):
                dd = d[i][k] + d[k][j]
                if dd < d[i][j]:
                    d[i][j] = dd

    ans = float("inf")

    for perm in itertools.permutations(r):
        a = 0
        for i in range(len(perm)-1):
            a += d[perm[i]][perm[i+1]]
        ans = min(a, ans)

    print(ans)
    
main()

Solution (Python):
from itertools import permutations
 
 
def closest_path_lens(idx___neigh_idxes__dists, idx1):
    INF = 100001 * 201 * 200
    nodes_nr = len(idx___neigh_idxes__dists)
    idx___visited = [False] * nodes_nr
    idx___dist = [INF] * nodes_nr
    idx___dist[idx1] = 0
    for _ in range(nodes_nr):
        curr_idx = -1
        curr_dist = INF
        for idx, dist in enumerate(idx___dist):
            if dist < curr_dist and not idx___visited[idx]:
                curr_idx = idx
                curr_dist = dist
        idx___visited[curr_idx] = True
        for neigh_idx, dist in idx___neigh_idxes__dists[curr_idx]:
            
            idx___dist[neigh_idx] = min(idx___dist[neigh_idx], curr_dist + dist)
    return idx___dist
 
 
towns_nr, roads_nr, towns_to_visit_nr = (int(x) for x in input().split())
towns_to_visit = [(int(x) - 1) for x in input().split()]
town_idx___neigh_idxes__dists = [set() for _ in range(towns_nr)]
for road_idx in range(roads_nr):
    idx1, idx2, dist = (int(x) for x in input().split())
    idx1 -= 1
    idx2 -= 1
    town_idx___neigh_idxes__dists[idx1].add((idx2, dist))
    town_idx___neigh_idxes__dists[idx2].add((idx1, dist))
ttv_idx___ttv_idx__dist = []
for ttv in towns_to_visit:
    town_idx___dist  = closest_path_lens(town_idx___neigh_idxes__dists, ttv)
    
    ttv_idx___dist = [town_idx___dist[idx] for idx in towns_to_visit]
    
    ttv_idx___ttv_idx__dist.append(ttv_idx___dist)
ans = 100001 * 201 * 200
for path in permutations(list(range(towns_to_visit_nr))):
    curr_ans = 0
    curr_idx = path[0]
    for ttv_idx in path:
        
        curr_ans += ttv_idx___ttv_idx__dist[curr_idx][ttv_idx]
        curr_idx = ttv_idx
    
    
    ans = min(ans, curr_ans)
print(ans)

Solution (Python):
from itertools import permutations

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

def main():
    n, m, r = input_list()
    rlist = input_list()
    rlist = [r-1 for r in rlist]
    d = [[float('inf')]*n for i in range(n)]
    for i in range(n):
        d[i][i] = 0
    
    for i in range(m):
        a, b, c = input_list()
        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):
                distance = d[i][k]+d[k][j]
                if d[i][j] > distance:
                    d[i][j] = distance

    ans = float('inf')
    for p in permutations(rlist):
        distance = 0
        for i in range(r-1):
            distance += d[p[i]][p[i+1]]

        if ans > distance:
            ans = distance

    print(ans)

main()

Solution (Python):
from collections import defaultdict
from itertools import product, groupby, permutations
from math import pi
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = 10 ** 10


def main():
    N, M, R = map(int, input().split())
    r_list = list(map(int, input().split()))
    dp = [[float("inf")] * (N + 1) for _ in range(N + 1)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        dp[A][B] = dp[B][A] = C

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

    for m in range(N + 1):
        for s in range(N + 1):
            for e in range(N + 1):
                dist = dp[s][m] + dp[m][e]
                if dist < dp[s][e]:
                    dp[s][e] = dist

    ans = float("inf")
    for p in permutations(r_list, len(r_list)):
        total = 0
        for i in range(len(p) - 1):
            total += dp[p[i]][p[i + 1]]
            if total >= ans:
                break
        else:
            if total < ans:
                ans = total
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
from itertools import permutations
 
 
def warshallFloyd(V, dp):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                
                new_dist = dp[i][k] + dp[k][j]
                if dp[i][j] > new_dist:
                    dp[i][j] = new_dist
 
 
def main():
    N, M, R = [int(x) for x in input().split()]
    destinations = [int(x) for x in 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):
        f, t, d = [int(x) for x in input().split()]
        dp[f][t] = dp[t][f] = d
 
    warshallFloyd(N+1, dp)
 
    minimum_cost = float('inf')
    for route in permutations(destinations, len(destinations)):
        cost = 0
        while len(route) > 1:
            f, t = route[0], route[1]
            cost += dp[f][t]
            if cost > minimum_cost:
                break
            route = route[1:]
        if cost < minimum_cost:
            minimum_cost = cost
    print(minimum_cost)
 
 
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

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

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

def md(beg):
  d = [1001001001] * N
  done = [False] * N
  d[beg] = 0
  while True:
    cur = 1001001001
    pos = -1
    for i in range(N):
      if not done[i] and cur > d[i]:
        cur = d[i]
        pos = i
    if pos == -1:
      break
    done[pos] = True
    for i in range(N):
      d[i] = min(d[i], d[pos] + g[pos][i])
  return d

for i in range(R):
  g[r[i]] = md(r[i])

ans = 1001001001
for p in itertools.permutations(r):
  cur = 0
  for i in range(1, R):
    cur += g[p[i-1]][p[i]]
  ans = min(ans, cur)
print(ans)

Solution (Python):

"""
https://beta.atcoder.jp/contests/abc073/tasks/abc073_d
"""
from itertools import permutations


def warshallFloyd(V, dp):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                
                new_dist = dp[i][k] + dp[k][j]
                if dp[i][j] > new_dist:
                    dp[i][j] = new_dist


def main():
    N, M, R = [int(x) for x in input().split()]
    destinations = [int(x) for x in 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):
        f, t, d = [int(x) for x in input().split()]
        dp[f][t] = dp[t][f] = d

    warshallFloyd(N+1, dp)

    minimum_cost = float('inf')
    for route in permutations(destinations, len(destinations)):
        cost = 0
        while len(route) > 1:
            f, t = route[0], route[1]
            cost += dp[f][t]
            if cost > minimum_cost:
                break
            route = route[1:]
        if cost < minimum_cost:
            minimum_cost = cost
    print(minimum_cost)


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import permutations

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

def main() :
    n, m ,r = input_list()
    road = input_list()
    road = [x-1 for x in road]
    d = [[float('inf')] * n for i in range(n)]
    for i in range(n) :
        d[i][i] = 0
    for i in range(m) :
        a, b, c = input_list()
        a -= 1
        b -= 1
        d[a][b] = c
        d[b][a] = c

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

    ans = float('inf')
    for p in permutations(road) :
        dist = 0
        for i in range(r-1) :
            dist += d[p[i]][p[i+1]]
        if ans > dist :
            ans = dist

    print(ans)

main()

Solution (Python):
import scipy.sparse as S
import itertools as i
m=lambda:map(int,input().split())
N,M,_=m()
R=m()
G=S.dok_matrix((N,N))
G.update((lambda x:((next(x)-1,next(x)-1),next(x)))(m())for _ in range(M))
G=S.csgraph.floyd_warshall(G.tocsr(),directed=0)
print(int(min(sum(G[a-1,b-1]for a,b in zip(p[1:],p))for p in i.permutations(R))))

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

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

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

G = np.zeros((N,N))

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

floyd_warshall(G, directed=False, overwrite=True)

def it2():
  from itertools import permutations
  for p in permutations(R):
    pp = iter(p)
    next(pp)
    yield sum(G[a,b] for a,b in zip(p,pp))

print(int(min(it2())))

Solution (Python):
from itertools import permutations
import sys

def main():
    
    N, M, R = map(int, sys.stdin.readline().split())
    r = [i - 1 for i in map(int, sys.stdin.readline().split())]
    
    d = [[float('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,sys.stdin.readline().split())
        d[a-1][b-1] = c
        d[b-1][a-1] = c
        
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
    
    ans = 10**12
    
    for each in permutations(r):
        t_dis = 0
        for i in range(R-1):
            t_dis += d[each[i]][each[i+1]]  
        
        ans = min(ans, t_dis)
    
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import itertools
import sys

def main():
    N, M, R = map(int, sys.stdin.readline().split())
 
    r = [i - 1 for i in map(int, sys.stdin.readline().split())]
 
    d = [[float('inf')]*N for _ 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
 
    for a in range(N):
        d[a][a] = 0
 
    res = float('inf')
 
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if d[i][k]+d[k][j] < d[i][j]:
                    d[i][j] = d[i][k]+d[k][j]
 
    for perm in itertools.permutations(r):
        a = 0
        for i in range(len(perm)-1):
            a += d[perm[i]][perm[i+1]]
        res = min(a, res)
 
    print(res)
 
if __name__ == '__main__':
    main()