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 scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
from itertools import permutations

input = sys.stdin.readline
ans = -1

n, m, r = map(int, input().split())
r  = list(map(int, input().split()))
A, B, C = [], [], []
for i in range(m):
    a, b, c = map(int, input().split())
    A.append(a-1)
    B.append(b-1)
    C.append(c)

wf = floyd_warshall(csr_matrix((C, (A, B)), shape = (n, n)), directed=False)

for pi in permutations(r):
    cand = 0
    for r1, r2 in zip(pi, pi[1:]):
        cand += int(wf[r1-1][r2-1])
    if ans < 0 or ans > cand:
        ans = cand

print(ans)

Submission status: Accepted

Solution code:
import time
import itertools

def main():
    N,M,R = tuple([int(x) for x in input().split()])

    r = [int(x)-1 for x in input().split()]
    
    w_e = [tuple([int(x)for x in input().split()]) for _ in [0]*M]
    w_e = [(a-1,b-1,w) for (a,b,w) in w_e]


    g = Graph(list(range(N)),w_e)

    minimums = {}
    for r_i in r:
        minimums[r_i] = g.dijkstra(r_i)[0]

    bf = itertools.permutations(r)

    candidates = []
    for bf_i in bf:
        distance = 0
        for i in range(R-1):
            distance += minimums[bf_i[i]][bf_i[i+1]]
        candidates.append(distance)

    print(min(candidates))

def speedtest(func,*args):
    b = time.perf_counter()
    res = func(*args)
    e = time.perf_counter()
    elapsed = e-b
    print("{} (sec)".format(elapsed))

    return res

class Graph:
    def __init__(self,w_v,w_e):
        super().__init__()
        self.size = len(w_v)
        self.w_v = [v_i for v_i in w_v]#value of vartex
        self.w_e = [{} for _ in [0]*self.size]

        self.neighbor = [[] for _ in [0]*self.size]
        for a_i,b_i,w_i in w_e:
            self.w_e[a_i][b_i] = w_i#weight of edge
            self.w_e[b_i][a_i] = w_i#weight of edge

            self.neighbor[a_i].append(b_i)
            self.neighbor[b_i].append(a_i)

    def dijkstra(self,v_n):
        d = [-1]*self.size
        temp_d = [(10**9,i)for i in range(self.size)]
        temp_d[v_n] = (0,v_n)
        prev = [-1]*self.size

        q = set(range(self.size))
        
        while len(q)>0:
            u = min([temp_d[q_i] for q_i in q])[1]
            d[u] = temp_d[u][0]
            q.discard(u)
            for v in self.neighbor[u]:
                temp = temp_d[u][0]+self.w_e[u][v]
                if temp_d[v][0]>temp:
                    temp_d[v] = temp,v
                    prev[v] = u

        return d,prev

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools

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

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

inf = 10 ** 12

dp = [[inf]*N for i in range(N)]
for i 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):
            dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j])

l = list(range(R))
m = inf

for x in itertools.permutations(l,R):
    count = 0
    for i in range(len(l)-1):
        count += dp[r[x[i]]][r[x[i+1]]]
    m = min(count,m)

print(m)

Submission status: Accepted

Solution code:
import itertools
n, m, r = map(int, input().split())
d = [[float('inf')]*n for _ in range(n)]
rs = list(map(int, input().split()))
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 p in itertools.permutations(rs):
  tmp = 0
  for i in range(len(p)-1):
    tmp += d[p[i]-1][p[i+1]-1]
  ans = min(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
import itertools
 
n,m,r_ = map(int, input().split( ))
 
r = list(map(int, input().split( )))
for i in range(r_):
  	r[i] -= 1
d = [[10**10 for _ in range(n)] for i in range(n)]
 
for i in range(m):
    ai,bi,ci = map(int, input().split( ))
    ai-=1
    bi-=1
    d[ai][bi] = d[bi][ai] = ci

for k in range(n):
    for i in range(n):
        for j in range(n):
            d[i][j] = min(d[i][k]+d[k][j],d[i][j])
ans= 100000000000000
for l in itertools.permutations(r,r_):
    tmp = 0
    for i in range(r_-1):
        tmp += d[l[i]][l[i+1]]
    ans = min(ans, tmp)
 
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

INF = 10**10

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

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

for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    if d[a][b] > c:
        d[a][b] = c
        d[b][a] = c


def warshall(d):
    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]


# d = floyd_warshall(d)
warshall(d)


ans = INF
for p in itertools.permutations(r):
    dist = 0
    for i in range(R-1):
        dist += d[p[i]-1][p[i+1]-1]

    if ans > dist:
        ans = dist

print(int(ans))

Submission status: Accepted

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

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

INF = 10**10

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

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

for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    if d[a][b] > c:
        d[a][b] = c
        d[b][a] = c


def warshall(d):
    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]


# d = floyd_warshall(d)
warshall(d)


ans = INF
for p in itertools.permutations(r):
    dist = 0
    for i in range(R-1):
        dist += d[p[i]-1][p[i+1]-1]

    if ans > dist:
        ans = dist

print(int(ans))

Submission status: Accepted

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

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

INF = 10**10

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

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

for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    if d[a][b] > c:
        d[a][b] = c
        d[b][a] = c

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

d = floyd_warshall(d)


ans = INF
for p in itertools.permutations(r):
    dist = 0
    for i in range(R-1):
        dist += d[p[i]-1][p[i+1]-1]

    ans = min(ans, dist)

print(int(ans))

Submission status: Accepted

Solution code:
import itertools
import math

n , m , r = map(int , input().split())
rr = list(map(int,input().split()))
q = len(rr)
INF = 1145141919810364364334

p = list(itertools.permutations(rr))

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())
    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] )
            
ans = INF
for i in p:
    temp = 0
    for j in range(q-1):
        temp += d[i[j] - 1][i[j+1] - 1]
        
    ans = min(ans , temp)
    
print(ans)

Submission status: Accepted

Solution code:
# Author: cr4zjh0bp
# Created: Tue Mar 17 19:50:06 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from itertools import permutations

n, m, R = na()
r = na()
abc = nan(m)
adj = [[0 for _ in range(n)] for _ in range(n)]
for i in range(m):
    a, b, c = abc[i]
    a -= 1
    b -= 1
    adj[a][b] = c
    adj[b][a] = c

dist = [[inf for _ in range(n)] for _ in range(n)]
for i in range(n):
    for j in range(n):
        if i == j:
            dist[i][j] = 0
        elif adj[i][j]:
            dist[i][j] = adj[i][j]

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

ans = inf
for p in permutations(r):
    res = 0
    for i in range(R - 1):
        f, t = p[i] - 1, p[i + 1] - 1
        res += dist[f][t]
    ans = min(ans, res)

print(ans)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
from itertools import permutations
N,M,R=map(int,input().split())
r=list(map(lambda x: int(x)-1,input().split()))
l=tuple(permutations(range(R)))
C=[[10**8]*N for i in range(N)]
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 i in range(N):
    C[i][i]=0
for i in range(N):
    for j in range(N):
        for k in range(N):
            C[j][k] = min(C[j][k],C[j][i] + C[i][k])
a=10**8
for i in l:
    t=0
    for j in range(R-1):
        t+=C[r[i[j]]][r[i[j+1]]]
    if a>t:
        a=t
print(a)

Submission status: Accepted

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

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

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

Washall_Floyd(dist)

S = list(itertools.permutations(R, r))
cnt = f_inf
for s in S:
  tmp = 0
  for i in range(len(s)-1):
    tmp += dist[s[i]-1][s[i+1]-1]
  cnt = min(cnt, tmp)
print(cnt)

Submission status: Accepted

Solution code:
N,M,R = map(int,input().split())
rs = list(map(int,input().split()))
ABC = [tuple(map(int,input().split())) for i in range(M)]

INF = float('inf')
d = [[INF]*N for _ in range(N)]
for a,b,c in ABC:
    a,b = a-1,b-1
    d[a][b] = d[b][a] = c
for i in range(N):
    d[i][i] = 0

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

ans = INF
import itertools
for ptn in itertools.permutations(rs):
    tmp = 0
    for a,b in zip(ptn,ptn[1:]):
        a,b = a-1,b-1
        tmp += d[a][b]
    ans = min(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
import itertools

def warshall_floid(graph: list) -> list:
    """warshall-floid法: 各頂点から各頂点への最短距離を求める
    計算量: O(V^3)
    """
    n = len(graph)
    INF = 10 ** 18
    dp = [[INF] * n for i in range(n)]
    for i in range(n):
        dp[i][i] = 0
    for i in range(n):
        for j, cost in graph[i]:
            dp[i][j] = cost

    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])
    return dp

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

graph = [[] for i in range(n)]
for i in range(m):
    a, b, cost = info[i]
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))
dp = warshall_floid(graph)

ans = 10 ** 18
for ptn in itertools.permutations(r):
    tmp = 0
    for i in range(1, len(ptn)):
        tmp += dp[ptn[i] - 1][ptn[i - 1] - 1]
    ans = min(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
from scipy.sparse.csgraph import floyd_warshall
n,m,r=map(int,input().split())
R=list(map(int,input().split()))
l=[[float('inf')]*n for _ in range(n)]
for _ in range(m):
    a,b,c,=map(int,input().split())
    a-=1
    b-=1
    l[a][b]=c
    l[b][a]=c
for i in range(n):
    l[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
#F=warshall_floyd(l)
F1 = floyd_warshall(l)
ans=float('inf')
for v in permutations(R):
    temp=0
    for i in range(r-1):
        temp+=F1[v[i]-1][v[i+1]-1]
    ans=min(ans,temp)
print(int(ans))

Submission status: Accepted

Solution code:
from itertools import permutations as p
 
from scipy.sparse.csgraph import floyd_warshall
 
n, m, r = map(int, input().split())
R = list(map(int, input().split()))
l = [[0]*n for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    l[a][b] = c
    l[b][a] = c
F = floyd_warshall(l)
 
ans = float("inf")
for v in p(R):
    temp = 0
    for i in range(r-1):
        temp += F[v[i]-1][v[i+1]-1]
    ans = min(ans, temp)
print(int(ans))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def warshallFloyd():
    for k in range(N):
        for i in range(N-1):
            for j in range(i, N):
                tmp = min(E[i][j], E[i][k] + E[k][j])
                E[i][j] = E[j][i] = tmp

def dfs(c, p, d):
    if c == R:
        ans[0] = min(ans[0], d)
        return
    for i in range(R):
        if used[i]:
            continue
        used[i] = True
        if p == -1:
            dfs(c+1, i, 0)
        else:
            dfs(c+1, i, d + E[S[p]-1][S[i]-1])
        used[i] = False

N, M, R = map(int, input().split())
S = list(map(int, input().split()))
E = [[float('inf')] * N for _ in range(N)]
for i in range(N):
    E[i][i] = 0
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    E[a][b] = E[b][a] = c
warshallFloyd()
ans = [float('inf')]
used = [False] * R
dfs(0, -1, 0)
print(*ans)

Submission status: Accepted

Solution code:
from itertools import permutations

class Graph():  #non-directed
    def __init__(self, n, edge):
        self.n = n
        self.graph = [[] for _ in range(n)]
        for e in edge:
            self.graph[e[0] - 1].append((e[1] - 1, e[2]))
            self.graph[e[1] - 1].append((e[0] - 1, e[2]))

    def warshall_floyd(self, INF=10**18):
        dist = [[INF for j in range(self.n)] for i in range(self.n)]
        for i in range(self.n):
            dist[i][i] = 0
        for i in range(self.n):
            for j, cost in self.graph[i]:
                dist[i][j] = cost
        for k in range(self.n):
            for i in range(self.n):
                for j in range(self.n):
                    if dist[i][k] != INF and dist[k][j] != INF:
                        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
        return dist

N, M, R = map(int, input().split())
T = list(map(int, input().split()))
E = [tuple(map(int, input().split())) for _ in range(M)]

G = Graph(N, E)
D = G.warshall_floyd()

ans = 10**18

for p in permutations(range(R)):
    dist = 0
    for i in range(R - 1):
        t1, t2 = T[p[i]], T[p[i + 1]]
        dist += D[t1 - 1][t2 - 1]
    ans = min(ans, dist)

print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc073/tasks/abc073_d

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))



# default import
from itertools import product, permutations, combinations

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

# ダイクストラか？
# 全点間の最小距離を取得
# rについてpermutationして。その通りに訪れたときの距離をシミュレーション
# 最小値を選ぶ

N, M, r = read_ints()
R = [x - 1 for x in read_ints()]
adj_mat = [[0] * N for _ in range(N)]
for _ in range(M):
    a, b, c = read_ints()
    a -= 1
    b -= 1
    adj_mat[a][b] = c
    adj_mat[b][a] = c

# print(csr_matrix(adj_mat, dtype='int'))
D = dijkstra(csr_matrix(adj_mat, dtype='int'), directed=False)
# print(D)
# 全探索パート
ans = 2 ** 31


def get_kyori(p):
    ret = 0
    for ps, pt in zip(p[:-1], p[1:]):
        ret += D[ps, pt]
    return ret


for p in permutations(R):
    ans = min(ans, get_kyori(p))
print(int(ans))

Submission status: Accepted

Solution code:
from itertools import permutations as perm

n, m, r = map(int, input().split())
r = list(map(lambda x: int(x) - 1, input().split()))
d = [[10 ** 10] * n for _ in range(n)]
for i in range(m):
    abc = tuple(map(int, input().split()))
    a = abc[0] - 1
    b = abc[1] - 1
    c = abc[2]
    d[a][b] = c
    d[b][a] = c
for k in range(n):
    for i in range(n):
        for j in range(n):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])
            d[j][i] = d[i][j]

ans = 10 ** 10
for arr in perm(r):
    rep = 0
    for i in range(len(arr) - 1):
        rep += d[arr[i]][arr[i + 1]]
    ans = min(ans, rep)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations as perm

n, m, r = map(int, input().split())
r = list(map(lambda x: int(x) - 1, input().split()))
d = [[10 ** 9] * n for _ in range(n)]
for i in range(m):
    abc = tuple(map(int, input().split()))
    a = abc[0] - 1
    b = abc[1] - 1
    c = abc[2]
    d[a][b] = c
    d[b][a] = c
for k in range(n):
    for i in range(n):
        for j in range(n):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])
            d[j][i] = d[i][j]

ans = 10 ** 9
for arr in perm(r):
    rep = 0
    for i in range(len(arr) - 1):
        rep += d[arr[i]][arr[i + 1]]
    ans = min(ans, rep)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
N, M, R, *L = map(int, open(0).read().split())
city = L[:R]
inf = L[R:]
dist = [[10**10]*N for i in range(N)]
for x,y,c in zip(*[iter(inf)]*3):
  dist[x-1][y-1] = c
  dist[y-1][x-1] = c
for i in range(N):
  dist[i][i] = 0

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

ans = 10**10
for m in permutations(city):
  n = 0
  for i in range(R-1):
    n += dist[m[i]-1][m[i+1]-1]
  ans = min(ans,n)
print(ans)

Submission status: Accepted

Solution code:
import itertools
#TLE

N,M,R = map(int,input().split())
rs = list(map(lambda x:int(x)-1,input().split()))
cost=[[10**9]*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(i):  # j<i
            cost[i][j] =  min(cost[i][j],cost[i][k] + cost[k][j])
            cost[j][i] = cost[i][j]

ans = 10**9
for roads in itertools.permutations(rs):
    co = 0
    p = roads[0]
    for r in roads[1:]:
        co += cost[p][r]
        p = r
    ans = min(ans,co)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
n,m,r=map(int,input().split())
rlis=list(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
d=[[10**10]*n for _ in range(n)]
for _ in range(m):
  a,b,c=map(int,input().split())
  a-=1
  b-=1
  d[a][b]=c
  d[b][a]=c
for i in range(n):
  d[i][i]=0
dist=warshall_floyd(d)
rlisp=list(permutations(rlis,r))
ans=10**10
for i in rlisp:
  cnt=0
  for j in range(r-1):
    cnt+=dist[i[j]-1][i[j+1]-1]
  ans=min(ans,cnt)
print(ans)

Submission status: Accepted

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

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

r = [e - 1 for e in r]

g = [[0] * N for _ in range(N)]
for a, b, c in abc:
	a -= 1
	b -= 1
	g[a][b] = c
	g[b][a] = c

dist = floyd_warshall(csr_matrix(g))

ans = float("inf")
for pat in permutations(r, len(r)):
	sm = 0
	for e1, e2 in zip(pat, pat[1:]):
		sm += dist[e1][e2]

	ans = min(ans, sm)

ans = int(ans)
print(ans)

Submission status: Accepted

Solution code:
from subprocess import call
call(('pypy3','-c',"""N,M,R=map(int,input().split())
r=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 a,b,c in A:
  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])
      
import itertools 
ans=1000000000
for i in itertools.permutations(range(R),R):
  D=0
  for j in range(R-1):
    D+=d[r[i[j]]-1][r[i[j+1]]-1]
  ans=min(D,ans)
print(ans)
"""))

Submission status: Accepted

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

dist = [[float('inf') for _ in range(N+1)] for _ in range(N+1)]

for i in range(N+1):
    dist[i][i] = 0
for a, b, c in ABC:
    dist[a][b] = c
    dist[b][a] = c

# ワーシャルフロイドで各頂点ごとの最短距離を求める
for k in range(N+1):
    for i in range(N+1):
        for j in range(N+1):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

from itertools import permutations as per

ans = float('inf')
for k in per(r, R):
    score = 0
    for i in range(R-1):
        score += dist[k[i]][k[i+1]]
    ans = min(ans, score)

print(ans)

Submission status: Accepted

Solution code:
import itertools
import sys

N, M, R = map(int, input().split())
r = [int(i) for i in input().split()]
r.sort()
a = [[sys.maxsize for j in range(N)] for i in range(N)]
for i in range(M):
	A, B, C = map(int, input().split())
	a[A - 1][B - 1] = C
	a[B - 1][A - 1] = C
for i in range(N):
	a[i][i] = 0
for i in range(N):
	for j in range(N):
		if a[j][i] == sys.maxsize:
			continue
		for k in range(N):
			if a[i][k] == sys.maxsize:
				continue
			a[j][k] = min(a[i][k] + a[j][i], a[j][k])
ans = sys.maxsize
for i in itertools.permutations(r):
	b = 0
	j = 1
	while j < R:
		b += a[i[j - 1] - 1][i[j] - 1]
		j += 1
	ans = min(b, ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, csgraph_from_dense
import itertools

input = sys.stdin.readline


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

    EDGE = [[10 ** 9] * N for j in range(N)]

    for a, b, c in ABC:
        EDGE[a - 1][b - 1] = c
        EDGE[b - 1][a - 1] = c

    G = csgraph_from_dense(EDGE, null_value=10 ** 9)

    d = floyd_warshall(G)

    ans = float("inf")
    for a in itertools.permutations(r):
        tmp = 0
        c = a[0]
        for n in a:
            tmp += int(d[c][n])
            c = n
        ans = min(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import permutations


def floyd_warshall(dist):
    v = len(dist)
    for k in range(v):
        for i in range(v):
            for j in range(v):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])


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(N):
    dist[i][i] = 0
for _ in range(M):
    A, B, C = map(int, input().split())
    A -= 1
    B -= 1
    dist[A][B] = dist[B][A] = C
floyd_warshall(dist)
ans = float('inf')
for perm in permutations(r):
    d = 0
    for i in range(R-1):
        d += dist[perm[i]][perm[i+1]]
    ans = min(ans, d)
print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
from itertools import permutations
n,m,r,*L=map(int,open(0).read().split())
f=floyd_warshall(csr_matrix((L[r+2::3],(L[r::3],L[r+1::3])),(n+1,n+1)),0)
print(int(min(sum(f[s,t]for s,t in zip(o,o[1:]))for o in permutations(L[:r]))))

Submission status: Accepted

Solution code:
from itertools import permutations
class WarshallFloyd:
    def __init__(self,n):
        self.n = n
        self.inf = float('inf')
        self.d = [[self.inf for _ in range(n)] for _ in range(n)]
        for i in range(self.n):
            self.d[i][i] = 0
    def register(self,v1,v2,l,multiple=True):
        self.d[v1][v2] = l
        if multiple:
            self.d[v2][v1] = l
    def solve(self):
        for i in range(self.n):
            for j in range(self.n):
                for k in range(self.n):
                    self.d[j][k] = min(self.d[j][k],self.d[j][i]+self.d[i][k])
        return self.d
N,M,R = map(int,input().split())
v = list(map(int,input().split()))
Edges = [[] for i in range(N)]
W = WarshallFloyd(N)
for i in range(M):
    a,b,c = map(int,input().split())
    a,b = a-1,b-1
    W.register(a,b,c)
D = W.solve()
a = permutations(v,R)
ans = 100000000000
for e in a:
    value = 0
    for e1,e2 in zip(e[:-1],e[1:]):
        value += D[e1-1][e2-1]
    ans = min(ans,value)
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import permutations
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

N, M, R = [int(x) for x in input().strip().split()]
r = [int(x) for x in input().strip().split()]
G = [[float('inf')] * N for _ in range(N)]
for m in range(M):
    a, b, c = [int(x) for x in input().strip().split()]
    G[a-1][b-1] = c
    G[b-1][a-1] = c

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

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 = float('inf')
for rr in permutations(r):
    ans_ = 0
    for i in range(len(rr)-1):
        ans_ += G[rr[i]-1][rr[i+1]-1]
    ans = min(ans, ans_)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

import itertools

def main():
    mod=10**9+7
    N,M,R=MI()
    r=LI()
    inf=10**10
    d=[[inf]*N for _ in range(N)]
    for _ in range(M):
        a,b,c=MI()
        a-=1
        b-=1
        d[a][b]=c
        d[b][a]=c
    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=inf
    for ite in itertools.permutations(range(R), R):
        temp=0
        for i in range(R-1):
            a=r[ite[i]]-1
            b=r[ite[i+1]]-1
            temp+=d[a][b]
        ans=min(ans,temp)
        
    print(ans)
            
        
        
    
    
    

main()

Submission status: Accepted

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

N, M, R = [int(x) for x in input().split()]
r = [int(x) - 1 for x in input().split()]
d = [[float("inf")] * N for _ in range(N)]
for i in range(N):
    d[i][i] = 0
for _ in range(M):
    A, B, C = [int(x) for x in input().split()]
    d[A - 1][B - 1] = C
    d[B - 1][A - 1] = C
def warshall_floyd(d):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d
d = warshall_floyd(d)

from itertools import permutations
ans = 10 ** 10
route = list(permutations(r))
for i in route:
    cnt = 0
    for j in range(R - 1):
        cnt += d[i[j]][i[j + 1]]
    ans = min(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

#保存
import heapq
import sys
import itertools
 
sys.setrecursionlimit(10**7)

def bfs(cost,node):
    root[node]=min(root[node],cost)
    for next_c,next_n in way[node]:
        if root[next_n]==10**9:
            heapq.heappush(q,[cost+next_c,next_n])
    return
    
N,M,R=map(int,input().split())
r=list(map(int,input().split()))

way=[[] for i in range(N)]

for _ in range(M):
    A,B,C=map(int,input().split())
    way[A-1].append([C,B-1])
    way[B-1].append([C,A-1])

made=[]

#print(q)
for start in r:
    root=[10**9]*N
    q=[[0,start-1]]
    heapq.heapify(q)#costとnode
    while q:
        temp=heapq.heappop(q)
        #print(temp)
        if root[temp[1]]==10**9:
            bfs(temp[0],temp[1])
    made.append(root)
#print(made)

ans=10**9
for order in itertools.permutations([i for i in range(len(r))]):
    #print(order)
    temp=0
    for i in range(len(order)-1):
        fro=r[order[i]]
        aft=r[order[i+1]]
        #print("YES")
        #print(order[i]-1,order[i+1]-1)
        #print(root[order[i]-1][0])
        temp+=abs(made[order[i]][aft-1]-made[order[i]][fro-1])
    ans=min(ans,temp)
print(ans)

Submission status: Accepted

Solution code:
#17:03
n,m,r = map(int,input().split())
must = list(map(lambda x: int(x)-1,input().split()))
inf = 10**18
wf = [[inf for _ in range(n)] for _ in range(n)]
for i in range(n):
  wf[i][i] = 0
for _ in range(m):
  a,b,l = map(int,input().split())
  a -= 1
  b -= 1
  wf[a][b] = l
  wf[b][a] = l
for k in range(n):
  for i in range(n):
    for j in range(n):
      wf[i][j] = min(wf[i][j],wf[i][k]+wf[k][j])
#print(wf)
can = []
import itertools
for perm in itertools.permutations(range(r)):
  ans = 0
  for i in range(r-1):
    ans += wf[must[perm[i]]][must[perm[i+1]]]
  can.append(ans)
#print(can)
print(min(can))

Submission status: Accepted

Solution code:
from itertools import permutations as p

from scipy.sparse.csgraph import floyd_warshall

n, m, r = map(int, input().split())
R = list(map(int, input().split()))
l = [[0]*n for _ in range(n)]
for _ in range(m):
  a, b, c = map(int, input().split())
  a -= 1
  b -= 1
  l[a][b] = c
  l[b][a] = c
F = floyd_warshall(l)

ans = float("inf")
for v in p(R):
  temp = 0
  for i in range(r-1):
    temp += F[v[i]-1][v[i+1]-1]
  ans = min(ans, temp)
  
print(int(ans))