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:
from itertools import permutations

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    n=len(d[0])
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
    return d

INF = float("inf")

N,M,R=[int(x) for x in input().split()]
r=[int(x)-1 for x in input().split()]

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

for i in range(M):
    a,b,c=[int(x) for x in input().split()]
    route_list[a-1][b-1]=c
    route_list[b-1][a-1]=c

wa_list=warshall_floyd(route_list)
ans=30**9

for perm in permutations(r):
    #print(perm)
    cur = sum(wa_list[v][u] for v, u in zip(perm, perm[1:]))
    ans = min(ans, cur)

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
 
 
def warshall_floyd(d):
    # d        : nxn adjacent matrix
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
 
 
INF = float("inf")
 
n, m, r = map(int, input().split())
r_list = list(map(lambda x: int(x) - 1, input().split()))
d = [[INF] * n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    d[a][b] = d[b][a] = c
warshall_floyd(d)
 
ans = float("inf")
for np in permutations(r_list):
    cand = sum([d[np[i]][np[i + 1]] for i in range(r - 1)])
    ans = min(ans, cand)
 
print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse import *
from itertools import *
 
n,m,r = [int(x) for x in input().split()]
R = [int(i)-1 for i in input().split()]
route_list = [[0]*n for i in range(n)]
ans = 10**9
for j in range(m):
  a,b,c = map(int,input().split())
  route_list[a-1][b-1] = c
  route_list[b-1][a-1] = c
 
Co = csgraph.floyd_warshall(route_list)
 
for v in permutations(R):
  temp = 0
  for i in range(1,r):
    temp += Co[v[i-1]][v[i]]
  ans = min(ans,temp)
print(int(ans))

Submission status: Accepted

Solution code:
from scipy.sparse import *
from itertools import *
 
n,m,r = [int(x) for x in input().split()]
R = [int(i)-1 for i in input().split()]
route_list = [[10**8]*n for i in range(n)]
ans = 10**9
for j in range(m):
  a,b,c = map(int,input().split())
  route_list[a-1][b-1] = c
  route_list[b-1][a-1] = c
 
Co = csgraph.floyd_warshall(csr_matrix(route_list))
 
for v in permutations(R):
  temp = 0
  for i in range(1,r):
    temp += Co[v[i-1]][v[i]]
  ans = min(ans,temp)
print(int(ans))

Submission status: Accepted

Solution code:
from scipy.sparse import *
from itertools import *

n,m,r = [int(x) for x in input().split()]
R = [int(i)-1 for i in input().split()]
route_list = [[0]*n for i in range(n)]
ans = 10**9
for j in range(m):
  a,b,c = map(int,input().split())
  route_list[a-1][b-1] = c
  route_list[b-1][a-1] = c
 
Co = csgraph.floyd_warshall(csr_matrix(route_list))
 
for v in permutations(R):
  temp = 0
  for i in range(1,r):
    temp += Co[v[i-1]][v[i]]
  ans = min(ans,temp)
print(int(ans))

Submission status: Accepted

Solution code:
import math
from itertools import permutations

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    n=len(d[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])
    return d

N,M,R=[int(x) for x in input().split()]
r=[int(x)-1 for x in input().split()]

route_list=[[10**9]*N for i in range(N)]

for i in range(M):
    a,b,c=[int(x) for x in input().split()]
    route_list[a-1][b-1]=c
    route_list[b-1][a-1]=c

wa_list=warshall_floyd(route_list)
ans=30**9

for perm in permutations(r):
    #print(perm)
    cur = sum(wa_list[v][u] for v, u in zip(perm, perm[1:]))
    ans = min(ans, cur)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra
import itertools
from scipy.sparse import csr_matrix
inf = 1 + 10**8
n, m, r = list(map(int, input().split()))
r = list(map(int, input().split()))
graph = np.full((n+1,n+1), inf)
for i in range(m):
    a,b,c = list(map(int, input().split()))
    graph[a][b] = c
    graph[b][a] = c
p_list = list(itertools.permutations(r,len(r)))
graph = dijkstra(csr_matrix(graph))
min_cost = inf * 200
for i in p_list:
    candidate = 0
    for j in range(len(i) - 1):
        candidate += graph[i[j]][i[j + 1]]
    if min_cost > candidate:
        min_cost = candidate
print(int(min_cost))

Submission status: Accepted

Solution code:
def warshall_floyd(n,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
##################################################################
import itertools
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')

N, M, R = LI()
r = LI()
cur = 0
ans = inf
d = [[float("inf") for i in range(N)] for i in range(N)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)
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 #自身のところに行くコストは０
#print(warshall_floyd(N,d))
W = warshall_floyd(N,d)
loop = int(1)
#for i in range(len(r)):
#    loop *=(i+1)
for course in itertools.permutations(r):
    cur = int(0)
    for i in range(len(course)-1):
        to = course[i+1]
        go = course[i]
        cur += W[go-1][to-1]
    ans = min(ans,cur)

print(ans)

Submission status: Accepted

Solution code:



def wantans(nowp,sc,rlis,ans):

    if len(rlis) == 0:
        ans = min(ans , sc)
        return ans

    for i in range(len(rlis)):

        nexsc = sc

        nexlis = []
        for j in range(len(rlis)):
            if i != j:
                nexlis.append(rlis[j])

        if nowp != None:
            nexsc += lis[nowp][rlis[i]]
            
        ans = wantans(rlis[i],nexsc,nexlis,ans)

    return ans
        




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

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

lis = [ [float("inf")] * N for i in range(N) ]

for i in range(N):

    lis[i][i] = 0

for i in range(M):

    A,B,C = map(int,input().split())

    A -= 1
    B -= 1

    lis[A][B] = C
    lis[B][A] = C

for k in range(N):

    for i in range(N):

        for j in range(N):

            lis[i][j] = min(lis[i][j],lis[i][k]+lis[k][j])



for i in range(R):
    r[i] -= 1
    
ans = wantans(None,0,r,float("inf"))

print (ans)

Submission status: Accepted

Solution code:
from itertools import permutations


class WarshallFloyd(object):

    def __init__(self, adj):
        """
        ワーシャル・フロイド法によって全頂点間の最短距離を O(|V|^3) で計算する。

        :param adj: 隣接行列 adj[i][j] でi番目の頂点からj番目の頂点へのコストを示す パスがなければINF
        """
        self._dist = adj  # 各頂点間の最短距離 初期値として隣接行列をそのまま用い、[i, i]要素を0に初期化する
        for i in range(len(adj)):
            self._dist[i][i] = 0

        self._solve()

    def _solve(self):
        v_len = len(self._dist)
        for i in range(v_len):  # 経由する頂点
            for j in range(v_len):  # 開始頂点
                for k in range(v_len):  # 終端
                    self._dist[j][k] = min(self._dist[j][k], self._dist[j][i] + self._dist[i][k])

    def distance(self, start, goal):
        return self._dist[start][goal]

    def path(self, start, goal):
        pass


N, M, R = map(int, input().split())
r = list(map(int, input().split()))
adj = [[float('inf') for _ in range(N + 1)] for _ in range(N + 1)]
for _ in range(M):
    A, B, C = map(int, input().split())
    adj[A][B] = C
    adj[B][A] = C

wf = WarshallFloyd(adj)

ans = float('inf')
tours = list(map(list, permutations(r, R)))
for tour in tours:
    cost = 0
    for i in range(1, len(tour)):
        cost += wf.distance(tour[i - 1], tour[i])
    ans = min(ans, cost)
print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m,R=map(int,input().split())
r=list(map(int,input().split()))
abc=[list(map(int,input().split())) for i in range(m)]
inf=float("inf")
data=[[inf]*(n+1) for i in range(n+1)]
for i in range(n+1):
    data[i][i]=0
for u in abc:
    a,b,c=u
    data[a][b]=c
    data[b][a]=c
for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            data[i][j]=min(data[i][j],data[i][k]+data[k][j])
ans=inf
for h in itertools.permutations(r):
    l=0
    for j in range(1,R):
        l+=data[h[j-1]][h[j]]
    ans=min(ans,l)
print(ans)

Submission status: Accepted

Solution code:
import math
import itertools
import sys
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N, M, R = IL()
r = IL()
abc = [IL() for _ in range(M)]

dp = [[MAX_INT]*(N+1) for _ in range(N+1)]
for a, b, c in abc:
  dp[a][b] = c
  dp[b][a] = c

for k in range(1, N+1):
  for i in range(1, N+1):
    for j in range(1, N+1):
      if i == j:
        dp[i][j] = 0
      else:
        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
#print(dp)

ans = MAX_INT
for root in itertools.permutations(r):
  tmp = 0
  for i in range(R-1):
    tmp += dp[root[i]][root[i + 1]]
  else:
    ans = min(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse import*
from itertools import*
n,m,r = map(int,input().split())
R = [int(i)-1 for i in input().split()]
cost = [[0]*n for i in range(n)]
ans = 10**9
for j in range(m):
  a,b,c = map(int,input().split())
  cost[a-1][b-1] = c
  cost[b-1][a-1] = c

Co = csgraph.floyd_warshall(csr_matrix(cost))

for v in permutations(R):
  temp = 0
  for i in range(1,r):
    temp += Co[v[i-1]][v[i]]
  ans = min(ans,temp)
print(int(ans))

Submission status: Accepted

Solution code:
import sys
import itertools


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    wn, wm, r = list(map(int, input().rstrip('\n').split()))
    r = list(map(int, input().rstrip('\n').split()))
    inf = 10 ** 13
    wl = [[inf] * wn for _ in range(wn)]
    for i in range(wn):
        wl[i][i] = 0

    for i in range(wm):
        wa, wb, wc = list(map(int, input().rstrip('\n').split()))
        wl[wa - 1][wb - 1] = wc
        wl[wb - 1][wa - 1] = wc

    for i in range(wn):
        for j in range(wn):
            for k in range(wn):
                wl[j][k] = min(wl[j][k], wl[j][i] + wl[i][k])

    md = 10 ** 10
    for v in itertools.permutations(r, len(r)):
        l = 0
        d = 0
        for i, vv in enumerate(v):
            if i == 0:
                l = vv - 1
            else:
                d += wl[l][vv-1]
                l = vv-1
        md = min(md, d)
    print(md)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from itertools import permutations

inf = float('inf')
n, m, r = map(int, input().split())  # 町数、道数、訪問地数
t = tuple(int(x) - 1 for x in input().split())  # 訪問地
g = [[inf] * n for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    g[a][b] = c
    g[b][a] = c

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

ans = inf
for p in permutations(t):
    ans = min(ans, sum(g[a][b] for a, b in zip(p, p[1:])))
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations


def warshall_floyd(d):
    # d        : nxn adjacent matrix
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]


INF = float("inf")

n, m, r = map(int, input().split())
r_list = list(map(lambda x: int(x) - 1, input().split()))
d = [[INF] * n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    d[a][b] = d[b][a] = c
warshall_floyd(d)

ans = float("inf")
for np in permutations(r_list):
    cand = sum([d[np[i]][np[i + 1]] for i in range(r - 1)])
    ans = min(ans, cand)

print(ans)

Submission status: Accepted

Solution code:
def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d
import itertools
N,M,R=[int(x) for x in input().split()]
r=[int(x) for x in input().split()]
cost = [[float("inf") for i in range(N)] for i in range(N)] 
d=[[0]*N for _ in range(N)]
for i in range(M):
  x,y,z = [int(x) for x in input().split()]
  cost[x-1][y-1]=z
  cost[y-1][x-1]=z
for i in range(N):
  d[i]=dijkstra(i,N,M,cost)
r=list(itertools.permutations(r))
ans=10**9
for i in r:
  res=0
  for j in range(len(i)-1):
    res+=d[i[j]-1][i[j+1]-1]
  ans=min(ans,res)
print(ans)

Submission status: Accepted

Solution code:
n,m,k1=map(int,input().split())
mat=[[10**9 for j in range(n)]for i in range(n)]
r=[int(i)-1 for i in input().split()]
for i in range(m):
    a,b,c=map(int,input().split())
    mat[a-1][b-1]=c 
    mat[b-1][a-1]=c
for i in range(n):
    mat[i][i]=0 
dp=[[10**9 for j in range(n)]for i in range(n)]
for i in range(n):
    dp[i][i]=0 
for k in range(n):
    for i in range(n):
        for j in range(n):
            if mat[k][j]==10**9:
                continue 
            mat[i][j]=min(mat[i][j], mat[i][k]+mat[k][j])
            mat[j][i]=mat[i][j]
#print(dp)\
dp=mat 
mini=10**100 
#print(dp[2][3]+dp[3][1])
from itertools import permutations
for i in permutations(r) : 
    ans=0 
   # print(i)
    for j in range(1,k1): 
        ans+=dp[i[j-1]][i[j]]
    #print(i,ans)
    mini=min(mini,ans)
print(mini)

Submission status: Accepted

Solution code:
# __name__宣言が無いと300msほど？遅くなってTLEになるらしい。今後気をつけよう。。。

import itertools

def main():
  n, m, r = map(int, input().split())
  list_r = [one_r-1 for one_r in map(int, input().split())]

  dist = [[float("inf")] * n for _ in range(n)]
  for i in range(n):
    dist[i][i] = 0
  for i 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):
        if dist[i][j] > dist[i][k] + dist[k][j]:
          dist[i][j] = dist[i][k] + dist[k][j]

  result = float("inf")
  for one_cand in itertools.permutations(list_r):
    temp = 0
    for i in range(r-1):
      temp += dist[one_cand[i]][one_cand[i+1]]
    if temp < result:
      result = temp
  print(result)
  

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import itertools

def main():
  n, m, r = map(int, input().split())
  list_r = [one_r-1 for one_r in map(int, input().split())]

  dist = [[float("inf")] * n for _ in range(n)]
  for i in range(n):
    dist[i][i] = 0
  for i 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):
        if dist[i][j] > dist[i][k] + dist[k][j]:
          dist[i][j] = dist[i][k] + dist[k][j]

  result = float("inf")
  for one_cand in itertools.permutations(list_r):
    temp = 0
    for i in range(r-1):
      temp += dist[one_cand[i]][one_cand[i+1]]
    if temp < result:
      result = temp
  print(result)
  

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
from itertools import permutations
import sys

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall

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

G = [[10**8]*(N+1) for _ in range(N+1)]   # 1-indexed
for _ in range(M):
    A, B, C = map(int, input().split())
    # 無向グラフ
    G[A][B] = C
    G[B][A] = C

    # 有向グラフ
    # G[A][B]=C

dg = csgraph_from_dense(G, null_value=10**8)
d = floyd_warshall(dg)


ans = 10**12
for Q in itertools.permutations(r):
    c = 0
    for i in range(R-1):
        c += d[Q[i]][Q[i+1]]
    ans = min(ans, c)
print(int(ans))

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
from itertools import permutations

N, M, R = map(int, input().split())
r = list(input().split())
edge = np.array([input().split() for _ in range(M)], dtype = np.int64).T
graph = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))

lst = floyd_warshall(graph, directed = False)
# print (lst)
def calc(path):
    cost = 0
    s = int(path[0]) - 1
    for i in range(1, R):
        g = int(path[i]) - 1
        cost += lst[s, g]
        s = g
    return cost

ans = 10 ** 18
for tmp in permutations(r):
    # print (tmp)
    ans = min(ans, calc(tmp))

print (int(ans))

Submission status: Accepted

Solution code:
def resolve():
    
    N,M,R = map(int,input().split())
    r = list(map(int,input().split()))
    DP = [[2 ** 63 - 1 for _ in range(N)] for _ in range(N)]

    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][k]+DP[k][j],DP[i][j])

    import itertools
    ans = 2 ** 63 - 1 
    for v in itertools.permutations(r,R):
        s = 0
        for i in range(R-1):
            s += DP[v[i]-1][v[i+1]-1]
        ans = min(ans,s)
    print(ans)
resolve()

Submission status: Accepted

Solution code:
import itertools
n,m,R = map(int,input().split())
r = list(map(int,input().split()))
cost = [[-1]*n for i in range(n)]
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):
            if k == i or k == j or cost[i][k] == -1 or cost[k][j] == -1:
                continue
            if cost[i][j] == -1:
                cost[i][j] = cost[i][k]+cost[k][j]
            else:
                cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j])

ans = -1
for p in itertools.permutations(r):
    c = 0
    for i in range(R-1):
        c += cost[p[i]-1][p[i+1]-1]
    if ans == -1:
        ans = c
    else:
        ans = min(c, ans)
print(ans)

Submission status: Accepted

Solution code:
import heapq
import itertools


class Graph:
    def __init__(self, n_nodes):
        self.n_nodes = n_nodes
        self.edges = [[] for _ in range(n_nodes)]

    def add_edge(self, s, t, d=None, undirected=False):
        if d is not None:
            self.edges[s].append((t, d))
        else:
            self.edges[s].append(t)
        if undirected:
            self.add_edge(t, s, d)

    def add_edges(self, edges, undirected=False):
        for edge in edges:
            self.add_edge(*edge, undirected=undirected)


class Dijkstra:
    def __init__(self, graph):
        self.graph = graph

    def compute_all(self, s):
        distances = [float('inf') for _ in range(self.graph.n_nodes)]
        visited = [False for _ in range(self.graph.n_nodes)]
        prev_nodes = [None for _ in range(self.graph.n_nodes)]
        distances[s] = 0
        q = []
        for t in range(self.graph.n_nodes):
            heapq.heappush(q, (distances[t], t))
        while q:
            dist_x, x = heapq.heappop(q)
            if visited[x]:
                continue
            visited[x] = True

            for y, d_xy in self.graph.edges[x]:
                if visited[y]:
                    continue
                dist_y = dist_x + d_xy
                if dist_y < distances[y]:
                    distances[y] = dist_y
                    prev_nodes[y] = x
                    heapq.heappush(q, (dist_y, y))
        return distances, prev_nodes


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

graph = Graph(n + 1)
graph.add_edges([list(map(int,
                          input().split())) for _ in range(m)],
                undirected=True)
dijkstra = Dijkstra(graph)
distances = []
for i in range(n + 1):
    ds, _ = dijkstra.compute_all(i)
    distances.append(ds)
res = float('inf')
for perm in itertools.permutations(rs):
    s = sum([distances[a][b] for a, b in zip(perm, perm[1:])])
    res = min(res, s)
print(res)

Submission status: Accepted

Solution code:
# ABC073D - joisino's travel
from heapq import heappop, heappush
from itertools import permutations


def dijkstra(source: int) -> "Array[int]":
    # compute the distance of the shortest path from V_source to each vertex
    size = len(G)
    dist = [float("inf")] * size
    dist[source] = 0
    undetermined = size - 2  # V_0 and V_source are determined in 1-idx graph
    queue = [(0, source)]
    while queue:
        cost, v = heappop(queue)
        if cost > dist[v]:
            continue
        for next_cost, u in G[v]:
            if cost + next_cost < dist[u]:
                dist[u] = cost + next_cost
                heappush(queue, (dist[u], u))
        undetermined -= 1
        if not undetermined:
            return dist
    return dist


def main():
    global G
    N, M, R, *RABC = map(int, open(0).read().split())
    visit, ABC = RABC[:R], RABC[R:]
    G = [[] for _ in range(N + 1)]
    for v, u, cost in zip(*[iter(ABC)] * 3):
        G[v].append((cost, u)), G[u].append((cost, v))
    dist = {v: dijkstra(v) for v in visit}
    ans = float("inf")
    for perm in permutations(visit):
        cur = sum(dist[v][u] for v, u in zip(perm, perm[1:]))
        ans = min(ans, cur)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC073D - joisino's travel (210ms)
from heapq import heapify, heappop, heappush
from itertools import permutations


def dijkstra(source: int) -> list:
    dist = [float("inf")] * (N + 1)
    undetermined = N  # vertex_0 won't appear in 1-idx graph
    queue = [(0, source)]
    heapify(queue)
    while queue:
        cost, v = heappop(queue)
        if cost > dist[v]:
            continue
        dist[v] = cost
        for next_cost, u in G[v]:
            if cost + next_cost < dist[u]:
                heappush(queue, (cost + next_cost, u))
        undetermined -= 1
        if not undetermined:
            return dist


def main():
    global G, N
    N, M, R, *RABC = map(int, open(0).read().split())
    visit, ABC = RABC[:R], RABC[R:]
    G = [[] for _ in range(N + 1)]
    for v, u, cost in zip(*[iter(ABC)] * 3):
        G[v].append((cost, u)), G[u].append((cost, v))
    dist = {v: dijkstra(v) for v in visit}
    ans = float("inf")
    for perm in permutations(visit):
        cur = sum(dist[v][u] for v, u in zip(perm, perm[1:]))
        ans = min(ans, cur)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC073D - joisino's travel
from heapq import heapify, heappop, heappush
from itertools import permutations


def dijkstra(G: "Array[Array[int]]", size: int, start: int) -> list:
    dist = [float("inf")] * size
    checked = [0] * size
    checked[0] = 1
    queue = [(0, start)]
    heapify(queue)
    while queue:
        cost, v = heappop(queue)
        if cost > dist[v]:
            continue
        dist[v] = cost
        for next_cost, u in G[v]:
            if cost + next_cost < dist[u]:
                heappush(queue, (cost + next_cost, u))
        checked[v] = 1
        if sum(checked) == size:
            return dist


def main():
    global G, N
    N, M, R, *RABC = map(int, open(0).read().split())
    visit, ABC = RABC[:R], RABC[R:]
    G = [[] for _ in range(N + 1)]
    for v, u, cost in zip(*[iter(ABC)] * 3):
        G[v].append((cost, u)), G[u].append((cost, v))
    dist = {v: dijkstra(G, N + 1, v) for v in visit}
    ans = float("inf")
    for perm in permutations(visit):
        cur = sum(dist[v][u] for v, u in zip(perm, perm[1:]))
        ans = min(ans, cur)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC073D - joisino's travel
from heapq import heapify, heappop, heappush
from itertools import permutations


def dijkstra(G: "Array[Array[int]]", size: int, start: int) -> list:
    dist = [1 << 30] * size
    unchecked = size - 1  # vertex_0 won't appear in 1-idx graph
    queue = [(0, start)]
    heapify(queue)
    while queue:
        cost, v = heappop(queue)
        if cost > dist[v]:
            continue
        dist[v] = cost
        for next_cost, u in G[v]:
            if cost + next_cost < dist[u]:
                heappush(queue, (cost + next_cost, u))
        unchecked -= 1
        if not unchecked:
            return dist


def main():
    global G, N
    N, M, R, *RABC = map(int, open(0).read().split())
    visit, ABC = RABC[:R], RABC[R:]
    G = [[] for _ in range(N + 1)]
    for v, u, cost in zip(*[iter(ABC)] * 3):
        G[v].append((cost, u)), G[u].append((cost, v))
    dist = {v: dijkstra(G, N + 1, v) for v in visit}
    ans = 1 << 60
    for perm in permutations(visit):
        cur = sum(dist[v][u] for v, u in zip(perm, perm[1:]))
        ans = min(ans, cur)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC073D - joisino's travel
from heapq import heapify, heappop, heappush
from itertools import permutations


def dijkstra(G: "Array[Array[int]]", size: int, start: int) -> list:
    dist = [1 << 60] * size
    unchecked = size - 1  # vertex_0 won't appear in 1-idx graph
    queue = [(0, start)]
    heapify(queue)
    while queue:
        cost, v = heappop(queue)
        if cost > dist[v]:
            continue
        dist[v] = cost
        for next_cost, u in G[v]:
            if cost + next_cost < dist[u]:
                heappush(queue, (cost + next_cost, u))
        unchecked -= 1
        if not unchecked:
            return dist


def main():
    global G, N
    N, M, R, *RABC = map(int, open(0).read().split())
    visit, ABC = RABC[:R], RABC[R:]
    G = [[] for _ in range(N + 1)]
    for v, u, cost in zip(*[iter(ABC)] * 3):
        G[v].append((cost, u)), G[u].append((cost, v))
    dist = {v: dijkstra(G, N + 1, v) for v in visit}
    ans = 1 << 60
    for perm in permutations(visit):
        cur = sum(dist[v][u] for v, u in zip(perm, perm[1:]))
        ans = min(ans, cur)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC073D - joisino's travel (218ms)
from heapq import heapify, heappop, heappush
from itertools import permutations


def dijkstra(G: "Array[Array[int]]", size: int, start: int) -> list:
    dist = [float("inf")] * size
    unchecked = size - 1  # vertex_0 won't appear in 1-idx graph
    queue = [(0, start)]
    heapify(queue)
    while queue:
        cost, v = heappop(queue)
        if cost > dist[v]:
            continue
        dist[v] = cost
        for next_cost, u in G[v]:
            if cost + next_cost < dist[u]:
                heappush(queue, (cost + next_cost, u))
        unchecked -= 1
        if not unchecked:
            return dist


def main():
    global G, N
    N, M, R, *RABC = map(int, open(0).read().split())
    visit, ABC = RABC[:R], RABC[R:]
    G = [[] for _ in range(N + 1)]
    for v, u, cost in zip(*[iter(ABC)] * 3):
        G[v].append((cost, u)), G[u].append((cost, v))
    dist = {v: dijkstra(G, N + 1, v) for v in visit}
    ans = float("inf")
    for perm in permutations(visit):
        cur = sum(dist[v][u] for v, u in zip(perm, perm[1:]))
        ans = min(ans, cur)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC073D - joisino's travel (218ms)
from heapq import heapify, heappop, heappush
from itertools import permutations


def dijkstra(G: "Array[Array[int]]", size: int, start: int) -> list:
    dist = [float("inf")] * size
    queue = [(0, start)]
    heapify(queue)
    while queue:
        cost, v = heappop(queue)
        if cost > dist[v]:
            continue
        dist[v] = cost
        for next_cost, u in G[v]:
            if cost + next_cost < dist[u]:
                heappush(queue, (cost + next_cost, u))
    return dist


def main():
    global G, N
    N, M, R, *RABC = map(int, open(0).read().split())
    visit, ABC = RABC[:R], RABC[R:]
    G = [[] for _ in range(N + 1)]
    for v, u, cost in zip(*[iter(ABC)] * 3):
        G[v].append((cost, u)), G[u].append((cost, v))
    dist = {v: dijkstra(G, N + 1, v) for v in visit}
    ans = float("inf")
    for perm in permutations(visit):
        cur = sum(dist[v][u] for v, u in zip(perm, perm[1:]))
        ans = min(ans, cur)
    print(ans)


if __name__ == "__main__":
    main()