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 collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    n,m = LI()
    a = LIR(n)
    ans = 0
    for i in range(2):
        for j in range(2):
            for k in range(2):
                a.sort(key = lambda x:(-1)**i*x[0]+(-1)**j*x[1]+(-1)**k*x[2])
                p = [0,0,0]
                for l in range(m):
                    p[0] += a[l][0]
                    p[1] += a[l][1]
                    p[2] += a[l][2]
                p = abs(p[0])+abs(p[1])+abs(p[2])
                if p > ans:
                    ans = p
    print(ans)
    return


def B():
    def root(x):
        if x == par[x]:
            return x
        par[x] = root(par[x])
        return par[x]

    def unite(x,y,su):
        x = root(x)
        y = root(y)
        su += comb_2(s[x])+comb_2(s[y])
        if rank[x] < rank[y]:
            s[y] += s[x]
            su -= comb_2(s[y])
            par[x] = y
        else:
            s[x] += s[y]
            su -= comb_2(s[x])
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1
        return su

    def comb_2(a):
        return a*(a-1)//2

    n,m = LI()
    v = LIR(m)
    par = [i for i in range(n)]
    rank = [0]*n
    s = [1]*n
    su = comb_2(n)
    ans = [su]
    for a,b in v[:0:-1]:
        a -= 1
        b -= 1
        if root(a) != root(b):
            su = unite(a,b,su)
        ans.append(su)
    for i in ans[::-1]:
        print(i)
    return


def C():
    def root(x):
        if par[x] == x:
            return par[x]
        r = root(par[x])
        d[x] += d[par[x]]
        par[x] = r
        return par[x]

    def weight(x):
        root(x)
        return d[x]

    def unite(x,y,w):
        w += weight(x)
        w -= weight(y)
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
            d[x] = -w
        else:
            par[y] = x
            d[y] = w
            if rank[x] == rank[y]:
                rank[x] += 1
    n,m = LI()
    par = [i for i in range(n)]
    rank = [0]*n
    d = [0]*n
    for i in range(m):
        l,r,w = LI()
        l -= 1
        r -= 1
        if root(l) != root(r):
            unite(l,r,w)
        else:
            if weight(r)-weight(l) != w:
                print("No")
                return
    print("Yes")
    return


def D():
    h,w = LI()
    n = I()
    a = LI()
    ans = [0]*h*w
    p = 0
    for i in range(n):
        for j in range(a[i]):
            ans[p+j] = i+1
        p += a[i]
    for i in range(h):
        s = ans[i*w:(i+1)*w]
        if i%2:
            print(*s[::-1])
        else:
            print(*s)
    return


def E():
    n,k = LI()
    s = [int(x) for x in input()]
    f = [0]*n
    j = 0
    su = 1
    p = s[0]
    for i in range(1,n):
        if s[i] != p:
            f[j] = su
            j += 1
            su = 1
            p = s[i]
        else:
            su += 1
    f[j] = su
    f.append(0)
    if s[0]:
        m = sum(f[:2*k+1])
        ans = m
        for i in range(2*k+1,n):
            m -= f[i-2*k-1]
            if not i%2:
                m += f[i-1]
                m += f[i]
            ans = max(m,ans)
    else:
        m = sum(f[:2*k])
        ans = m
        for i in range(2*k,n):
            m -= f[i-2*k]
            if not i%2:
                m += f[i]
                m += f[i+1]
            ans = max(m,ans)
    print(ans)
    return


def F():
    n = I()
    a = LI()
    s = [0,0,0]
    for i in a:
        if i%4 == 0:
            s[0] += 1
        elif i%2 == 0:
            s[1] += 1
        else:
            s[2] += 1
    a = [0]
    while 1:
        if s[2]:
            if a[-1] == 2:
                print("No")
                return
            s[2] -= 1
            a.append(2)
            if s[0]:
                s[0] -= 1
                a.append(0)
        elif s[1]:
            if a[-1] == 2:
                print("No")
            else:
                print("Yes")
            return
        else:
            print("Yes")
            return
    return


def G():
    n,m,l = LI()
    r = LI()
    for i in range(l):
        r[i] -= 1
    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 = LI()
        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][j],d[i][k]+d[k][j])
    m = 1<<l
    dp = [[float("inf")]*l for i in range(m)]
    for i in range(l):
        dp[1<<i][i] = 0
    for b in range(m):
        for i in range(l):
            x = r[i]
            if not b&(1<<i):
                continue
            for j in range(l):
                if b&(1<<j):
                    continue
                nb = b|(1<<j)
                y = r[j]
                res = dp[b][i]+d[x][y]
                if res < dp[nb][j]:
                    dp[nb][j] = res
    print(min(dp[m-1]))
    return


def H():

    return


def I_():

    return


if __name__ == "__main__":
    G()

Solution (Python):
from itertools import permutations

n,m,rnum = map(int,input().split())
inf = 10**18
shortest = [[inf for i in range(n)] for j in range(n)]
r = list(map(int,input().split()))
for i in range(len(r)):
    r[i]-= 1

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

for i in range(len(shortest)):
    for j in range(len(shortest)):
        for k in range(len(shortest)):
            shortest[j][k] = min(shortest[j][k],shortest[j][i]+shortest[i][k])

ans = inf

for p in permutations(r):
    temp = 0
    for i in range(rnum-1):
        temp+=shortest[p[i]][p[i+1]]
    if ans > temp:
        ans = temp
print(ans)

Solution (Python):
from itertools import*

n,m,o=map(int,input().split())
*R,=map(int,input().split())
INF=float("inf")
d=[[INF]*n for _ in range(n)]
r=range
for i in r(n):
	d[i][i]=0
for _ in r(m):
	a,b,c=map(int,input().split())
	d[a-1][b-1]=d[b-1][a-1]=c
for k in r(n):
	for i in r(n):
		for j in r(n):
			d[i][j]=min(d[i][j],d[i][k]+d[k][j])
v=[[d[i-1][j-1]for j in R]for i in R]
m=INF
for t in permutations(r(o)):
	a=0;f=1
	for i,j in zip(t,t[1:]):
		if v[i][j]==INF:
			f=0
			break
		else:
			a+=v[i][j]
	if f:
		m=min(m,a)
print(m)

Solution (Python):
from itertools import permutations

n,m,r=map(int,input().split())
*R,=map(int,input().split())
INF=float("inf")
dist=[[INF]*n for _ in range(n)]
for i in range(n):
	dist[i][i]=0
for _ in range(m):
	a,b,c=map(int,input().split())
	dist[a-1][b-1]=c
	dist[b-1][a-1]=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])
v=[]
for i in R:
	t=[]
	for j in R:
		t.append(dist[i-1][j-1])
	v.append(t)
mn=INF
for t in permutations(range(r)):
	a=0;f=1
	for i,j in zip(t,t[1:]):
		if v[i][j]==INF:
			f=0
			break
		else:
			a+=v[i][j]
	if f:
		mn=min(mn,a)
print(mn)

Solution (Python):
n,m,R=map(int,input().split())
r=[int(i) for i in input().split()]
inputs=[]
d=[[10**100 for i in range(n+1)] for i in range(n+1)]
for i in range(m):
    a,b,c=map(int,input().split())
    d[a][b]=c
    d[b][a]=c

def warshall_floyd(d):
    
    for k in range(n+1):
        for i in range(n+1):
            for j in range(n+1):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
d=warshall_floyd(d)
ans=10**100
import itertools
for x in itertools.permutations(r):
    p=0
    for i in range(1,R):
        p+=d[x[i-1]][x[i]]
    ans=min(ans,p)
print(ans)

Solution (Python):
from itertools import permutations
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)]
ans = inf
for _ in range(M): 
    A,B,C = map(int, input().split())
    d[A][B] = C
    d[B][A] = C

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

warshall_floyd(N)

for p in permutations(r): 
    tmp = 0
    for r1,r2 in zip(p,p[1:]):
        tmp += d[r1][r2]
    ans = min(ans, tmp)
print(ans)

Solution (Python):

import sys
from itertools import permutations
INF = float("inf")


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.V = list(range(N))
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        """辺を加える。edgeは(始点, 終点、重み)からなるリスト
        重みがなければ、重み1とする。
        """
        if len(edge) == 2:
            edge.append(1)
        elif len(edge) != 3:
            print("error in add_edge")
            pass

        s, t, w = edge
        self.E[s].append([t, w])
        self.E[t].append([s, w])  

        pass


def Warshall_Floyd(g: Graph):
    """ワーシャルフロイド法により、全節点対の最短距離を求める。O(V^3)
    https://ja.wikipedia.org/wiki/%E3%83%AF%E3%83%BC%E3%82%B7%E3%83%A3%E3%83%AB%E2%80%93%E3%83%95%E3%83%AD%E3%82%A4%E3%83%89%E6%B3%95
    """
    N = g.N
    dist = [[INF]*N for _ in range(N)]
    for from_, toweights in enumerate(g.E):
        for to_, w in toweights:
            dist[from_][to_] = w

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


def solve(N: int, M: int, R: int, r: "List[int]", A: "List[int]", B: "List[int]", C: "List[int]"):

    g = Graph(N)
    for a, b, c in zip(A, B, C):
        g.add_edge([a-1, b-1, c])

    B = Warshall_Floyd(g)

    m = INF
    for order in permutations(r, R):
        counter = 0
        for i in range(R-1):
            counter += B[order[i]-1][order[i+1]-1]
        m = min(m, counter)
    print(m)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    R = int(next(tokens))  
    r = [int(next(tokens)) for _ in range(R)]  
    A = [int()] * (M)  
    B = [int()] * (M)  
    C = [int()] * (M)  
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    solve(N, M, R, r, A, B, C)


if __name__ == '__main__':
    main()

Solution (Python):
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque

from itertools import product

from itertools import permutations

from itertools import combinations

from itertools import accumulate
from bisect import bisect_left, bisect_right

import re







def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 


def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]


    

def warshall_floyd(G):
    
    N = len(G)
    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])
    return G

def main():
    
    N, M, R = l_inpl()
    r = list(map(int, input().split()))
    r = [ ri - 1 for ri in r ]

    
    G = [[INF] * N for _ in range(N)]

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

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

    G = warshall_floyd(G)

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

    print(ans)
if __name__ == "__main__":
    main()

Solution (Python):
import itertools
n,m,r = map(int, input().split())
towns = 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 i 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): 
            cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])


ans = INF

for node in itertools.permutations(range(r)): 
    tmp = 0
    for x, y in zip(node, node[1:]):
        s, g = towns[x], towns[y] 
        tmp += cost[s-1][g-1] 
    ans = min(ans, tmp)

print(ans)

Solution (Python):

import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math
import itertools
 




 
def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N,M,R = inputMap()
    r = inputList()
    A = [[float('inf') for _ in range(N)] for _ in range(N)]
    
    for _ in range(M):
        a,b,c = inputList()
        A[a-1][b-1] = c
        A[b-1][a-1] = c
    
    for i in range(N):
        A[i][i] = 0
        
    A = warshall_floyd(A, N)
        
    ans = -1
    visi = list(itertools.permutations(r))
    for sp in visi:
        tmp = 0
        for i, val in enumerate(sp):
            if i == 0:
                continue
            tmp += A[sp[i-1]-1][sp[i]-1]
            
        if ans == -1 or ans > tmp:
            ans = tmp
            
    print(ans)
        
def warshall_floyd(d, n):
	
	for k in range(n):
		for i in range(n):
			for j in range(n):
				d[i][j] = min(d[i][j], d[i][k] + d[k][j])
	return d
		
            	
if __name__ == "__main__":
	main()

Solution (Python):

import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math
import itertools






def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N,M,R = inputMap()
    r = inputList()
    A = [[100000000000000000 for _ in range(N)] for _ in range(N)]
    
    for _ in range(M):
        a,b,c = inputList()
        A[a-1][b-1] = c
        A[b-1][a-1] = c
    
    for i in range(N):
        A[i][i] = 0
        
    A = warshall_floyd(A, N)
        
    ans = -1
    visi = list(itertools.permutations(r))
    for sp in visi:
        tmp = 0
        for i, val in enumerate(sp):
            if i == 0:
                continue
            tmp += A[sp[i-1]-1][sp[i]-1]
            
        if ans == -1 or ans > tmp:
            ans = tmp
            
    print(ans)
        
def warshall_floyd(d, n):
	
	for k in range(n):
		for i in range(n):
			for j in range(n):
				d[i][j] = min(d[i][j], d[i][k] + d[k][j])
	return d
		
            	
if __name__ == "__main__":
	main()

Solution (Python):
n,m,r=map(int,input().split())
root=list(map(int,input().split()))
abc=[list(map(int,input().split())) for _ in [0]*m]
inf=10**10
dist=[[inf for _ in [0]*n] for _ in [0]*n]
for i in range(n):dist[i][i]=0
for a,b,c in abc:
    dist[a-1][b-1]=c
    dist[b-1][a-1]=c
for k in range(n):
    for i in range(n):
        for j in range(n):dist[i][j]=min(dist[i][j],(dist[i][k]+dist[k][j]))

from itertools import permutations

p=list(permutations(root))

D=10**10
for i in p:
    d=0
    for j in range(len(i)-1):
        d+=dist[i[j]-1][i[j+1]-1]
    D=min(D,d)
print(D)

Solution (Python):

import itertools
from scipy.sparse.csgraph import floyd_warshall as wf

def do():
    N,M,R = list(map(int,input().split(" ")))
    rs = list(map(int,input().split(" ")))
    INF = float('inf')

    graph = [ [INF for _ in range(N + 1)]for _ in range(N + 1)]
    for _ in range(M):
        a,b,c = (map(int, input().split(" ")))
        graph[a][b] = c
        graph[b][a] = c

    graph = wf(graph)

    perms = itertools.permutations(rs)
    ans = INF
    for temp in perms:
        cand = 0
        for i in range(0,R-1):
            fr = temp[i]
            to = temp[i + 1]
            cand+= graph[fr][to]
        ans = min(cand,ans)
    print(int(ans))

if __name__ == "__main__":
    do()

Solution (Python):

import itertools

def do():
    N,M,R = list(map(int,input().split(" ")))
    rs = list(map(int,input().split(" ")))
    INF = 10 ** 20
    graph = [ [INF for _ in range(N + 1)]for _ in range(N + 1)]
    for _ in range(M):
        a,b,c = (map(int, input().split(" ")))
        graph[a][b] = c
        graph[b][a] = c
    for k in range(1,N+1):
        for j in range(1, N + 1):
            for i in range(1, N + 1):
                graph[j][i] = min(graph[j][i] , graph[j][k] + graph[k][i])

    perms = itertools.permutations(rs)
    ans = INF
    for temp in perms:
        cand = 0
        for i in range(0,R-1):
            fr = temp[i]
            to = temp[i + 1]
            cand+= graph[fr][to]
        ans = min(cand,ans)
    print(ans)

if __name__ == "__main__":
    do()

Solution (Python):
import heapq
import itertools

def dijkstra(s):
    cost = [10**20] * (N+1)
    visited = [False] * (N+1)
    visited[s], cost[s] = True, 0
    q = []

    for r in route[s]:
        heapq.heappush(q, r)

    while q:
        c, r = heapq.heappop(q)

        if not visited[r]:
            visited[r] = True
            cost[r] = min(cost[r], c)

            for c_, n in route[r]:
                if not visited[n]:
                    heapq.heappush(q, (c+c_, n))

    return cost

N, M, R = map(int, input().split())
r_ = list(map(int, input().split()))
ans = 10**10
route = [[] for i in range(N+1)]

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

cost = {r:dijkstra(r) for r in r_}
for r in itertools.permutations(r_):
    total = 0

    for i in range(R-1):
        total += cost[r[i]][r[i+1]]
    ans = min(ans, total)
print(ans)

Solution (Python):
from collections import deque
import itertools
from scipy.sparse.csgraph import floyd_warshall as wf
import sys


MAX = 1e9


def main():
    n, m, r = map(int, input().split())
    R = list(map(int, input().split()))
    link = [[MAX if j != i else 0 for j in range(n+1)] for i in range(n+1)]
    for i in range(m):
        a, b, c = map(int, input().split())
        link[a][b] = c
        link[b][a] = c
    link = wf(link)
    ans = MAX
    for per in list(itertools.permutations(R)):
        tmp = 0
        for i in range(r-1):
            tmp += link[per[i]][per[i+1]]
        ans = min(ans, tmp)
    print(int(ans))


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
import itertools
from scipy.sparse.csgraph import floyd_warshall as wf
import sys
input = sys.stdin.readline

MAX = 1e9

def main():
    N, M, R = map(int, input().split())
    r = list(map(int, input().split()))
    link = [[MAX if j != i else 0 for j in range(N+1)] for i in range(N+1)]

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

    link = wf(link)

    ans = MAX
    for per in list(itertools.permutations(r)):
        tmp = 0
        for i in range(R-1):
            tmp += link[per[i]][per[i+1]]
        ans = min(ans, tmp)
    print(int(ans))

if __name__ == "__main__":
    main()

Solution (Python):
from itertools import permutations
n,m,r=map(int,input().split())
visit=list(map(int,input().split()))
dist=[[10**9]*n for i in range(n)]
for i in range(m):
  a,b,c=map(int,input().split())
  dist[a-1][b-1],dist[b-1][a-1]=c,c
for i in range(n):
  dist[i-1][i-1]=0
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=10**9
check=permutations(visit)
for i in check:
  c=0
  for j in range(1,r):
    c+=dist[i[j-1]-1][i[j]-1]
  if c<ans:ans=c
print(ans)

Solution (Python):
n,m,r=map(int,input().split())
r_list=list(map(int,input().split()))
dp=[]
INF=10**9
for i in range(n):
    sub_list=[INF]*n
    dp.append(sub_list)
for i in range(n):
    dp[i][i]=0
for i in range(m):
    a,b,c=map(int,input().split())
    dp[a-1][b-1]=c
    dp[b-1][a-1]=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])
R=[i for i in range(r)]
import itertools
Rp=itertools.permutations(R,r)
ans=INF
count=0
for i in Rp:
    temp=0
    for j in range(r-1):
        temp+=dp[r_list[i[j]]-1][r_list[i[j+1]]-1]
    ans=min(ans,temp)
print(ans)

Solution (Python):
from itertools import permutations


def solve(n, m, r):
    ans = 10**18
    d = [[10**18]*n for _ in range(n)]
    rx = list(i-1 for i in map(int, input().split()))

    for i in range(m):
        s, t, length = map(int, input().split())
        d[s-1][t-1] = length
        d[t-1][s-1] = length

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

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

    for p in permutations(rx):
        from_p1_to_pr = 0
        for p_j,  p_next in zip(p, p[1:]):
            from_p1_to_pr += d[p_j][p_next]
        if from_p1_to_pr < ans:
            ans = from_p1_to_pr

    return ans


if __name__ == '__main__':
    n, m, r = map(int, input().split())
    print(solve(n, m, r))

Solution (Python):
import itertools
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
r = list(map(lambda x: x - 1, r))
d = [[10 ** 10] * 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):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

ans = 10 ** 10

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

print(ans)

Solution (Python):
from itertools import permutations
N,M,R=map(int,input().split())
r=list(map(int,input().split()))
inf=10**9
d=[[inf]*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 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 permutations(r):
  start=0
  for j in range(R-1):
    start+=d[l[j]-1][l[j+1]-1]
  ans=min(start,ans)
print(ans)

Solution (Python):
import itertools

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


INF = 10 ** 12
dist = [[INF] * N for _ in range(N)]
for i in range(N):
	dist[i][i] = 0


for a, b, c in ABC:
	a, b = a - 1, b - 1
	dist[a][b] = c
	dist[b][a] = c


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




min_dist = INF
for p in itertools.permutations(r):
	d = 0
	for n in range(1, R):
		d += dist[p[n] - 1][p[n - 1] - 1]
	if d < min_dist:
		min_dist = d
		
print(min_dist)

Solution (Python):
from itertools import permutations
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(M)]

graph = [[float('inf')] * N for _ in range(N)]
for i in range(N):
    graph[i][i] = 0

for u, v, l in edges:
    graph[u - 1][v - 1] = l
    graph[v - 1][u - 1] = l

for k in range(N):
    for i in range(N):
        if graph[i][k] == float('inf'):
            continue
        for j in range(N):
            if graph[k][j] == float('inf'):
                continue
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

ans = 10 ** 9 + 7
for l in permutations(r, R):
    ans = min(ans, sum(graph[l[i] - 1][l[i + 1] - 1] for i in range(R - 1)))
        
print(ans)

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

N,M,R = map(int,input().split())
r = list(map(int,input().split()))
S = [[]for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    S[a-1].append([b-1,c])
    S[b-1].append([a-1,c])
d = [[float('inf')]*N for i in range(N)]
queue = []
hoge = [0]*(M)
for i in range(N):
    queue = [i]
    d[i][i] = 0
    while queue !=[]:
        l = 0
        for q in queue:
            for next,c in S[q]:
                if d[i][next] > d[i][q]+c:
                    d[i][next] = d[i][q]+c
                    if not(next in hoge[:l]):
                        hoge[l] = next
                        l += 1
        queue = hoge[:l]
def func(x,l):
    if l == []:
        return 0
    ans = float('inf')
    for i in range(len(l)):
        ans =min(ans,func(l[i],l[:i]+l[i+1:]) + d[x-1][l[i]-1])
    return ans
ans = float('inf')
for i in r:
    ans = min(ans,func(i,r))
print(ans)

Solution (Python):




"""
Dijkstra法: 単一始点最短路（距離が正）
g: g[i] = [(子、距離),...]の隣接リスト
start: 始点
"""
from heapq import heappush, heappop
def dijkstra(g,start): 
    dist = [1e18]*(len(g)) 
    q = [(0,start)] 
    dist[start] = 0
    pending = len(g)-1
    while q and pending:
        c,v = heappop(q)
        if dist[v] < c: continue
        pending -= 1
        for to, cost in g[v]:
            if dist[v] + cost < dist[to]:
                dist[to] = dist[v] + cost
                heappush(q, (dist[to], to))
    return dist


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

inf = 10**9
g = [[] for _ in range(n)]
for _ in range(m):
    a,b,c = [int(i) for i in input().split()]
    g[a-1].append((b-1, c))
    g[b-1].append((a-1, c))


dvec = [None]*R
for i, ri in enumerate(r):
    dvec[i] = dijkstra(g, ri)

m = {ri:i for i, ri in enumerate(r)}    

ans = inf
import itertools
for x in itertools.permutations(r):
    c = 0
    for i, xi in enumerate(x):
        if i > 0:
            c += dvec[m[xi]][x[i-1]]
    if c < ans:
        ans = c
            
print(ans)

Solution (Python):



from heapq import heappush, heappop
def dijkstra(g,start): 
    inf = float("inf")
    dist = [inf]*(len(g))
    q = [(start,0)] 
    dist[start] = 0
    while q:
        v,c = heappop(q)
        if dist[v] < c: continue
        for to, cost in g[v]:
            if dist[v] + cost < dist[to]:
                dist[to] = dist[v] + cost
                heappush(q, (to, dist[to]))
    return dist


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

inf = 10**9
g = [[] for _ in range(n)]
for _ in range(m):
    a,b,c = [int(i) for i in input().split()]
    g[a-1].append((b-1, c))
    g[b-1].append((a-1, c))


dvec = [None]*R
for i, ri in enumerate(r):
    dvec[i] = dijkstra(g, ri)

m = {ri:i for i, ri in enumerate(r)}    

ans = inf
import itertools
for x in itertools.permutations(r):
    c = 0
    for i, xi in enumerate(x):
        if i > 0:
            c += dvec[m[xi]][x[i-1]]
    if c < ans:
        ans = c
            
print(ans)

Solution (Python):
import itertools

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

N,M,R = [int(x) for x in input().split()]
graph = [[float('inf')]*(N+1) for _ in range(N+1)]
r = [int(x) for x in input().split()]

for _ in range(M):
    s,d,w = [int(x) for x in input().split()]
    graph[s][d] = w
    graph[d][s] = w

warshall_floyd(graph,N+1)
ans = float('inf')
for _r in itertools.permutations(r):
    di = 0
    for ind,j in enumerate(_r[:-1]):
        di+=graph[j][_r[ind+1]]
    ans = min(ans,di)

print(ans)

Solution (Python):

import string
import sys
from itertools import chain, dropwhile, takewhile, permutations


def read(
    *shape, f=int, it=chain.from_iterable(sys.stdin), whitespaces=set(string.whitespace)
):
    def read_word():
        w = lambda c: c in whitespaces
        nw = lambda c: c not in whitespaces
        return f("".join(takewhile(nw, dropwhile(w, it))))

    if not shape:
        return read_word()
    elif len(shape) == 1:
        return [read_word() for _ in range(shape[0])]
    elif len(shape) == 2:
        return [[read_word() for _ in range(shape[1])] for _ in range(shape[0])]


def readi(*shape):
    return read(*shape)


def readi1(*shape):
    return [i - 1 for i in readi(*shape)]


def readf(*shape):
    return read(*shape, f=float)


def reads(*shape):
    return read(*shape, f=str)


def arr(*shape, fill_value=0):
    if len(shape) == 1:
        return [fill_value] * shape[fill_value]
    elif len(shape) == 2:
        return [[fill_value] * shape[1] for _ in range(shape[0])]


def dbg(**kwargs):
    print(
        ", ".join("{} = {}".format(k, repr(v)) for k, v in kwargs.items()),
        file=sys.stderr,
    )


def main():
    N, M, R = readi(3)
    rs = readi1(R)

    G = arr(N, N, fill_value=10 ** 10)
    for i in range(N):
        G[i][i] = 0

    for _ in range(M):
        a, b, c = readi(3)
        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):
                G[i][j] = min(G[i][j], G[i][k] + G[k][j])

    ans = 10 ** 10
    for perm in permutations(rs):
        tmp = 0
        for i in range(len(perm) - 1):
            tmp += G[perm[i]][perm[i + 1]]
        ans = min(ans, tmp)

    print(ans)


if __name__ == "__main__":
    main()