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:
# ワーシャルフロイドで、各町間の最短距離の更新は200^3 = 8,000,000
# 訪れるべき町Rはたかだか8個なので、順番の全通りを試して8! = 約40000通り

import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall
from scipy.sparse import csr_matrix

N,M,R = map(int,input().split())
r = list(map(int,input().split()))
r = list(map(lambda x:x-1,r))

E = [[0 for j in range(N)] for i in range(N)]
for i in range(M):
  a,b,c = map(int,input().split())
  E[a-1][b-1] = c
  E[b-1][a-1] = c

E = np.array(E)
E = shortest_path(E,method = "FW")

# DFSですべての数を試す
stack = []
for i in range(len(r)):
  stack.append([r[i],[],0])
ans = 10 ** 18
while stack:
  v,visited,dist = stack.pop()
  if len(visited) != 0:
    dist += E[visited[-1]][v]
  visited2 = visited.copy()
  visited2.append(v)
  if len(visited2) == len(r):
    if dist < ans:
      ans = dist
    continue
  for i in range(len(r)):
    if r[i] not in visited2:
      stack.append([r[i],visited2,dist])
    
print(int(ans))

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
from itertools import permutations

n,m,R = map(int, input().split())
r = list(map(int, input().split()))
r = [i-1 for i in r]
abc = [list(map(int, input().split())) for i in range(m)]
edge = [[10 ** 9] * (n) for i in range(n)]
for a,b,c in abc:
  a-=1
  b-=1
  edge[a][b] = c
  edge[b][a] = c
d = floyd_warshall(edge)
ans = 10 ** 18
for i in permutations(r):
  tmp = 0
  for j in range(R-1):
    tmp += d[i[j]][i[j+1]]
  ans = min(ans,tmp)
print(int(ans))

Submission status: Accepted

Solution code:
t,r,g=map(int,input().split())
d=[[float("INF") for ccc in range(t)] for i in range(t)]
for i in range(t):
    d[i][i]=0
gl=list(map(int,input().split()))
for j in range(r):
    x,y,c=map(int,input().split())
    d[x-1][y-1]=c
    d[y-1][x-1]=c
for i in range(t):
    for j in range(t):
        for k in range(t):
            d[k][j]=min(d[k][j],d[k][i]+d[i][j])
from itertools import permutations as pe
ans=float("INF")
for G in pe(gl):
    p=0
    for qw in range(g-1):
        p+=d[G[qw]-1][G[qw+1]-1]
    ans=min(ans,p)
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

class WarshallFloyd():
    def __init__(self, N):
        self.N = N
        self.d = [[float("inf") for i in range(N)]
                  for i in range(N)]  # d[u][v] : 辺uvのコスト(存在しないときは'inf')

    def add(self, u, v, c, directed=False):
        """
        0-indexedであることに注意
        u = from, v = to, c = cost
        directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.d[u][v] = c
            self.d[v][u] = c
        else:
            self.d[u][v] = c

    def WarshallFloyd_search(self):
        # これを d[i][j]: iからjへの最短距離 にする
        # 本来無向グラフでのみ全域木を考えるが、二重辺なら有向でも行ける
        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])
        for i in range(self.N):
            self.d[i][i] = 0
        return self.d

n,m,o = na()
r = na()
g = WarshallFloyd(n)

for i in range(m):
    a,b,c = na()
    g.add(a-1,b-1,c)

import itertools
p = min(8,n)
rs = list(itertools.permutations(r))

ans = 10000000000000
d = g.WarshallFloyd_search()
for l in rs:
    q = 0
    for j in range(len(l)-1):
        q += d[l[j+1]-1][l[j]-1]
    ans = min(ans, q)

print(ans)

Submission status: Accepted

Solution code:
import itertools 

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

class WarshallFloyd:
    def __init__(self,n):
        self.v = n
        self.d = [[1e100]*n for _ in range(n)]
        for i in range(n):
            self.d[i][i] = 0

    def path(self,x,y,c):
        if x == y:
            return False
        self.d[x][y] = c
        self.d[y][x] = c
        return True

    def build(self):
        for k in range(self.v):
            for i in range(self.v):
                for j in range(self.v):
                    self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])
        return self.d
wf = WarshallFloyd(N)

for i in range(M):
    a,b,c = map(int,input().split())
    wf.path(a-1,b-1,c)

d = wf.build()
ans = 1e100
for T in itertools.permutations(r):
    Td = 0
    for i in range(len(T) - 1):
        Td += d[T[i]-1][T[i+1] - 1]
    ans = min(ans , Td)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
INF = 10 ** 8
N, M, R = map(int,input().split())
r = list(map(lambda x: int(x)-1 ,input().split()))
MAP = [[INF for i in range(N)] for j in range(N)]
for i in range(M):
    A, B, C = map(int,input().split())
    MAP[A-1][B-1] = C
    MAP[B-1][A-1] = C
for k in range(N):
    for i in range(N):
        for j in range(N):
            MAP[i][j] = min(MAP[i][j], MAP[i][k] + MAP[k][j])

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

Submission status: Accepted

Solution code:
# solution

import itertools
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

int1 = lambda x: int(x) - 1

N, M, R = map(int, input().split())
T = sorted(list(map(int1, input().split())))
A = np.array([tuple(map(int, input().split())) for _ in range(M)]).T

matr = csr_matrix((A[2], (A[0] - 1, A[1] - 1)), shape=(N, N))
way = [dijkstra(matr, indices=t, directed=False)[T].astype(int).tolist() for t in T]

result = float('inf')
for t in itertools.permutations(range(R)):
    tmp = 0
    for i in range(R - 1):
        tmp += way[t[i]][t[i + 1]]
    result = min(result, tmp)
print(result)

Submission status: Accepted

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

from itertools import permutations


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

D = [[float("inf")] * (n + 1) for _ in range(n + 1)]
for i in range(n + 1):
    D[i][i] = 0
for _ in range(m):
    a, b, c = map(int, input().split())
    D[a][b] = c; D[b][a] = c

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

P = list(permutations(R))

answer = float("inf")
for p in P:
    temporary = 0
    for k in range(r - 1):
        i, j = p[k], p[k + 1]
        temporary += D[i][j]
    answer = min(answer, temporary)

print(answer)

Submission status: Accepted

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

n,m,r= map(int, input().split())
rr= list(map(int, input().split()))
a= [list(map(int, input().split())) for i in range(m)]
d=[[float('inf')]*n for i in range(n)]
for i in range(n):
    d[i][i]=0

for i,j,k in a:
    i-=1
    j-=1
    d[i][j]=k
    d[j][i]=k


# ワーシャルフロイド　全点最短経路、負の距離あっても可　o(n**3)
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
d=warshall_floyd(d)


# bit DP
# dp[S][v]: 訪れた点の集合がSで最後にVを訪れた時のVのMIN
INF=float('inf')
dp=[[INF]*r for i in range(1<<r)]
dp[0]=[0]*r

for i in range(1<<r):
    for k in range(r):
        # 訪問リストに入っているものを最後に訪問する時
        if (i >> k) & 1:
            if i^(1<<k)==0:
                dp[i][k]=0
            else:
                # 最後に訪れるものを除いた集合でどこを最後に訪問した時がminか調べる
                for l in range(r):
                    if (i ^ (1 << k))>>l:
                        dpm = dp[i ^ (1 << k)][l]
                        ad = d[rr[l] - 1][ rr[k] - 1]
                        dp[i][k] = min(dpm + ad, dp[i][k])

print(min(dp[-1]))

Submission status: Accepted

Solution code:
import itertools
n,m,r = map(int,input().split())
ri = [int(i) for i in input().split()]
#abc = [[int(i) for i in input().split()] for j in range(m)]

mat=[[10**18 for i in range(n+1)] for j in range(n+1)]

for i in range(n+1):
	mat[i][i]=0

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

for i in range(1,n+1):
	for x in range(1,n+1):
		for y in range(1,n+1):
			mat[x][y] = min(mat[x][y], mat[x][i] + mat[i][y])
            
            
permutations = list(itertools.permutations(range(1, r+1)))
#p = permutations.index(p)

#print(mat)
#exit()
ans = 10**18

for i in range(len(permutations)):
    tmp = 0
    for j in range(r-1):
        #print(permutations[i][j],permutations[i][j+1])
        tmp += mat[ri[permutations[i][j]-1]][ri[permutations[i][j+1]-1]]
    ans = min(ans,tmp)
    #print(permutations[i][0])
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from itertools import permutations

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

def main():
    N, M, R = map(int, input().split())
    A = [int(i)-1 for i in input().split()]
    inf = float('inf')
    G = [[inf] * N for _ in range(N)]
    for i in range(N):
        G[i][i] = 0
    for _ in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        G[a][b] = min(G[a][b], c)
        G[b][a] = min(G[b][a], c)
    warshall_floyd(G)
    ans = float('inf')
    for perm in permutations(A, R):
        tmp = 0
        for i in range(R-1):
            tmp += G[perm[i]][perm[i+1]]
        ans = min(ans, tmp)
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Accepted

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

import sys
input = sys.stdin.readline
n,m,r = map(int,input().split())
R = [int(i)-1 for i in input().split()]
d = [[10**9]*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
    
chk = tuple(warshall_floyd(d))
ans = float('inf')

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

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from pprint import pprint

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

n,m,R = myinput()
r = list(myinput())
abc = mylistinput(m)

d = [[float("inf")]*n for i in range(n)] 
# d[u][v]: 辺uvのコスト(存在しないときはinf)

for i in range(m):
    a = abc[i][0] - 1
    b = abc[i][1] - 1
    c = abc[i][2]
    d[a][b] = c
    d[b][a] = c

#自身のところに行くコストは０
for i in range(n):
    d[i][i] = 0 

# ワーシャルフロイド（warshall_floyd）法
# d[u][v]: 辺uvのコスト(存在しないときはinf)
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

d = warshall_floyd(n,d)
# print(d)

rp = list(permutations(r))
# print(rp)

ls_count = []
for i in rp:
    count = 0
    for j in range(len(i)-1):
        s = i[j] - 1
        t = i[j+1] - 1
        count += d[s][t]
    ls_count.append(count)
# print(ls_count)

ans = min(ls_count)
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from itertools import permutations
input = sys.stdin.buffer.readline

n, m, R = map(int, input().split())
r = list(map(int, input().split()))
INF = 10**10
dist = [[INF for _ in range(n)] for _ in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    dist[a][b] = c
    dist[b][a] = c

def warshall_floyd(n, d):
    # 空間計算量: O(n^2)
    # 時間計算量: O(n^3)
    # よって、n <= 10^2程度が限界
    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

dist = warshall_floyd(n, dist)
ans = INF
for t in permutations(r):
    ans_t = 0
    for i in range(R-1):
        ans_t += dist[t[i]-1][t[i+1]-1]
    ans = min(ans, ans_t)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations


def main():
    N, M, R = map(int, input().split())
    r = list(map(lambda x: int(x) - 1, input().split()))
    dist = [[1001001001 for _ in range(N)] for _ in range(N)]

    for _ in range(M):
        a, b, c = map(int, input().split())
        a, b = a - 1, b - 1
        dist[a][b] = c
        dist[b][a] = c
    for i in range(N):
        dist[i][i] = 0

    # warshall-floyd
    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 = 1001001001
    for way in permutations(r):
        ans_now = 0
        for i in range(R - 1):
            ans_now += dist[way[i]][way[i + 1]]
        if ans > ans_now: ans = ans_now
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

from itertools import permutations


def submit():
    n, m, _ = map(int, input().split())
    rlist = list(map(int, input().split()))
    rlist = [r - 1 for r in rlist]

    # warshall floyd
    dp = [[float('inf') for _ in range(n)] for _ in range(n)]
    for i in range(n):
        dp[i][i] = 0
    for _ in range(m):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        dp[a][b] = 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])

    
    min_cost = float('inf')
    for pt in permutations(rlist):
        cost = 0
        for i in range(len(pt) - 1):
            cost += dp[pt[i]][pt[i + 1]]
        
        if min_cost > cost:
            min_cost = cost

    print(min_cost)


submit()

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

n,m,r=map(int,input().split())
r=list(map(int,input().split()))
abc=[list(map(int,input().split())) for i in range(m)]

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


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 = abc[i]
    x-=1
    y-=1
    d[x][y] = z
    d[y][x] = z
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
warshall_floyd(d)

lst=list(permutations(r))
# print(lst)

ans=float('inf')
for i in range(len(lst)):
    tmp=0
    for j in range(len(lst[i])-1):
        tmp+=d[lst[i][j+1]-1][lst[i][j]-1]
    ans=min(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
INF = 10 ** 8
import itertools

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

G = [[INF] * N for _ in range(N)]
for i in range(N):
    G[i][i] = 0
for el in ABC:
    a, b, c = el
    G[a-1][b-1] = c
    G[b-1][a-1] = c

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

#print(G)
p = itertools.permutations(r)
m = INF
for el in p:
    #print(el)
    dist = 0
    for i in range(R - 1):
        dist += G[el[i] - 1][el[i + 1] - 1]
    m = min(m, dist)
print(m)

Submission status: Accepted

Solution code:
from itertools import product,permutations

n,m,R = map(int,input().split())
r = list(map(int,input().split()))
INF = 10**10
d = [[INF for i in range(n)] for j in range(n)]

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

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

ans = INF

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

print(ans)

Submission status: Accepted

Solution code:
import copy
from collections import deque
n, m, r = map(int,input().split())
R = list(map(int, input().split()))

f_inf = float('inf')
wf = [[f_inf for _ in range(n+1)] for __ in range(n+1)]

tree = [[] for _ in range(n+1)]
for i in range(m):
    a, b, c = map(int, input().split())
    wf[a][b] = c
    wf[b][a] = c
for i in range(1, n+1):
    wf[i][i] = 0
for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            wf[i][j] = min(wf[i][j], wf[i][k]+wf[k][j])

all_type = []
def get_all_type(r, info, lon):
    if lon == len(info):
        return [info]
    result = []
    for i in r:
        if i in info:
            continue
        else:
            next_info = copy.deepcopy(info)
            next_info.append(i)
            result.extend(get_all_type(r, next_info, lon))
    return result

Result = []
for i in get_all_type(R, [], r):
    j = deque(i)
    x = j.popleft()
    result = 0
    while j:
        y = j.popleft()
        result += wf[x][y]
        x = y
    Result.append(result)
print(min(Result))

Submission status: Accepted

Solution code:
n,m,r  = map(int,input().split())
r_list = list(map(int,input().split()))
matrix = [[float("inf") for i in range(n)] for j in range(n)]
for c in range(n):
  matrix[c][c] = 0
for v in range(m):
  a,b,c = map(int,input().split())
  if matrix[a-1][b-1] > c:
    matrix[a-1][b-1] = c
    matrix[b-1][a-1] = c
import numpy as np
matrix = np.array(matrix)
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
load = shortest_path(matrix, directed=False)
import itertools
ans_list = []
for balls in itertools.permutations(r_list):
    balls = list(balls)
    ans = 0
    for i in range(1,len(r_list)):
      ans += load[balls[i-1]-1][balls[i]-1]
    ans_list.append(int(ans))
    
print(min(ans_list))

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    inf = 10**17
    #mod = 10**9 + 7

    N,M,R = map(int, input().split())
    r = list(map(int, input().split()))
    for i in range(R):
        r[i] -= 1

    def dijkstra_heap(start,edge):
        #始点から各頂点への最短距離(頂点番号:0~N-1)
        d = [inf]*N
        used = [False]*N
        d[start] = 0
        used[start] = True
        edgelist = []
        #a:重み(//), b:次の頂点(%)
        for a,b in edge[start]:
            heappush(edgelist,a*(10**6)+b)

        while len(edgelist):
            #まだ最短距離が決まっていない頂点の中から最小の距離のものを探す
            minedge = heappop(edgelist)
            if used[minedge%(10**6)]:
                continue
            node = minedge%(10**6)
            d[node] = minedge//(10**6)
            used[node] = True

            for e in edge[node]:
                if not used[e[1]]:
                    heappush(edgelist,(e[0]+d[node])*(10**6)+e[1])
        return d

    edge = [[] for i in range(N)]
    #edge[i] : iから出る道の[重み,行先]の配列
    for _ in range(M):
        x,y,z = map(int,input().split())
        edge[x-1].append((z,y-1))
        edge[y-1].append((z,x-1))

    kyori = []
    for i in r:
        kyori.append(dijkstra_heap(i,edge))
    
    res = inf
    for i in permutations(range(R), R):
        l = list(i)
        path = 0
        for j in range(R-1):
            path += kyori[l[j]][r[l[j+1]]]
        res = min(res, path)

    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

int1 = lambda x: int(x) - 1

N, M, R = map(int, input().split())
T = sorted(list(map(int1, input().split())))
A = np.array([tuple(map(int, input().split())) for _ in range(M)]).T

matr = csr_matrix((A[2], (A[0] - 1, A[1] - 1)), shape=(N, N))
way = [dijkstra(matr, indices=t, directed=False)[T].astype(int).tolist() for t in T]

ans = float('inf')
for t in itertools.permutations(range(R)):
    tmp = 0
    for i in range(R - 1):
        tmp += way[t[i]][t[i + 1]]
    ans = min(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from itertools import permutations
import numpy as np

HUGE = 10 ** 18

def main():
    n, m, r = map(int, input().split())
    togo = list(map(int, input().split()))
    adj_mat = [[HUGE for j in range(n)] for i in range(n)]
    for i in range(n):
        adj_mat[i][i] = HUGE
    for i in range(m):
        a, b, c = map(int, input().split())
        a0 = a - 1
        b0 = b - 1
        adj_mat[a0][b0] = c
        adj_mat[b0][a0] = c
    adj_mat = np.array(adj_mat)

    wf(adj_mat, n)

    res = HUGE
    for way in permutations(togo):
        assert len(way) > 1
        x = 0
        for i in range(len(way) - 1):
            x += adj_mat[way[i] - 1][way[i + 1] - 1]
        res = min(res, x)

    print(res)

def wf(adj_mat, n):
    for k in range(n):
        for i in range(n):
            adj_mat[i, :] = np.minimum(adj_mat[i, :], adj_mat[i][k] + adj_mat[k, :])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import copy

N,M,R=map(int,input().split())
r=list(map(int,input().split()))
d=[[10**15 for i in range(0,N+1)] for i in range(0,N+1)]
for i in range(0,M):
    a,b,c=map(int,input().split())
    d[a][b]=c
    d[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 d[i][j]>d[i][k]+d[k][j]:
                d[i][j]=d[i][k]+d[k][j]

ans=10**15
def dfs(load,cost,last):
    global ans
    if len(load)==R:
        if ans>cost:
            ans=cost

    elif len(load)!=0:
        for city in r:
            if not city in load:
                a=copy.copy(load)
                a.add(city)
                dfs(a,cost+d[last][city],city)

    else:
        for city in r:
            dfs(set([city]),0,city)



dfs(set([]),0,0)

print(ans)

Submission status: Accepted

Solution code:
import itertools


N,M,R = map(int,input().split())
r = list(map(int,input().split()))
INF = float('inf')
D = [[INF]*(N+1) for _ in range(N+1)]
for i in range(1,N+1):
    D[i][i] = 0

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

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

loads = list(itertools.permutations(r))
# for load in loads:
#     print(load)
ans = INF
#ans_load = None
for load in loads:
    temp = 0
    for i in range(R-1):
        temp += D[load[i]][load[i+1]]
    #print(load,temp)
    ans = min(temp,ans)
    # if temp < ans:
    #     ans = temp
    #     ans_load = load

print(ans)
#print(ans_load)

Submission status: Accepted

Solution code:
# coding: utf-8
from heapq import heappop, heappush
from itertools import permutations

N,M,R=map(int,input().split())
town=list(map(int,input().split()))
INF=10**9
G=[[INF for i in range(N+1)] for j in range(N+1)]

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

d=[[INF*10 for i in range(N+1)] for j in range(R)]

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

        used[u] = True
        
        if d[k][u] < d_u:
            continue
        
        for v in range(N+1):
            if not(used[v]) and d_u + G[u][v] < d[k][v]:
                d[k][v] = d_u + G[u][v]
                heappush(heap,(d[k][v],v))

ans=INF

L=[i for i in range(R)]

for v in permutations(L,R):
    D=0
    for i in range(R-1):
        D+=d[v[i]][town[v[i+1]]]
    ans=min(ans,D)
    
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
N, M, R = map(int, input().split())

# ワーシャフロイドで全点の最短経路を求める
# 訪問順を全列挙して全て試して、最も短いものが答えになる
# 計算量はワーシャルフロイドで200**3、全列挙で8!(40320)
# ワーシャルフロイドが間に合えばいけそう

r = list(map(lambda x: int(x)-1, input().split()))
edge = [[10**9] * N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    a, b = a-1, b-1
    edge[a][b] = c
    edge[b][a] = c

for k in range(N):
    for i in range(N):
        for j in range(N):
            edge[i][j] = min(edge[i][j], edge[i][k] + edge[k][j])
    
#print(edge)
ans = 10 ** 20
for per in permutations(r):
    tmp = 0
    for i in range(R-1):
        tmp += edge[per[i]][per[i+1]]
    ans = min(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m,r=map(int,input().split())
point=list(map(int,input().split()))
g=[[10**9]*n for i in range(n)]
for _ in range(m):
  u,v,c=map(int,input().split())
  g[u-1][v-1]=g[v-1][u-1]=c
for k in range(n):
  for i in range(n):
    for j in range(n):
      g[i][j]=min(g[i][j],g[i][k]+g[k][j])
for i in range(n):
  g[i][i]=0
ans=10**18
for v in itertools.permutations(point):
  tmp=0
  for i in range(r-1):
    tmp+=g[v[i]-1][v[i+1]-1]
  ans=min(ans,tmp)
print(ans)

Submission status: Accepted

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

from itertools import permutations
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
cost = np.ones((n,n))*float('inf')
for i in range(m):
    a,b,c = map(int,input().split())
    cost[a-1][b-1]=cost[b-1][a-1]=c
d = floyd_warshall(cost)
def main():
    m = float('inf')

    for j in permutations(r):
        l = 0
        for i in range(len(j)-1):
            s,t = j[i],j[i+1]
            l += d[s-1][t-1]
        if l<m:
            m = l
    print(int(m))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import permutations

N, M, R = map(int, input().split())
T = list(map(int, input().split()))
grid = [[float('inf')] * N for _ in range(N)]

for i in range(N):
    grid[i][i] = 0
for i in range(M):
    A, B, C = map(int, input().split())
    A -= 1; B -= 1
    if grid[A][B] > C:
        grid[A][B] = C
        grid[B][A] = C

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

ans = float('inf')
for path in permutations(T):
    cnt = 0
    for i in range(R - 1):
        s = path[i] - 1
        g = path[i + 1] - 1
        cnt += grid[s][g]
    ans = min(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
import itertools


def warshall_floyd(G):
    import copy
    ret = copy.deepcopy(G)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                ret[i][j] = min(ret[i][j], ret[i][k] + ret[k][j])
    return ret


N, M, R = map(int, input().split())
r = list(map(int, input().split()))
G = [[10 ** 10] * N for _ in range(N)]
for _ in range(M):
    A, B, C = map(int, input().split())
    G[A - 1][B - 1] = C
    G[B - 1][A - 1] = C
W, ans = warshall_floyd(G), 10 ** 10
for p in itertools.permutations(r, R):
    ans = min(ans, sum([W[p[i] - 1][p[i + 1] - 1] for i in range(R - 1)]))
print(ans)

Submission status: Accepted

Solution code:
import heapq
import itertools
n, m, r = map(int, input().split())
r = list(map(lambda x:int(x)-1, input().split()))
d = [[float('inf')]*n for _ in range(n)]
for _ in range(m):
  a, b, t = map(int, input().split())
  a -= 1
  b -= 1
  d[a][b] = t
  d[b][a] = t
for i in range(n):
  d[i][i] = 0

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  

d = warshall_floyd(d)
ans = float('inf')
for v in itertools.permutations(r):
  tmp = 0
  for i in range(len(v)-1):
    tmp += d[v[i]][v[i+1]]
  ans = min(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
import sys
input = sys.stdin.readline

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

T = [[float("inf")] * N for _ in range(N)]

for _ in range(M):
    A, B, C = list(map(int, input().split()))
    A -= 1
    B -= 1
    T[A][B] = T[B][A] = min(C, T[A][B])
for i in range(N):
    T[i][i] = 0

# T[j][i]: cost from j to i, O(V^3)
# T[j][i] = 0 if j == i


def warshall_floyd(T, V):
    for k in range(V):
        for j in range(V):
            for i in range(V):
                T[j][i] = min(T[j][i], T[j][k] + T[k][i])


warshall_floyd(T, N)


ans = float("inf")

for v in permutations(R):
    tmp = 0
    for i in range(len(v)-1):
        tmp += T[v[i]-1][v[i+1]-1]
    ans = min(ans, tmp)

print(ans)