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 accumulate, permutations, combinations, combinations_with_replacement, groupby, product









import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    
    
    def warshall_floyd(v_num, dist_lst):
        
        negative_cycle_flag = False
    
        
        
        for k in range(v_num):
            for i in range(v_num):
                for j in range(v_num):
                    
                    if dist_lst[i][k] != INF and dist_lst[k][j] != INF:
                        if dist_lst[i][j] > dist_lst[i][k] + dist_lst[k][j]:
                            dist_lst[i][j] = dist_lst[i][k] + dist_lst[k][j]
    
        for v in range(v_num):
            
            
            if dist_lst[v][v] < 0:
                negative_cycle_flag = True
    
        return dist_lst
    
    
    

    v_num, e_num ,R= map(int, input().split())
    r=list(map(int,input().split()))
    
    
    
    INF = 10 ** 20
    dist_lst = [[INF] * v_num for _ in range(v_num)]
    
    for _ in range(e_num):
        s, t, dist = map(int, input().split())
        dist_lst[s-1][t-1] = dist
        dist_lst[t-1][s-1] = dist

    
    for v in range(v_num):
        dist_lst[v][v] = 0
    
    ll=warshall_floyd(v_num, dist_lst)
    minans=10**10
    for i in permutations(r):
        ans=0
        for j in range(len(i)-1):
            if ll[i[j]-1][i[j+1]-1]==INF or ll[i[j]-1][i[j+1]-1]==0:
                break
            else:
                ans+=ll[i[j]-1][i[j+1]-1]
        minans=min(minans,ans)
    print(minans)


    
      
    
resolve()

Solution (Python):
n, m, r = map(int, input().split())
rs = list(map(int, input().split()))
rs = [i-1 for i in rs]
d = [[float('inf')] * n for i in range(n)]
for i in range(m):
    x, y, r = map(int, input().split())
    x -= 1
    y -= 1
    d[x][y] = r
    d[y][x] = r

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

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

d = warshall_floyd(d)

ans = float('inf')
from itertools import permutations
for i in permutations(rs):
    di = 0
    for j in range(len(rs) - 1):
        di += d[i[j]][i[j + 1]]
    ans = min(ans, di) 

print(ans)

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

INFTY = 10**9
cost = [[INFTY]*(N+1) for _ in range(N+1)]


for _ in range(W):
    u, v, c = map(int, input().split())
    cost[u][v] = c
    cost[v][u] = c


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


def WarshallFloyd():
    for k in range(N+1):
        for i in range(N+1):
            for j in range(N+1):
                cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j])


WarshallFloyd()

ans = 10**9
for T in permutations(S, R):
    temp = 0
    t = T[0]
    for i in range(1, R):
        temp += cost[t][T[i]]
        t = T[i]
    ans = min(ans, temp)
print(ans)

Solution (Python):
N,M,R = map(int,input().split())
R = list(map(int,input().split()))
dp = [[float("INF")]*(N+1) for _ in range(N+1)]
for i in range(N+1):
    dp[i][i] = 0

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

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

candidate = []
def dfs (r,cost,path=set()):
    path.add(r)
    if len(path) == len(R):
        candidate.append(cost)
    else:
        for nx in R:
            if nx not in path:
                dfs(nx,cost+dp[r][nx],path)
    path.remove(r)

for r in R:
    dfs(r,0)
print(min(candidate))

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


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


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





N,M,R = IL()
R = IL()

class WarshallFloyd():
  def __init__(self, N):
    self.N = N
    self.d = [[float("inf") for i in range(N)] for i in range(N)]

  def add(self, u, v, c, directed=False):
    if directed is False:
      self.d[u][v] = c
      self.d[v][u] = c
    else:
      self.d[u][v] = c

  def WarshallFloyd_search(self):
    for k in range(self.N):
      for i in range(self.N):
        for j in range(self.N):
          self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])
    hasNegativeCycle = False
    for i in range(self.N):
      if self.d[i][i] < 0:
        hasNegativeCycle = True
        break
    for i in range(self.N):
      self.d[i][i] = 0
    return hasNegativeCycle, self.d

graph = WarshallFloyd(N+1)
for _ in range(M):
  u,v,c = IL()
  graph.add(u, v, c)
_, d = graph.WarshallFloyd_search()

from itertools import permutations
MIN = INF
for t in permutations(R):
  COST = 0
  prev = t[0]
  for now in t[1:]:
    COST += d[prev][now]
    prev = now
  MIN = min(MIN,COST)
print(MIN)

Solution (Python):
def main():
    from itertools import permutations

    n, m, r, *x = map(int, open(0).read().split())
    to = x[:r]

    dis = [[10 ** 8] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        dis[i][i] = 0

    for a, b, c in zip(*[iter(x[r:])] * 3):
        dis[a][b] = c
        dis[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[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])

    ans = 10 ** 8
    for p in permutations(to):
        tmp = 0
        nw = p[0]
        for nx in p[1:]:
            tmp += dis[nw][nx]
            nw = nx

        ans = min(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from itertools import permutations

    n, m, r, *x = map(int, open(0).read().split())
    to = x[:r]

    dis = [[float("Inf")] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        dis[i][i] = 0

    for a, b, c in zip(*[iter(x[r:])] * 3):
        dis[a][b] = c
        dis[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[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])

    ans = float("Inf")
    for p in permutations(to):
        tmp = 0
        nw = p[0]
        for nx in p[1:]:
            tmp += dis[nw][nx]
            nw = nx

        ans = min(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from itertools import permutations

    n, m, r, *x = map(int, open(0).read().split())
    to = x[:r]

    dis = [[0 if i == j else float("Inf") for j in range(n + 1)] for i in range(n + 1)]

    for a, b, c in zip(*[iter(x[r:])] * 3):
        dis[a][b] = c
        dis[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[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])

    ans = float("Inf")
    for p in permutations(to):
        tmp = 0
        for nw, nx in zip(p, p[1:]):
            tmp += dis[nw][nx]
    
        ans = min(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from itertools import permutations

    n, m, r, *x = map(int, open(0).read().split())
    to = x[:r]

    dis = [[0 if i == j else float("Inf") for j in range(n + 1)] for i in range(n + 1)]

    for a, b, c in zip(*[iter(x[r:])] * 3):
        dis[a][b] = c
        dis[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[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])

    ans = float("Inf")
    for p in permutations(to):
        tmp = 0
        nw = p[0]
        for nx in p[1:]:
            tmp += dis[nw][nx]
            nw = nx

        ans = min(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.read
from itertools import permutations
def main():
    def warshall_floyd(d):
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])
        return d
 
    n, m, r = map(int, input().split())
    rs = tuple(map(int, input().split()))
    d = [[10**9] * n for _ in range(n)]
    m = map(int, read().split())
    mmm = zip(m, m, m)
    for s, t, dis in mmm:
        s -= 1
        t -= 1
        d[t][s] = d[s][t] = dis
    for j1 in range(n):
        d[j1][j1] = 0
    res = warshall_floyd(d)
    rsp = tuple(permutations(rs))
    result = float('inf')
    for rspe in rsp:
        res_t = 0
        for i1 in range(r - 1):
            res_t += res[rspe[i1]-1][rspe[i1+1]-1]
        result = min(result, res_t)
    print(result)
 
if __name__ == '__main__':
    main()

Solution (Python):

from itertools import permutations
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
graph = [[float("inf") for _ in range(N)] for _ in range(N)]
for i in range(N):
    graph[i][i] = 0
for i in range(M):
    a, b, c = map(int, input().split())
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c
for k in range(N):
    for i in range(N):
        for j in range(N):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
P = permutations(r)
ans = float("inf")
for p in P:
    tmp = 0
    for i in range(R-1):
        tmp += graph[p[i]-1][p[i+1]-1]
    ans = min(ans, tmp)
print(ans)

Solution (Python):

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

INF=10**11
G=[[INF for j in range(N+1)] for i in range(N+1)]
conection=[[] for i in range(N+1)]

RG=[[INF for j in range(N+1)] for i in range(N+1)]

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

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

        if d[u] < d_u:
            continue
        
        for v in conection[u]:
            if not(used[v]) and d_u + G[u][v] < d[v]:
                d[v] = d_u + G[u][v]
                heappush(heap,(d[v],v))
    
    for i in range(R):
        r=r_list[i]
        RG[start][r]=d[r]
        RG[r][start]=d[r]
        
P=permutations(r_list,R)
ans=INF

for p in P:
    tmp=0
    for j in range(R-1):
        tmp+=RG[p[j]][p[j+1]]
    ans=min(ans,tmp)

print(ans)

Solution (Python):
from itertools import permutations
N,M,R=map(int, input().split())
G=[[float("INF")]*N for _ in range(N)]
r=list(map(int, input().split()))
for i in range(M):
    a,b,c=map(int, input().split())
    G[a-1][b-1]=c
    G[b-1][a-1]=c

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

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




ans=float("INf")
for t in permutations(r):
    sub=0
    
    for i in range(R):
        if i==0:
            now=t[i]
        sub+=G[now-1][t[i]-1]
        now=t[i]
        
    ans=min(ans, sub)
print(ans)

Solution (Python):
def warshall_floyd(graph):
    n_nodes = len(graph)

    froms = []
    for i in range(len(graph)):
        froms.append([])
        for j in range(len(graph[i])):
            if i == j:                          
                froms[i].append(0)
            elif graph[i][j] < float("inf"):    
                froms[i].append(i)
            else:
                froms[i].append(None)

    for k in range(n_nodes):
        for i in range(n_nodes):
            for j in range(n_nodes):
                adj_cost = graph[i][k] + graph[k][j]
                if adj_cost < graph[i][j]:
                    graph[i][j] = adj_cost
                    froms[i][j] = froms[k][j]
    
    has_negative_loop = False
    for i in range(n_nodes):
        if graph[i][i] < 0:
            has_negative_loop = True
            break

    return graph, froms, has_negative_loop

def resolve():
    N, M, R = list(map(int, input().split()))
    R = list(map(int, input().split()))
    adjs = [[float("inf") for _ in range(N)] for __ in range(N)]
    for i in range(M):
        a, b, c = list(map(int, input().split()))
        adjs[a-1][b-1] = c
        adjs[b-1][a-1] = c
    costs, _, __ = warshall_floyd(adjs)
    
    import itertools
    mincost = float("inf")
    for route in itertools.permutations(R):
        src = route[0] - 1
        cost = 0
        for didx in range(1, len(route)):
            dst = route[didx] - 1
            cost += costs[src][dst]
            src = dst
        mincost = min(mincost, cost)
    print(mincost)
    
        

if '__main__' == __name__:
    resolve()

Solution (Python):
import sys
read = sys.stdin.read
from itertools import permutations
def main():
    def warshall_floyd(d):
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])
        return d

    n, m, r = map(int, input().split())
    rs = tuple(map(int, input().split()))
    d = [[10**9] * n for _ in range(n)]
    m = map(int, read().split())
    mmm = zip(m, m, m)
    for s, t, dis in mmm:
        s -= 1
        t -= 1
        d[t][s] = d[s][t] = dis
    for j1 in range(n):
        d[j1][j1] = 0
    res = warshall_floyd(d)
    rsp = tuple(permutations(rs))
    result = float('inf')
    for rspe in rsp:
        res_t = 0
        for i1 in range(r - 1):
            res_t += res[rspe[i1]-1][rspe[i1+1]-1]
        result = min(result, res_t)
    print(result)

if __name__ == '__main__':
    main()

Solution (Python):
def WarshallFloyd(d):
    v = len(mat)
    for k in range(v):
        for i in range(v):
            for j in range(v):
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])

n,m,r = map(int, input().split())
ls = list(map(int, input().split()))
INF = 1001001001001
mat = [[INF]*n for _ in range(n)]
for i in range(m):
    u,v,c = map(int, input().split())
    u-=1
    v-=1
    mat[u][v]=c
    mat[v][u]=c

WarshallFloyd(mat)

from itertools import permutations

ans=INF
for p in permutations(ls):
    now=0
    for i in range(len(p)-1):
        now+=mat[p[i]-1][p[i+1]-1]
    ans=min(ans,now)

print(ans)

Solution (Python):
n,m,r_=map(int,input().split())
r=list(map(int,input().split()))
g=[[]for _ in range(n)]
for _ in range(m):
  a,b,c=map(int,input().split())
  a-=1
  b-=1
  g[a].append([b,c])
  g[b].append([a,c])
from heapq import heapify,heappush,heappop
def dks(t0,t1):
  kyori=[-1]*n
  todo=[[0,t0]]
  heapify(todo)
  while todo:
    d,t=heappop(todo)
    kyori[t]=d
    if t==t1:break
    l=g[t]
    for li,c in l:
      if kyori[li]==-1:
        heappush(todo,[c+d,li])
  return kyori[t1]
ans=pow(10,9)
allr=[]
import sys
sys.setrecursionlimit(10**7)
def dfs(s,k): 
  if len(k)==1:
    s.append(k.pop())
    return [s]
  ret=[]
  for ki in k:
    ret.extend(dfs(s+[ki],k-{ki}))
  return ret
allr=dfs([],set(r))
d={}
for i in range(r_-1):
  for j in range(i+1,r_):
    k=dks(r[i]-1,r[j]-1)
    d[r[i]-1,r[j]-1]=k
    d[r[j]-1,r[i]-1]=k

for j in range(len(allr)):
  r1=allr[j]
  ansi=0
  for i in range(r_-1):
    ansi+=d[(r1[i]-1,r1[i+1]-1)]
  ans=min(ans,ansi)
print(ans)

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





def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))


from itertools import permutations

def main():
	n,m,R=MI()
	r=LI()

	G=[[10**9]*(n+1) for _ in range(n+1)]
	for i in range(n+1):
		G[i][i]=0



	for _ in range(m):
		a,b,c=MI()
		G[a][b]=min(G[a][b],c)
		G[b][a]=min(G[b][a],c)
	

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

	ans=10**9
	for i in permutations(r,R):
		
		ret=0
		for j in range(R-1):
			ret+=G[i[j]][i[j+1]]
		
		ans=min(ans,ret)
	print(ans)





if __name__ == "__main__":
	main()

Solution (Python):
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

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

RS = list(map(int, input().split()))

G = [[] for _ in range(N + 1)]

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


def dijkstra(s):
    d = [1 << 28] * (N + 1)
    d[s] = 0
    q = []
    heapq.heappush(q, (0, s))

    while q:
        cur = heapq.heappop(q)

        if d[cur[1]] != cur[0]:
            continue

        for nx in G[cur[1]]:
            if d[nx[0]] > cur[0] + nx[1]:
                d[nx[0]] = cur[0] + nx[1]
                heapq.heappush(q, (cur[0] + nx[1], nx[0]))

    return d


DIRS = [dijkstra(s) for s in RS]
MAT = [[d[r] for r in RS] for d in DIRS]

mem = {}


def solve(idx, st):
    if st == (1 << R) - 1:
        return 0
    if (idx, st) in mem:
        return mem[(idx, st)]

    ret = 1 << 28
    for i in range(R):
        if ((st >> i) & 1) == 0:
            ret = min(ret, solve(i, st | (1 << i)) + MAT[idx][i])

    mem[(idx, st)] = ret
    return ret


print(min([solve(i, 1 << i) for i in range(R)]))

Solution (Python):
import itertools
import sys

INF = 10 ** 9

def input(): return sys.stdin.readline().strip()
def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N, M, R = ZZ()
    r = ZZ()
    d = [[INF] * (N) for _ in range(N)]
    for i in range(N): d[i][i] = 0
    for _ in range(M):
        a, b, c = ZZ()
        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])
    ans = INF
    for v in itertools.permutations(r, R):
        cc = 0
        for i in range(R-1): cc += d[v[i]-1][v[i+1]-1]
        ans = min(ans, cc)
    print(ans)

    return

if __name__ == '__main__':
    main()

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7






N, M, R = getNM()

d = [[float("inf")] * N for i in range(N)]
list_R = [int(i) - 1 for i in input().split()]
for i in range(M):
   x, y, z = getNM()
   d[x - 1][y - 1] = min(d[x - 1][y - 1], z)
   d[y - 1][x - 1] = min(d[x - 1][y - 1], z)

def warshall_floyd(dist):
    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])
    

warshall_floyd(d)

ans = float('inf')
for case in permutations(list_R):
    x1 = case[0]
    opt = 0
    for j in range(1, R):
        x2 = case[j]
        opt += d[x1][x2]
        x1 = x2
    ans = min(ans, opt)
print(ans)

Solution (Python):
from sys import stdin
from itertools import permutations
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse.csgraph import csgraph_from_dense
def main():
    
    readline=stdin.readline
    inf=10**9
    n,m,r=map(int,readline().split())
    targets=list(map(lambda x:int(x)-1,readline().split()))
    G=[[inf]*n for _ in range(n)]
    for _ in range(m):
        a,b,c=map(int,readline().split())
        a-=1
        b-=1
        G[a][b]=min(G[a][b],c)
        G[b][a]=min(G[b][a],c)

    
    G=csgraph_from_dense(G,null_value=10**9)
    li=floyd_warshall(G)
    li=[list(map(int,li[i])) for i in range(n)]
    
    
    ans=inf
    for p in permutations(targets,r):
        tmp=0
        for i in range(r-1):
            now=p[i]
            nex=p[i+1]
            tmp+=li[now][nex]
        ans=min(ans,tmp)

    print(ans)

if __name__=="__main__":
    main()

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

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

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

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


ans = 10**8
for i in itertools.permutations(r):
  x = i
  k = 0
  for j in range(R-1):
    a,b = x[j+1],x[j]
    a -= 1
    b -= 1
    k += d[b][a]
  ans = min(ans,k)
print (ans)

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

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

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

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


ans = 10**10
for i in itertools.permutations(r):
  x = i
  k = 0
  for j in range(R-1):
    a,b = x[j+1],x[j]
    a -= 1
    b -= 1
    k += d[b][a]
  ans = min(ans,k)
print (ans)

Solution (Python):
import math



def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

def AddV2(v,w):
    return [v[0]+w[0],v[1]+w[1]]

dir4 = [[1,0],[0,1],[-1,0],[0,-1]]


def clamp(x,y,z):
    return max(y,min(z,x))

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            

def Zaatsu(a):
    a.sort()
    now = a[0][0]
    od = 0
    for i in range(n):
        if(now==a[i][0]):
            a[i][0]=od
        else:
            now = a[i][0]
            od+=1
            a[i][0] = od
    
    a.sort(key = lambda x : x[1])
    return a

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

def rl(x):
    return range(len(x))












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

city = list(map(int, input().split()))
city = [i-1 for i in city]

import itertools
p = list(itertools.permutations(range(r)))

dp = [[10**16 for i in range(n)] for j in range(n)]
for i in range(n):
    dp[i][i] = 0

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



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

ans = 10**16
for i in p:
    dist = 0
    for j in range(r-1):
            dist += dp[city[i[j]]][city[i[j+1]]]

    ans = min(ans,dist)
    

print(ans)

Solution (Python):

from sys import stdin
from itertools import permutations
N,M,R = [int(x) for x in stdin.readline().rstrip().split()]
r = [int(x) for x in stdin.readline().rstrip().split()]
cost = [[10**9]*(N+1) for i in range(N+1)]

for i in range(M):
    A,B,C = [int(x) for x in stdin.readline().rstrip().split()]
    cost[A][B] = C
    cost[B][A] = C
    
for k in range(N+1):
    for i in range(N+1):
        for j in range(N+1):
            cost[i][j] = min(cost[i][j],cost[i][k]+cost[k][j])
            cost[j][i] = min(cost[j][i],cost[k][i]+cost[j][k])

ans = 10**9+7

for l in permutations(r):
    ans_tmp = 0
    for m in range(R-1):
        tmp1,tmp2 = l[m],l[m+1]
        ans_tmp += cost[tmp1][tmp2]
    ans = min(ans,ans_tmp)
    
print(ans)

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

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

edge = np.zeros((N+1,N+1))
for _ in range(M):
  A,B,C = map(int,input().split())
  edge[A,B] = C  
dist = shortest_path(edge, directed = False).astype(int)

answer = 10**18
for visit in itertools.permutations(r):
  p = 0
  prev = visit[0]
  for x in visit[1:]:
    if prev != None:
      p += dist[prev,x]
    prev = x
  answer = min(answer,p)
  
print(answer)