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


from itertools import permutations

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


for k in range(N):
    for i in range(N):
        for j in range(N):
            
            if i == j:
                G[i][j] = 0
            else:
                G[i][j] = min(G[i][j], G[i][k] + G[k][j])

ans = float('inf')

for p in permutations(r):
    sm = 0
    
    for i in range(1, len(p)):
        sm += G[p[i-1]-1][p[i]-1]
    ans = min(sm, ans)
print(ans)

Solution (Python):
from itertools import permutations
N, M, Rn = map(int, input().split())
R = list(map(lambda x: int(x) - 1, input().split()))

G = [[float('inf')] * N for i in range(N)]
for m in range(M):
    a, b, c = map(int, input().split())
    a, b = 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 = float('inf')
for route in permutations(R):
    tmp = 0
    for i in range(Rn - 1):
        tmp += G[route[i]][route[i + 1]]
    ans = min(ans, tmp)

print(ans)

Solution (Python):
def washall_floyd(graph):
    num_v = len(graph)
    for k in range(num_v):
        for i in range(num_v):
            for j in range(num_v):
                if graph[i][j] > graph[i][k] + graph[k][j]:
                    graph[i][j] = graph[i][k] + graph[k][j]
    return graph


n, m, r = map(int, input().split())
r_list = list(map(int, input().split()))
graph = [[float("inf") for _ in range(n)] for _ in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    graph[a - 1][b - 1] = c
    graph[b - 1][a - 1] = c

graph = washall_floyd(graph)
result = float("inf")
import itertools
permi = itertools.permutations(r_list)
for per in permi:
    r = 0
    start = per[0] - 1
    for p in per[1:]:
        end = p - 1
        r += graph[start][end]
        start = p - 1
    result = min(r, result)
print(result)

Solution (Python):
def washall_floyd(graph):
    num_v = len(graph)
    for k in range(num_v):
        for i in range(num_v):
            for j in range(num_v):
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
    return graph


n, m, r = map(int, input().split())
r_list = list(map(int, input().split()))
graph = [[float("inf") for _ in range(n)] for _ in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    graph[a - 1][b - 1] = c
    graph[b - 1][a - 1] = c

graph = washall_floyd(graph)
result = float("inf")
import itertools
permi = itertools.permutations(r_list)
for per in permi:
    r = 0
    start = per[0] - 1
    for p in per[1:]:
        end = p - 1
        r += graph[start][end]
        start = p - 1
    result = min(r, result)
print(result)

Solution (Python):
import heapq
import itertools

def dijkstra(graph, node, start):
    dist = [float("inf") for _ in range(node)]

    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while q:
        cost, cur_node = heapq.heappop(q)

        if dist[cur_node] < cost:
            continue

        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heapq.heappush(q, (dist[nex_node], nex_node))

    return dist

n, m, R = map(int, input().split())
r = list(map(int, input().split()))
adj = [[] for _ in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    adj[a].append((c, b))
    adj[b].append((c, a))
shortest = []
for i in range(n):
    shortest.append(dijkstra(adj, n, i))
ans = float("INF")
for i in itertools.permutations(r):
    s = 0
    for j in range(R - 1):
        s += shortest[i[j] - 1][i[j + 1] - 1]
    ans = min(ans, s)
print(ans)

Solution (Python):
import itertools
import heapq

V, E, R = [int(_) for _ in input().split()]
r = [int(_) - 1 for _ in input().split()]  
G = {}
for i in range(V):
    G[i] = {}
    G[i][i] = 0

for _ in range(E):
    s, t, c = [int(_) for _ in input().split()]
    s -= 1  
    t -= 1  
    G[s][t] = c
    G[t][s] = c

INF = float('inf')

Ds = []
for r_index in range(R):
    que = []
    d = 0
    i = r[r_index]
    D = [INF] * V
    D[i] = 0
    used = [False] * V
    used[i] = True

    while True:
        for j in G[i].keys():
            heapq.heappush(que, (d + G[i][j], j))
        v = -1
        while que:
            d, j = heapq.heappop(que)
            if not used[j]:
                v = j
                break
        if v == -1:
            break
        else:
            used[v] = True
            D[v] = d
            i = v
    Ds += [D]
ans = INF
for array in itertools.permutations(range(R), R):
    d = 0
    for i in range(R - 1):
        d += Ds[array[i]][r[array[i + 1]]]
    ans = min(ans, d)
print(ans)

Solution (Python):
from itertools import permutations
import sys
def main():
    N, M, R = map(int, input().split())
    rs = [x - 1 for x in map(int, input().split())]
    
    dist = [[float('inf')] * (N) for _ in range(N)]
    for e in sys.stdin:
        A, B, C = map(int, e.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[i][k] + dist[k][j]
    
    ans = float('inf')
    for p in permutations(rs):
        ans = min(ans, sum(dist[u][v] for u, v in zip(p, p[1:])))
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
from itertools import permutations
import sys
import gc
def main():
    N, M, R = map(int, input().split())
    rs = [x - 1 for x in map(int, input().split())]
    
    dist = [[float('inf')] * (N) for _ in range(N)]
    for e in sys.stdin:
        A, B, C = map(int, e.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[i][k] + dist[k][j]
    
    ans = float('inf')
    for p in permutations(rs):
        tmp = 0
        for u, v in zip(p, p[1:]):
            tmp += dist[u][v]
            if tmp > ans:
                break
        else:
            ans = tmp
    print(ans)
if __name__ == '__main__':
    gc.disable()
    main()

Solution (Python):
from itertools import permutations
import sys
def main():
    N, M, R = map(int, input().split())
    rs = [x - 1 for x in map(int, input().split())]
    
    dist = [[float('inf')] * (N) for _ in range(N)]
    for e in sys.stdin:
        A, B, C = map(int, e.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[i][k] + dist[k][j]
    
    ans = float('inf')
    for p in permutations(rs):
        tmp = 0
        for u, v in zip(p, p[1:]):
            tmp += dist[u][v]
            if tmp > ans:
                break
        else:
            ans = tmp
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict
from heapq import heappop, heappush
import itertools
n, m, r = map(int, input().split())
rli = list(map(int, input().split()))
d = []
for i in range(m):
    d.append([int(m) for m in input().split()])


dist = d

class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        
        
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        
        self.prev = defaultdict(lambda: None)

        
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

inputs = dist

g = Graph()
for src, dst, weight in inputs:
    g.add_edge(src, dst, weight)
    g.add_edge(dst, src, weight)
spdi = {}

for i in rli:
    for j in rli:
        d = Dijkstra(g, i)
        sp = format(d.shortest_distance(j))
        spdi[str(j) + "+" + str(i)] = int(sp)
realroot = float("INF")
for pa in itertools.permutations(rli, len(rli)):
    root = 0
    for i in range(1, len(pa)):
        root += spdi[str(pa[i]) + "+" + str(pa[i - 1])]
    if root < realroot:
        realroot = root

print(realroot)

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

N, M, R = list(map(int, input().split()))
Rlist = list(map(int, input().split()))
RX = []

graph = defaultdict(list)

for i in range(M):
	a, b, w = list(map(int, input().split()))
	graph[a - 1].append([b - 1, w])
	graph[b - 1].append([a - 1, w])


for i in range(R):
	dist_node = [float("inf") for j in range(N)]
	dist_node[Rlist[i] - 1] = 0
	Q = []
	heapq.heappush(Q, (dist_node[Rlist[i] - 1], Rlist[i] - 1))

	while Q:
		dis, v = heapq.heappop(Q)
		if dist_node[v] < dis:
			continue
		for u, w in graph[v]:
			alt = dis + w
			if dist_node[u] > alt:
				dist_node[u] = alt
				heapq.heappush(Q, (alt, u))
	RX.append([dist_node[Rlist[k] - 1] for k in range(R)])
	
ans = float("inf")
nl = [i for i in range(R)]
pl = list(itertools.permutations(nl, R))
for i in pl:
	xx = 0
	for j in range(R - 1):
		xx += RX[i[j]][i[j + 1]]

	if xx < ans: 
		ans = xx

print(ans)

Solution (Python):

from scipy.sparse.csgraph import floyd_warshall
import itertools

from pprint import pprint as pp
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
ABC = [list(map(int, input().split())) for _ in range(M)]

graph = [[float('inf') for _ in range(N)] for _ in range(N)]
for i in range(M):
    x, y, c = ABC[i]
    x -= 1
    y -= 1
    graph[x][y] = c
    graph[y][x] = c

dist = floyd_warshall(graph, directed=False)

ans = []
for rlist in itertools.permutations(r, len(r)):
    tmp = 0
    for r,n in zip(rlist,rlist[1:]):
        tmp += dist[r-1,n-1]
    ans.append(tmp)

print(int(min(ans)))

Solution (Python):
from scipy.sparse.csgraph import floyd_warshall
from itertools import permutations
n,m,r=map(int, input().split())
s=[[10**9]*n for i in range(n)]
t=list(map(int, input().split()))
for i in range(m):
    a,b,c=map(int, input().split())
    s[a-1][b-1]=c
    s[b-1][a-1]=c

s=floyd_warshall(s)   
ans=float('inf')
for i in permutations(t):
    an=0
    for j in range(r-1):
        an+=s[i[j]-1][i[j+1]-1]
    ans=min(ans,an)
print(int(ans))

Solution (Python):
n,m,r=map(int, input().split())
s=[[10**9]*n for i in range(n)]
t=list(map(int, input().split()))
for i in range(m):
    a,b,c=map(int, input().split())
    s[a-1][b-1]=c
    s[b-1][a-1]=c
 
for k in range(n):
    for i in range(n):
        for j in range(n):
            s[i][j]=min(s[i][j],s[i][k]+s[k][j])
ans=float('inf')
from itertools import permutations
for i in permutations(t):
    an=0
    for j in range(r-1):
        an+=s[i[j]-1][i[j+1]-1]
    ans=min(ans,an)
print(ans)

Solution (Python):
import sys
import heapq
import math
import itertools

input = sys.stdin.readline

def make_Graph(N, edges):
    graph = {}
    for i in range(N):
        graph[i] = {}
        for j in range(N):
            graph[i][j] = 0
    for edge in edges:
        a, b, c = edge
        graph[a][b] = c
        graph[b][a] = c
    return graph

def Dijkstra(graph, start):
    N = len(graph)
    d = {}
    prev = {}
    for i in range(N):
        prev[i] = None
        if i == start:
            d[i] = 0
        else:
            d[i] = float('inf')
    Q = []
    heapq.heappush(Q, (0, start))
    while Q:
        d_u, u = heapq.heappop(Q)
        if d[u] < d_u:
            continue
        for i in range(N):
            if graph[u][i]:
                temp = d_u + graph[u][i]
                if d[i] > temp:
                    d[i] = temp
                    prev[i] = u
                    heapq.heappush(Q, (d[i], i))
    return (d, prev)

def saitan(start, goal, d, prev):
    temp = goal
    res = [goal]
    while True:
        res.append(prev[temp])
        if prev[temp] == start:
            break
        else:
            temp = prev[temp]
    return res

N,M,rr = (int(i) for i in input().split())
R = [int(i)-1 for i in input().split()]
edges = []
for i in range(M):
    a,b,c = (int(i) for i in input().split())
    edges.append((a-1, b-1, c))

graph = make_Graph(N, edges)

r_edges = []
for r1 in R:
    d, prev = Dijkstra(graph, r1)
    for r2 in R:
        (a,b,c) = r1, r2, d[r2]
        r_edges.append((a,b,c))

r_graph = make_Graph(N, r_edges)

reslis = []
for LL in list(itertools.permutations(R)):
    res = 0
    for i in range(len(LL)-1):
        a, b = (LL[i], LL[i + 1])
        res += r_graph[a][b]
    reslis.append(res)

reslis.sort()
res = reslis[0]
print(res)

Solution (Python):
import sys
import heapq
import math
import itertools

input = sys.stdin.readline

def make_Graph(N, edges):
    graph = {}
    for i in range(N):
        graph[i] = {}
        for j in range(N):
            graph[i][j] = 0
    for edge in edges:
        a, b, c = edge
        graph[a][b] = c
        graph[b][a] = c
    return graph

def Dijkstra(graph, start):
    N = len(graph)
    d = {}
    prev = {}
    for i in range(N):
        prev[i] = None
        if i == start:
            d[i] = 0
        else:
            d[i] = float('inf')
    Q = []
    heapq.heappush(Q, (0, start))
    while Q:
        d_u, u = heapq.heappop(Q)
        if d[u] < d_u:
            continue
        for i in range(N):
            if graph[u][i]:
                temp = d_u + graph[u][i]
                if d[i] > temp:
                    d[i] = temp
                    prev[i] = u
                    heapq.heappush(Q, (d[i], i))
    return (d, prev)

def saitan(start, goal, d, prev):
    temp = goal
    res = [goal]
    while True:
        res.append(prev[temp])
        if prev[temp] == start:
            break
        else:
            temp = prev[temp]
    return res

N,M,rr = (int(i) for i in input().split())
R = [int(i)-1 for i in input().split()]
edges = []
for i in range(M):
    a,b,c = (int(i) for i in input().split())
    edges.append((a-1, b-1, c))

graph = make_Graph(N, edges)

r_edges = []
for r1 in R:
    d, prev = Dijkstra(graph, r1)
    for r2 in R:
        (a,b,c) = r1, r2, d[r2]
        r_edges.append((a,b,c))

r_graph = make_Graph(N, r_edges)

reslis = []
for LL in list(itertools.permutations(R)):
    res = 0
    for i in range(len(LL)-1):
        a, b = (LL[i], LL[i + 1])
        res += r_graph[a][b]
    reslis.append(res)

reslis.sort()
res = reslis[0]
print(res)

Solution (Python):
import sys,itertools as o,scipy.sparse as s;_,r,*t=[map(int,i.split())for i in sys.stdin];a,b,c=zip(*t);l=s.csgraph.dijkstra(s.csr_matrix((c,(a,b)),[201]*2),0);print(min(sum(int(l[i][j])for i,j in zip(a,a[1:]))for a in o.permutations(r)))

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

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


def iter_patterns(l):
    if len(l) == 1:
        return [l]
    patterns = []
    for i in range(len(l)):
        patterns += [[l[i]] + p for p in iter_patterns(l[:i] + l[i+1:])]
    return patterns


def main():
    N, M, R = map(int, input().split())
    r = list(map(int, input().split()))
    paths = [[float("inf")] * N for _ in range(N)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        paths[A-1][B-1] = C
        paths[B-1][A-1] = C
    for i in range(N):
        paths[i][i] = 0
    warshall_floyd(paths, N)
    retval = float("inf")
    for p in iter_patterns(r):
        dist = 0
        for i in range(R-1):
            dist += paths[p[i]-1][p[i+1]-1]
        retval = min(retval, dist)
    print(retval)


if __name__ == "__main__":
    main()

Solution (Python):
import itertools
N,M,R=map(int,input().split())
towns=[int(i) for i in input().split()]
path=[[10**20]*N for i in range(N)]
for i in range(N):
  path[i][i]=0
for i in range(M):
  a,b,c=map(int,input().split())
  path[a-1][b-1]=c
  path[b-1][a-1]=c

for k in range(N):
  for i in range(N):
    for j in range(i):
      path[i][j]=min(path[i][j],path[i][k]+path[k][j])
      path[j][i]=path[i][j]   
Roots=list(itertools.permutations(towns))
ans=10**20
s=0
for r in Roots:
  for n in range(R-1):
    s+=path[r[n]-1][r[n+1]-1]
  ans=min(ans,s)
  s=0
print(ans)

Solution (Python):
from itertools import permutations

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

edges=[[inf for i in range(n+1)] for i in range(n+1)]

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


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


ans = inf
for i in permutations(R):
  tmp = 0
  for j in range(r-1):
    tmp += edges[i[j]][i[j+1]]
  ans = min(tmp, ans)

print(ans)

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


import itertools
import queue
G=[]

inf=3*10**15
V, E, R=map(int,input().strip().split(' '))
rlis=list(map(int,input().strip().split(' ')))

cost=[[inf]*V for i in range(V)]
for i in range(E):
    fr, to, co=map(int,input().strip().split(' '))
    cost[fr-1][to-1]=co
    cost[to-1][fr-1]=co
def dijkstra(s):
    d=[inf]*V
    used=[False]*V
    d[s]=0
    while True:
        v=-1
        for u in range(V):
            if used[u]==False and(v==-1 or d[u]<d[v]):
                v=u
        if v==-1:
            break
        used[v]=True
        for u in range(V):
            d[u]=min(d[u],d[v]+cost[v][u])
    return d

dist=[None] * V
for i in rlis:
    dist[i-1]=dijkstra(i-1)

ans=inf
for rperm in itertools.permutations(rlis):
    a_tmp=0
    for j in range(R-1):
        a_tmp+=dist[rperm[j]-1][rperm[j+1]-1]
    ans=min(ans,a_tmp)

print(ans)

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

V = [ i for i in range(1,N+1)]
E =[[100000000 for j in range(N+1)] for i in range(N+1)]
for i in range(N+1):
    E[i][i] = 0

for i in range(M):
    E[ABC[i][0]][ABC[i][1]] = ABC[i][2]
    E[ABC[i][1]][ABC[i][0]] = ABC[i][2]


def warshall_floyd(V,E):
    d = E
    for k in V:
        for i in V:
            for j in V:
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]

    return d

W = warshall_floyd(V,E)

import itertools
ans = 10000000000000
for val in list(itertools.permutations(r,len(r))):
    tmp = 0
    for i in range(len(val) - 1):
        tmp += W[val[i]][val[i+1]]
    if ans > tmp:
        ans = tmp
print(ans)

Solution (Python):
import sys, heapq, itertools
input = sys.stdin.readline
inf = float('inf')
N, M, R = map(int, input().split())
r = list(map(lambda x: int(x)-1, input().split()))

sec = [[inf] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j:
            sec[i][j] == 0
for abc in [list(map(int, input().split())) for _ in range(M)]: 
    sec[abc[0]-1][abc[1]-1] = abc[2]
    sec[abc[1]-1][abc[0]-1] = abc[2]
def marsh():
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if sec[i][j] > sec[i][k] + sec[k][j]:
                    sec[i][j] = sec[i][k] + sec[k][j]
marsh()
cost = inf
for perm in itertools.permutations(r):
    temp = 0
    for i in range(R-1):
        temp += sec[perm[i]][perm[i+1]]
    if temp < cost:
        cost = temp

print(cost)

Solution (Python):
def wf(N, cost):
    for k in range(N):
        for i in range(N):
            c_ik = cost[i][k]
            for j, (c_kj, c_ij) in enumerate(zip(cost[k], cost[i])):
                temp = c_ik + c_kj
                if temp < c_ij:
                    cost[i][j] = temp

import sys
import itertools
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
cost = [[float("inf")] * N for _ in range(N)]

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

for _ in range(M):
    A, B, C = map(int, sys.stdin.readline().split())
    cost[A - 1][B - 1] = C
    cost[B - 1][A - 1] = C

wf(N, cost)

ans = float('inf')
for place in itertools.permutations(r):
    temp_cost = 0
    current_place = place[0]
    for next_place in place[1:]:
        temp_cost += cost[current_place - 1][next_place - 1]
        current_place = next_place

    if temp_cost < ans:
        ans = temp_cost

print(ans)

Solution (Python):
from itertools import permutations

def wfa(N):
    for i in range(N + 1):
        for j in range(N + 1):
            w_ji = way[j][i]
            for k, (w_ik, w_jk) in enumerate(zip(way[i], way[j])):
                if k == 0:
                    continue
                tmp = w_ji + w_ik
                if w_jk > tmp:
                    way[j][k] = tmp


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

way = [[float("inf") if i != j else 0 for i in range(N + 1)] for j in range(N + 1)]
for m in range(M):
    a, b, c = map(int, input().split())
    way[a][b] = c
    way[b][a] = c

wfa(N)

ans = float("inf")
for path in permutations(r):
    time = 0
    for i in range(len(path) - 1):
        time += way[path[i]][path[i + 1]]
    ans = min(ans, time)
print(ans)

Solution (Python):
def wf(N, cost):
    for k in range(N):
        for i in range(N):
            c_ik = cost[i][k]
            for j, (c_kj, c_ij) in enumerate(zip(cost[k], cost[i])):
                temp = c_ik + c_kj
                if temp < c_ij:
                    cost[i][j] = temp

import sys
import itertools
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
cost = [[float("inf")] * N for _ in range(N)]
for _ in range(M):
    A, B, C = map(int, sys.stdin.readline().split())
    cost[A - 1][B - 1] = C
    cost[B - 1][A - 1] = C

wf(N, cost)

ans = float('inf')
for place in itertools.permutations(r):
    temp_cost = 0
    current_place = place[0]
    for next_place in place[1:]:
        temp_cost += cost[current_place - 1][next_place - 1]
        current_place = next_place

    if temp_cost < ans:
        ans = temp_cost

print(ans)

Solution (Python):



import sys
fin = sys.stdin.readline
from itertools import permutations


def warshall_floyd_int(adj, w):
    num_vertices = len(adj)
    dp = [[float('inf')] * num_vertices for _ in range(num_vertices)]
    for u in range(num_vertices):
        dp[u][u] = 0
        for v in adj[u]:
            dp[u][v] = w[u][v]

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


N, M, R = [int(elem) for elem in fin().split()]
r_list = [int(elem) - 1 for elem in fin().split()]
assert len(r_list) == R

adj = [[] for _ in range(N)]
w = [[None] * N for _ in range(N)]

for _ in range(M):
    A, B, C = [int(elem) for elem in fin().split()]
    A -= 1
    B -= 1
    adj[A].append(B)
    adj[B].append(A)
    w[A][B] = C
    w[B][A] = C


shortest_distances = warshall_floyd_int(adj, w)



min_distance = float('inf')
for permutation in permutations(r_list):
    distance = 0
    for i, city in enumerate(permutation[:-1]):
        next_city = permutation[i + 1]
        distance += shortest_distances[city][next_city]
    min_distance = min(min_distance, distance)
print(min_distance)

Solution (Python):
from itertools import permutations

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

INF = 10 ** 9

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

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

for i in range(R):
    r[i] -= 1

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



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

ans = INF
for x in permutations(r):
    temp = 0
    for i in range(R-1):
        temp += d[x[i]][x[i+1]]
    ans = min(temp, ans)

print(ans)

Solution (Python):
import heapq
INF=10**15
class weighted_graph():
    Vertex= 1
    AdjList=[dict() for i in range(Vertex)]
    Edge=[]
    directed=False
    def __init__(self,size,directed=False):
        self.directed=directed
        self.Vertex=size
        self.AdjList=[dict() for i in range(self.Vertex)]
    def add_edge(self,start,finish,weight):
        self.AdjList[start][finish]=weight
        self.Edge.append((start,finish,weight))
        if not(self.directed):
            self.AdjList[finish][start]=weight
    def dijkstra(self, st):
        dist=[INF for i in range(N)]
        dist[st]=0
        q=[]
        heapq.heappush(q,(0,st))
        while (len(q)!=0):
            prc,src=heapq.heappop(q)
            if dist[src]<prc:
                continue
            for dest in self.AdjList[src]:
                cost=self.AdjList[src][dest]
                if dist[dest]>dist[src]+cost:
                    dist[dest]=dist[src]+cost
                    heapq.heappush(q,(dist[dest],dest))                
        return dist
    def Warshall_Floyd(self):
        d=[[INF for i in range(self.Vertex)] for i in range(self.Vertex)]
        for seq in self.Edge:
            d[seq[0]][seq[1]]=seq[2]
            if not(self.directed):
                d[seq[1]][seq[0]]=seq[2]
        for k in range(self.Vertex):
            for i in range(self.Vertex):
                for j in range(self.Vertex):
                    if d[i][j]>d[i][k]+d[k][j]:
                        d[i][j]=d[i][k]+d[k][j]
        return d
import itertools
N,M,R=map(int,input().split())
r=[int(i)-1 for i in input().split()]
G=weighted_graph(N,directed=False)
for i in range(M):
    a,b,c=map(int,input().split())
    G.add_edge(a-1,b-1,c)
dist=G.Warshall_Floyd()
S=itertools.permutations(r,R)
ans=INF
for seq in S:
    tmp=0
    for i in range(R-1):
        tmp+=dist[seq[i]][seq[i+1]]
    ans=min(tmp,ans)
print(ans)

Solution (Python):
from itertools import permutations
N, M, R = map(int, input().split())
r = list(map(lambda x: int(x) - 1, input().split()))
G = [[float('inf')] * N for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    a, b = 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 = float('inf')
for perm in permutations(r):
    tmp = 0
    for i in range(R - 1):
        tmp += G[perm[i]][perm[i + 1]]
    ans = min(ans, tmp)

print(ans)

Solution (Python):
def inpl(): return [int(i) for i in input().split()]
import heapq
from itertools import permutations

N, M, R = inpl()
r = inpl()
for i in range(R):
    r[i] -= 1
inf = float('inf')
Q = [[inf] * N for _ in range(N)]
path = [[0] * N for _ in range(N)]

for i in range(M):
    A,B,C = inpl()
    path[A-1][B-1] = path[B-1][A-1] = C

for i in r:
    decided = [False for _ in range(N)]
    H = []
    ctr = 0
    Q[i][i] = 0
    heapq.heappush(H,(0,i))
    while ctr != N:
        while True:
            k = heapq.heappop(H)
            k = k[1]
            if not decided[k]:
                decided[k] = True
                ctr += 1
                break
        for j in range(N):
            if path[k][j] == 0:
                continue
            if decided[j]:
                continue
            Q[i][j] = min(Q[i][k] + path[k][j], Q[i][j])
            heapq.heappush(H,(Q[i][j],j))

Ans = inf
for i in permutations(r):
    ans = 0
    for j in range(R-1):
        ans += Q[i[j]][i[j+1]]
    Ans = min(Ans,ans) 
        
print(Ans)

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

def search(r,dist,ans):
    sum_=0
    for i in range(1,len(r)):
        sum_+=dist[r[i-1]][r[i]]
    return sum_

N,M,R=list(map(int,input().split()))
r=list(map(int,input().split()))
r=[x-1 for x in r]
dist=[[float('inf') for _ in range(N)] for _ in range(N)]
for i in range(M):
    A,B,C=list(map(int,input().split()))
    dist[A-1][B-1]=C
    dist[B-1][A-1]=C
for i in range(N):
    dist[i][i]=0
dist=ws(dist)

ans=float('inf')

ans=float('inf')
r=permutations(r)
for x in r:
    ans=min(ans,search(x,dist,0))
print(int(ans))