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

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, M, R = map(int, input().split())
    r = list(map(int, input().split()))
    P = permutations(r)

    dp = [[INF] * 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] = c
        dp[b][a] = c

    # ワーシャルフロイド
    for k in range(N):
        for i in range(N):
            for j in range(N):
                tmp = dp[i][k] + dp[k][j]
                if tmp < dp[i][j]:
                    dp[i][j] = tmp

    ans = INF
    for p in P:
        tmp = 0
        for i in range(R - 1):
            tmp += dp[p[i] - 1][p[i + 1] - 1]

        if tmp < ans:
            ans = tmp

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import collections

class WarshallFloyd():
    def __init__(self,N):  #Nは頂点の個数
        self.N = N
        self.d = [[float('inf')]*N for i in range(N)]  #d[i][j] = iからjへの最短距離,0-indexed
    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])
        for i in range(self.N):
            self.d[i][i] = 0
        return self.d

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

G = WarshallFloyd(N)

for u,v,c in data:
    G.add(u-1,v-1,c,directed=False)

d = G.WarshallFloyd_search()

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

ans = float('inf')

from itertools import permutations

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

print(ans)

Submission status: Accepted

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

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

g = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
    A, B, C = map(int, input().split())
    g[A][B] = C
    g[B][A] = C
g = floyd_warshall(csgraph_from_dense(g))

result = 1000000000
for p in permutations(r):
    t = 0
    for i in range(R - 1):
        t += g[p[i]][p[i + 1]]
    result = min(result, t)
print(int(result))

Submission status: Accepted

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

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

d = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
    A, B, C = map(int, input().split())
    d[A][B] = C
    d[B][A] = C
g = csgraph_from_dense(d)
g = floyd_warshall(g)

result = 1000000000
for p in permutations(r):
    t = 0
    for i in range(R - 1):
        t += g[p[i]][p[i + 1]]
    result = min(result, t)
print(int(result))

Submission status: Accepted

Solution code:
import itertools
import sys

def main():
  input = sys.stdin.readline
  n, m, r = map(int, input().split())
  R = [int(x) for x in input().split()]
  inf = pow(10, 9)+7

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

  for k in range(n):
    for i in range(n):
      for j in range(n):
        if roads[i][j] > roads[i][k]+roads[k][j]:
          roads[i][j] = roads[i][k]+roads[k][j]

  ans = inf
  for value in itertools.permutations(R):
    sub = 0
    for k in range(r-1):
      sub += roads[value[k]-1][value[k+1]-1]
    if ans > sub:
      ans = sub

  print(ans)

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
from itertools import permutations
n,m,r = map(int,input().split())
rl = list(map(int,input().split()))
d = [[10**8]*n for i in range(n)]
for i in range(m):
  a,b,c = map(int,input().split())
  d[a-1][b-1] = d[b-1][a-1] = c
for k in range(n):
  for i in range(n):
    for j in range(n):
      d[i][j] = min(d[i][j],d[i][k]+d[k][j])
m = 10**9
for i in permutations(rl):
  c = 0
  for j in range(1,r):
    c += d[i[j-1]-1][i[j]-1]
  m = min(m,c)
print(m)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections
from heapq import *

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**8
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,M,R = LI()
    r = _LI()
    root = [[] for _ in range(N)]
    for _ in range(M):
        a,b,c = LI()
        root[a-1].append((b-1,c))
        root[b-1].append((a-1,c))

    memo = [[0] * N for _ in range(N)]

    min_r = INF
    for x in itertools.permutations(r):
        it = 0
        s = x[0]
        for t in x[1:]:
            if memo[s][t]:
                it += memo[s][t]
            else:
                node = [INF] * N
                q = []
                heapify(q)
                heappush(q,(0,s))
                node[s] = 0
                while q:
                    l,u = heappop(q)
                    if l > node[u]: continue
                    for v,m in root[u]:
                        if node[v] > l + m:
                            node[v] = l + m
                            heappush(q,(l+m,v))
                memo[s][t] = node[t]
                memo[t][s] = node[t]
                it += node[t]
            s = t
        min_r = min(min_r,it)
    print(min_r)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections
from heapq import *

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**8
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,M,R = LI()
    r = _LI()
    root = [[] for _ in range(N)]
    for _ in range(M):
        a,b,c = LI()
        root[a-1].append((b-1,c))
        root[b-1].append((a-1,c))

    memo = [[0] * N for _ in range(N)]

    min_r = INF
    for x in itertools.permutations(r):
        it = 0
        s = x[0]
        for t in x[1:]:
            if memo[s][t]:
                it += memo[s][t]
            else:
                node = [INF] * N
                q = []
                heapify(q)
                heappush(q,(0,s))
                while q:
                    l,u = heappop(q)
                    if l >= node[u]: continue
                    node[u] = l
                    for v,m in root[u]:
                        if node[v] > l + m:
                            heappush(q,(l+m,v))
                memo[s][t] = node[t]
                memo[t][s] = node[t]
                it += node[t]
            s = t
        min_r = min(min_r,it)
    print(min_r)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections
from heapq import *

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**8
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,M,R = LI()
    r = _LI()
    root = [[] for _ in range(N)]
    for _ in range(M):
        a,b,c = LI()
        root[a-1].append((b-1,c))
        root[b-1].append((a-1,c))

    memo = [[0] * N for _ in range(N)]

    min_r = INF
    for x in itertools.permutations(r):
        it = 0
        s = x[0]
        for t in x[1:]:
            if memo[s][t]:
                it += memo[s][t]
            else:
                node = [INF] * N
                q = []
                heapify(q)
                heappush(q,(0,s))
                node[s] = 0
                while q:
                    l,u = heappop(q)
                    for v,m in root[u]:
                        if node[v] > l + m:
                            node[v] = l + m
                            heappush(q,(l+m,v))
                memo[s][t] = node[t]
                memo[t][s] = node[t]
                it += node[t]
            s = t
        min_r = min(min_r,it)
    print(min_r)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**8
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,M,R = LI()
    r = _LI()
    root = [[] for _ in range(N)]
    for _ in range(M):
        a,b,c = LI()
        root[a-1].append((b-1,c))
        root[b-1].append((a-1,c))

    memo = [[0] * N for _ in range(N)]

    min_r = INF
    for x in itertools.permutations(r):
        it = 0
        s = x[0]
        for t in x[1:]:
            if memo[s][t]:
                it += memo[s][t]
            else:
                node = [INF] * N
                q = collections.deque()
                q.append((s,0))
                node[s] = 0
                while q:
                    u,l = q.popleft()
                    for v,m in root[u]:
                        if node[v] > l + m:
                            node[v] = l + m
                            q.append((v,l+m))
                memo[s][t] = node[t]
                memo[t][s] = node[t]
                it += node[t]
            s = t
        min_r = min(min_r,it)
    print(min_r)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import permutations


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

INF = float('inf')

graph = [[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
    graph[a][b] = c
    graph[b][a] = 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])

min_dist = 10**10
for route in permutations(towns, r):
    dist = 0
    for i in range(r-1):
        a = route[i] - 1
        b = route[i+1] - 1
        dist += graph[a][b]
    if dist < min_dist:
        min_dist = dist

print(min_dist)

Submission status: Accepted

Solution code:
from itertools import permutations
INF = float("inf")

n, m, r = map(int, input().split())
r = list(map(lambda x: int(x)-1, input().split()))
g = [[INF] * n for _ in range(n)]
abc = [tuple(map(int, input().split())) for _ in range(m)]
for a, b, c in abc:
    a -= 1; b -= 1
    g[a][b] = c
    g[b][a] = c

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

d = warshall_floyd(g, n)
ans = INF
for route in permutations(r):
    res = 0
    for i in range(1, len(r)):
        res += d[route[i-1]][route[i]]
    ans = min(ans, res)

print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall
import numpy as np
from itertools import permutations, combinations
n,m,R = map(int,input().split())
r=list(map(int,input().split()))
for i in range(R):
    r[i]-=1
d = np.zeros((n,n)) 
# 入力
for i in range(m):
    a,b,c = map(int,input().split())
    a,b = a-1, b-1
    d[a,b] = c
dist =floyd_warshall(d,directed=0).astype(int)
ans=10**10
for v in permutations(r):
    tmp=0
    for i in range(R-1):
        tmp+=dist[v[i],v[i+1]]
    ans=min(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
INF = 10**10
n,m,R = map(int,input().split())
r=list(map(int,input().split()))
for i in range(R):
    r[i]-=1
d = [[INF]*n for i in range(n)] 
# 入力
for i in range(m):
    a,b,c = map(int,input().split())
    a,b = a-1, b-1
    d[a][b] = c
    d[b][a] = c # 無向グラフ
for i in range(n):
    d[i][i] = 0

def FW():
    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])
FW()
from itertools import permutations, combinations
ans=INF
for v in permutations(r):
    tmp=0
    for i in range(R-1):
        tmp+=d[v[i]][v[i+1]]
    ans=min(ans,tmp)
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 product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

INF = float("inf")

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,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    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

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

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

ans = INF

d = [ [INF]*n for _ in range(n) ]

# ワーシャルフロイド（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

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

d = warshall_floyd(n,d)

ls = list(permutations(R))
# print(ls)

for i in range(len(ls)):
    l = ls[i]
    cost = 0
    for j in range(r-1):
        s = l[j] - 1
        t = l[j+1] - 1
        cost += d[s][t]
    ans = min( ans, cost )
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import permutations

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m, r = map(int, input().split())
    R = list(map(int, input().split()))
    C = [[f_inf for _ in range(n)] for _ in range(n)]
    for i in range(n):
        C[i][i] = 0

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

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

    res = f_inf
    for pattern in permutations(R):
        cost = 0
        for k in range(r - 1):
            i, j = pattern[k], pattern[k + 1]
            cost += C[i - 1][j - 1]
        res = min(res, cost)

    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

#Warshall Floyd
d = [[float('inf')]*N for _ in range(N)]
for _ in range(M): #ひとまず枝があるペアは枝の長さをセット
    a,b,t = map(int, input().split())
    d[a-1][b-1] = t
    d[b-1][a-1] = t

for i in range(N):
    d[i][i] = 0 #自身への最短経路は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])

from itertools import groupby, accumulate, product, permutations, combinations
def solve(r,d):
    ans = float('inf')
    for p in permutations(r,R):
        dist = 0
        for i in range(R-1):
            dist += d[p[i]-1][p[i+1]-1]
        ans = min(ans,dist)
    return ans
print(solve(r,d))

Submission status: Accepted

Solution code:
import itertools
inf=10**8
n,m,R=map(int,input().split())
r=list(map(int,input().split()))
d=[[inf]*n for i in range(n)]
for i in range(n):
    d[i][i]=0
ans=inf
for i in range(m):
    a,b,c=map(int,input().split())
    d[a-1][b-1]=c
    d[b-1][a-1]=c
for k in range(n):
    for i in range(n):
        for j in range(n):
            d[i][j]=min(d[i][j],d[i][k]+d[k][j])
for i in itertools.permutations(r):
    preans=0
    for j in range(R-1):
        preans+=d[i[j]-1][i[j+1]-1]
    ans=min(ans,preans)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m,r = inpl()
rr = inpl()
g = [[INF]*n for _ in range(n)]
for i in range(n):
    g[i][i] = 0
for i in range(m):
    a,b,c = inpl()
    a,b = 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])
res = INF
for root in itertools.permutations(range(r)):
    cnt = 0
    for i in range(r-1):
        a,b = rr[root[i]], rr[root[i+1]]
        a,b = a-1, b-1
        cnt += g[a][b]
    res = min(res, cnt)
print(res)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
from itertools import permutations

n, m, r = map(int, readline().split())
rr = list(map(int, readline().split()))
graph = [[0] * n for _ in range(n)]
for i in range(m):
    a, b, c = map(int, readline().split())
    graph[a - 1][b - 1] = c
    graph[b - 1][a - 1] = c
cost = floyd_warshall(csr_matrix(graph))
ans = float('inf')
for bit in permutations(rr):
    cnt = 0
    for now, next in zip(bit, bit[1:]):
        cnt += cost[now - 1][next - 1]
    ans = min(cnt, ans)
print(int(ans))

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall
from itertools import permutations
from sys import stdin
nii=lambda:map(int,stdin.readline().split())

n,m,r=nii()
r=list(nii())

s=[[float('inf')]*n for i in range(n)]
for i in range(n):
  for j in range(n):
    s[i][j]=0
for i in range(m):
  a,b,c=nii()
  a-=1
  b-=1
  s[a][b]=c
  s[b][a]=c

ws=floyd_warshall(s)

ans=10**9
for i in permutations(r):
  t_ans=0
  for j in range(1,len(i)):
    t_ans+=ws[i[j-1]-1][i[j]-1]
  ans=min(ans,t_ans)
print(int(ans))

Submission status: Accepted

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

N, M, R = map(int, input().split())
R = list(map(int, input().split()))
A, B, C = np.array([input().split() for _ in range(M)], dtype=int).T
G = csr_matrix((C, (A - 1, B - 1)), shape=(N, N))
path = dijkstra(G, directed=False)
path = (path + 0.5).astype(int)

ans = 10 ** 18
for p in permutations(R):
    cnt = 0
    for x, y in zip(p[:-1], p[1:]):
        x -= 1
        y -= 1
        cnt += path[x][y]
    ans = min(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
inf = 10 ** 10
n, m, r = map(int,input().split())
R = list(map(int,input().split()))

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

G = csgraph_from_dense(edge, null_value = inf)
d = floyd_warshall(G, False)

rec = inf
for i in permutations(R, r):
    temp = 0
    #print(i)
    for j in range(r):
        if j == r - 1:continue
        temp += d[i[j] - 1][i[j + 1] - 1]
    rec = min(rec, temp)

print(int(rec))

Submission status: Accepted

Solution code:
import heapq
import itertools

def dijkstra(s):
    inf = pow(10, 10)
    dist = [inf] * (n + 1)
    dist[s] = 0
    c = [0] * (n + 1)
    p = []
    heapq.heapify(p)
    heapq.heappush(p, (dist[s], s))
    while p:
        d, u = heapq.heappop(p)
        if dist[u] < d:
            continue
        c[u] = 1
        for g in G[u]:
            if c[g[0]] == 0 and dist[u] + g[1] < dist[g[0]]:
                dist[g[0]] = dist[u] + g[1]
                heapq.heappush(p, (dist[g[0]], g[0]))
    return dist

n, m, r = map(int, input().split())
t = list(map(int, input().split()))
G = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    G[a].append([b, c])
    G[b].append([a, c])
D = [[0] * r for _ in range(r)]
for i in range(r):
    d = dijkstra(t[i])
    for j in range(r):
        D[i][j] = d[t[j]]

x = [i for i in range(r)]
ans = pow(10, 10)
for y in itertools.permutations(x):
    dist = 0
    y = list(y)
    for i in range(r - 1):
        dist += D[y[i]][y[i + 1]]
    ans = min(ans, dist)
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

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

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 i in range(N):
    dist[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

dist = warshall_floyd(dist)

min_ans = float("inf")
for perm in itertools.permutations(r):
    ans = 0
    for i in range(len(r)-1):
        ans += dist[perm[i]][perm[i+1]]
    min_ans = min(ans,min_ans)

print(min_ans)

Submission status: Accepted

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

def warshall_floyd(d):
  #d[i][j]: iからjへの最短距離
  for k in range(N+1):
    for i in range(N+1):
      for j in range(N+1):
        d[i][j]=min(d[i][j],d[i][k]+d[k][j])
  return d

# vlistに点のリスト、dist[vi][vj]に辺(vi,vj)のコストを入れて呼び出す
dist=[[float("inf")]*(N+1) for i in range(N+1)] 
for i in range(M):
  a,b,c=map(int,input().split())
  dist[a][b]=c
  dist[b][a]=c
for i in range(N+1):
  dist[i][i]=0

dist=warshall_floyd(dist)
#print(dist)

max_answer=float("inf")
for perm in itertools.permutations(rlist):
  #print(perm)
  answer=0
  for i in range(R-1):
    answer+=dist[perm[i]][perm[i+1]]
  
  max_answer=min(max_answer,answer)  
  
print(max_answer)

Submission status: Accepted

Solution code:
import sys
from itertools import permutations
 
 
def input():
    return sys.stdin.readline().strip()
 
 
def main():
    N, M, R = map(int, input().split())
 
    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
 
    r = 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  # 自身のところに行くコストは０
    D = warshall_floyd(d)
    P = list(permutations(r))
    cost = float("inf")
    for p in P:
        c = 0
        for i in range(R - 1):
            c += D[p[i] - 1][p[i + 1] - 1]
        if c < cost:
            cost = c
    print(cost)
 
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import permutations


def input():
    return sys.stdin.readline().strip()


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

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

    r = 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  # 自身のところに行くコストは０
    D = warshall_floyd(d)
    P = list(permutations(r))
    cost = float("inf")
    for p in P:
        c = 0
        for i in range(R - 1):
            c += D[p[i] - 1][p[i + 1] - 1]
        if c < cost:
            cost = c
    print(cost)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import permutations

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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

    dp = [[float("inf")] * 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] = c
        dp[b][a] = c

    for k in range(N):
        for i in range(N):
            for j in range(N):
                tmp = dp[i][k] + dp[k][j]
                if tmp < dp[i][j]:
                    dp[i][j] = tmp

    ans = float("inf")
    for p in P:
        tmp = 0
        for i in range(R - 1):
            tmp += dp[p[i]][p[i + 1]]

        if tmp < ans:
            ans = tmp

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import dijkstra
import numpy as np
from itertools import permutations
N,M,R = map(int,input().split())
r = list(map(int,input().split()))

"""
https://juppy.hatenablog.com/entry/2018/11/01/%E8%9F%BB%E6%9C%AC_python_%E5%85%A8%E7%82%B9%E5%AF%BE%E6%9C%80%E7%9F%AD%E7%B5%8C%E8%B7%AF%E6%B3%95%EF%BC%88%E3%83%AF%E3%83%BC%E3%82%B7%E3%83%A3%E3%83%AB%E3%83%95%E3%83%AD%E3%82%A4%E3%83%89%E6%B3%95
"""

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

graph = [[float("inf") for i in range(N)] for j in range(N)] 
for i in range(M):
    A,B,C = map(int,input().split())
    graph[A-1][B-1] = C
    graph[B-1][A-1] = C

dist = dijkstra(graph)

ans = 1e10
for i in permutations(r):
    flag = True
    way = list(i)
    tmp = 0
    for i in range(len(way)-1):
        if dist[way[i]-1][way[i+1]-1] < 0:
            flag = False
            break
        tmp += dist[way[i]-1][way[i+1]-1]
    if flag:
        ans = min(tmp,ans)

print(int(ans))

Submission status: Accepted

Solution code:
##from scipy.sparse.csgraph import csgraph_from_dense,floyd_warshall
##import numpy as np
from itertools import permutations
N,M,R = map(int,input().split())
r = list(map(int,input().split()))

"""
https://juppy.hatenablog.com/entry/2018/11/01/%E8%9F%BB%E6%9C%AC_python_%E5%85%A8%E7%82%B9%E5%AF%BE%E6%9C%80%E7%9F%AD%E7%B5%8C%E8%B7%AF%E6%B3%95%EF%BC%88%E3%83%AF%E3%83%BC%E3%82%B7%E3%83%A3%E3%83%AB%E3%83%95%E3%83%AD%E3%82%A4%E3%83%89%E6%B3%95
"""

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

graph = [[float("inf") for i in range(N)] for j in range(N)] 
for i in range(M):
    A,B,C = map(int,input().split())
    graph[A-1][B-1] = C
    graph[B-1][A-1] = C

dist = warshall_floyd(graph)

ans = 1e10
for i in permutations(r):
    flag = True
    way = list(i)
    tmp = 0
    for i in range(len(way)-1):
        if dist[way[i]-1][way[i+1]-1] < 0:
            flag = False
            break
        tmp += dist[way[i]-1][way[i+1]-1]
    if flag:
        ans = min(tmp,ans)

print(ans)

Submission status: Accepted

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

n,m,r = map(int,input().split())
rr = np.array(list(map(int,input().split()))) - 1

L = np.zeros((n,n),int)
for _ in range(m):
    a,b,c = map(int,input().split())
    L[a-1,b-1] = c

shortest = floyd_warshall(L, directed = False)

ans = float('inf')

for route in permutations(rr,len(rr)):
    ans = min(ans, shortest[route[:-1],route[1:]].sum())
print(int(ans))

Submission status: Accepted

Solution code:
import itertools
INF=10**30
N,M,R=map(int,input().split())
r=list(map(lambda x:int(x)-1,input().split()))

dist=[[INF]*N for i in range(N)]
for i 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 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=INF
for x in itertools.permutations(r):
    res=0
    for i in range(len(x)-1):
        res+=dist[x[i]][x[i+1]]
    ans=min(ans,res)
print(ans)