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



Sample input:
3 3 3
1 2 3
1 2 1
2 3 1
3 1 4


Sample output:
2

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from itertools import permutations

    n, m, q = map(int, readline().split())
    r_ = list(map(int, readline().split()))
    r = [i-1 for i in r_]

    dist = [[10 ** 18] * n for _ in range(n)]

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

    for _ in range(m):
        a, b, c = map(int, readline().split())
        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])

    ans = 10 ** 18
    for per in permutations(range(q)):
        score = 0
        for i in range(q - 1):
            score += dist[r[per[i]]][r[per[i + 1]]]
        ans = min(ans, score)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import permutations

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    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())
moku = list(map(int,input().split()))
d = [[float("inf")]*n for i in range(n)] 

for i in range(m):
    x,y,z = map(int,input().split())
    d[x-1][y-1] = z
    d[y-1][x-1] = z
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
p = warshall_floyd(d)

a = [i for i in range(r)]
zyun = list(permutations(a))

ans = 10**9
for i in zyun:
    cou = 0
    for j in range(r-1):
        cou += p[moku[i[j]]-1][moku[i[j+1]]-1]
    ans = min(ans,cou)
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    # 負の閉路を持つ場合は'NEGATIVE CYCLE'を、そうでない場合には(i,j)成分に
    # 頂点iから頂点jへの最短経路の距離を格納するdist_listをprintする関数
    def warshall_floyd(v_num, dist_lst):
        # 負の閉路を持つか
        negative_cycle_flag = False
    
        # 頂点iから頂点jへの経路と、頂点kを経由した場合の経路とを比較して
        # よりコストの合計が小さい方を配列に入れる動的計画法
        for k in range(v_num):
            for i in range(v_num):
                for j in range(v_num):
                    # i→k→jがつながっててしかもi→jルートよりもイケてるなら更新
                    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):
            # dist_lstに負の数が格納されているとは、
            # グラフが負の閉路を持つことを意味する
            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()))
    
    # 配列dist_lst[a][b]には頂点a,b間の辺のコストを入れておき、
    # a=bの時は0を、a,b間の辺が存在しないときはINFを入れておく。
    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()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

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

#############
# Functions #
#############

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

######OUTPUT######
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()

#####Shorten#####
def DD(arg): return defaultdict(arg)

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

######Combination######
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

######Factorization######
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

#####MakeDivisors######
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

#####MakePrimes######
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

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

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

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

#####ChangeBase#####
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]

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

#############
# Main Code #
#############

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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
#coding: utf-8
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)

Submission status: Accepted

Solution code:
# coding: utf-8
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)

Submission status: Accepted

Solution code:
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):
    #d[i][j]: iからjへの最短距離
    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
#print(G)
for i in range(N):
    G[i][i] = 0 #自身のところに行くコストは０
warshall_floyd(G)


#print(G)

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

Submission status: Accepted

Solution code:
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"):    # i -> j間に辺がある場合、ひとまずiをdestに行く直前のnodeとしておく
                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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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): #s:list, k:set
  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)

Submission status: Accepted

Solution code:
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)]))

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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


#############
# Main Code #
#############

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):
        # i:start j:goal k:中間地点でループ回す
        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

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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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])

# print (d)
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)

Submission status: Accepted

Solution code:
import math
#import sys
#input = sys.stdin.readline

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)

    # divisors.sort()
    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]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

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

# a = list(map(int, input().split()))

#################################################
#################################################
#################################################
#################################################



#52-

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

#print(dp)

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(dist,i)

print(ans)

#print(dp)

Submission status: Accepted

Solution code:
#1-index
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)

Submission status: Accepted

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