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 itertools
def main():
    n,m,r=map(int,input().split())
    rx=[int(i) for i in input().split()]
    inf=100000000
    wf=[[inf]*n for i in range(n)]
    for i in range(n):
        wf[i][i]=0

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

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if wf[i][j]>wf[i][k]+wf[k][j]:
                    wf[i][j]=wf[i][k]+wf[k][j]
    cnt=0
    l=list(itertools.permutations([i for i in range(r)]))
    cnt=inf
    for i in l:
        cnt_sub=0
        for j in range(r-1):
            cnt_sub+=wf[rx[i[j]]-1][rx[i[j+1]]-1]
        cnt=min(cnt,cnt_sub)
    print(cnt)
main()

Submission status: Accepted

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

n,m,r = inpl()
x = inpl()
g = [[INF] *n for i in range(n)]
for i in range(m):
    a,b,c = inpl()
    g[a-1][b-1] = c
    g[b-1][a-1] = c
for i in range(n):
    g[i][i] = 0
for k in range(n):
    for i in range(n):
        for j in range(n):
            g[i][j] = min(g[i][k]+g[k][j], g[i][j])

res = INF
for flag in itertools.permutations(range(r)):
    cnt = 0
    for i in range(r-1):
        cnt += g[x[flag[i]]-1][x[flag[i+1]]-1]
    res = min(res, cnt)
print(res)

Submission status: Accepted

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

inf = 10**9
graph = np.ones((N, N), dtype=int)*inf
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    graph[a][b] = c
    graph[b][a] = c
fy = floyd_warshall(graph)

ans = 10 ** 9
for p in permutations(r):
    tmp = 0
    for x, y in zip(p[:-1], p[1:]):
        x -= 1
        y -= 1
        tmp += int(fy[x][y])
    ans = min(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
INFTY = 10**8
N,M,R = map(int,input().split())
A = list(map(int,input().split()))
G = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b,c = map(int,input().split())
    G[a].append((b,c))
    G[b].append((a,c))
d = {i:[INFTY for _ in range(N+1)] for i in range(N+1)}
for i in G:
    d[i][i] = 0
    for x in G[i]:
        d[i][x[0]] = x[1] 
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])
dmin = INFTY
for x in permutations(range(R),R):
    cnt = 0
    for i in range(R-1):
        cnt += d[A[x[i]]][A[x[i+1]]]
    dmin = min(dmin,cnt)
print(dmin)

Submission status: Accepted

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

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

import itertools

U=list(itertools.permutations(lists))

mini=10**100
for some in U:
  dd=0
  for j in range(r-1):
    if dislist[some[j]][some[j+1]]!=float("inf"):
      dd+=dislist[some[j]][some[j+1]]
    else:
      break
  mini=min(mini,dd)
print(mini)

Submission status: Accepted

Solution code:
n,m,R=map(int,input().split())
r=list(map(int,input().split()))
g=[[float("inf")]*n for _ in range(n)]
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

for i in range(m):
    a,b,c=map(int,input().split())
    g[a-1][b-1]=c
    g[b-1][a-1]=c
g=warshall_floyd(g)
#print(g)
from itertools import permutations
P=permutations(r)
P=list(P)
#print(P)
ans=float("inf")
for p in P:
    #print(p)
    l=0
    for i in range(1,R):
        s=p[i-1]-1
        f=p[i]-1
        l+=g[s][f]
    #print(l)
    ans=min(ans,l)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations, combinations
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
N,M,R = map(int,input().split())
r = list(map(int,input().split()))
r = [r[i]-1 for i in range(R)]
vve = [list(map(int,input().split())) for i in range(M)]
v1,v2,edge = zip(*vve)
v1 = list(v1)
v2 = list(v2)
for i in range(M):
  v1[i] -= 1
  v2[i] -= 1
csr = csr_matrix((edge,(v1,v2)),shape = (N,N))
dist = [[0 for j in range(R)] for i in range(R)]
for i,j in combinations(range(R),2):
  r1,r2=r[i],r[j]
  dist[i][j] = int(dijkstra(csr, directed = False,indices = r1)[r2])
  dist[j][i] = dist[i][j]
ans = 10**18
for x in permutations(range(R)):
  distsum = 0
  for i in range(1,R):
    distsum += dist[x[i]][x[i-1]]
  ans = min(ans,distsum)
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import permutations
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,M,R=map(int,input().split())
    r=list(map(lambda x:int(x)-1,input().split()))
    d=[[INF]*N for _ in range(N)]
    for i in range(M):
        A,B,C=map(int,input().split())
        A-=1; B-=1
        d[A][B]=C
        d[B][A]=C
    for 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 p in permutations(r):
        tmp=0
        for i in range(R-1):
            tmp+=d[p[i]][p[i+1]]
        ans=min(ans,tmp)
    print(ans)
            

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# ABC073 D - joisino's travel
import itertools
N,M,R=map(int, input().split())
r=list(map(int, input().split()))
inf=float("inf")
mat=[[inf]*N for _ in range(N)]

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

for i in range(R):
    r[i]-=1

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

for rr in itertools.permutations(r,R):
    t_sum=0
    for j in range(1,R):
        t_sum+=mat[rr[j-1]][rr[j]]
    ans=min(ans,t_sum)
print(int(ans))

Submission status: Accepted

Solution code:
N,M,C=[int(x) for x in str(input()).split()]
r=[int(x) for x in str(input()).split()]
ABC=[[0 for i in range(4)]]

dis=[[1000000000000 for i in range(N+1)]]

for i in range(N):
  dis.append([1000000000000 for i in range(N+1)])


for i in range(M):
  x=[0]+[int(x) for x in str(input()).split()]
  ABC.append(x)
  dis[x[1]][x[2]]=x[3]
  dis[x[2]][x[1]]=x[3]
  y=[0,x[2],x[1],x[3]]
  ABC.append(y)

for i in range(1,N+1):
  dis[i][i]=0


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


mi=1000000000000
def perm(a,i):
  global mi
  if i==len(a):      

    p=0
    for x in range(len(a)-1):
      p+=dis[a[x]][a[x+1]]

    mi=min(mi,p)


  else:
    for j in range(i,len(a)):
      a[i],a[j]=a[j],a[i]
      perm(a,i+1)
      a[i],a[j]=a[j],a[i]


perm(r,0)

print(mi)

Submission status: Accepted

Solution code:
# ABC073 D - joisino's travel
from scipy.sparse.csgraph import floyd_warshall
from itertools import permutations

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

inf = 10**18
dist = [[inf]*N for _ in range(N)]
for i in range(M):
    A, B, C = map(int, input().split())
    dist[A-1][B-1] = dist[B-1][A-1] = C

dist = floyd_warshall(dist)

ans = inf
for rr in permutations(r):
    cost = 0
    for i in range(R-1):
        cost += dist[rr[i]-1][rr[i+1]-1]
    ans = min(ans, cost)
print(int(ans))

Submission status: Accepted

Solution code:
# ABC073 D - joisino's travel
from scipy.sparse.csgraph import floyd_warshall
from itertools import permutations

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

inf = 10**18
dist = [[inf]*N for _ in range(N)]
for i in range(M):
    A, B, C = map(int, input().split())
    dist[A-1][B-1] = dist[B-1][A-1] = C

dist = floyd_warshall(dist)

ans = inf
for rr in permutations(r):
    cost = 0
    for i in range(R-1):
        cost += dist[rr[i]-1][rr[i+1]-1]
    if cost < ans:
        ans = cost
print(int(ans))

Submission status: Accepted

Solution code:
import itertools
import numpy as np
import sys
input = sys.stdin.buffer.readline

def main():
    N,M,R = map(int,input().split())
    r = list(map(int,input().split()))
    INF = float('INF')
    root = [[INF for _ in range(N)] for _ in range(N)]
    for i in range(N):
        root[i][i] = 0
    for i in range(M):
        A,B,C = map(int,input().split())
        root[A-1][B-1] = C
        root[B-1][A-1] = C
    
    for i in range(N):
        for j in range(N):
            for k in range(N):
                if root[j][k] > root[j][i]+root[i][k]:
                    root[j][k] = root[j][i]+root[i][k]
                
    ans = INF
    for i in itertools.permutations(r):
        L = 0
        for j in range(R-1):
            L += root[i[j]-1][i[j+1]-1]
        ans = min(ans,L)
                
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import permutations as perm

def warshall(d, n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]

n,m,r = map(int, input().split())
rr = [i-1 for i in map(int, input().split())]

inf = float('INF')
route = [[inf for j in range(n)] for i in range(n)]
for _ in range(m):
    a,b,c = map(int, input().split())
    route[a-1][b-1] = route[b-1][a-1] = c

warshall(route, n)

ans = inf
for tmp in perm(rr):
    cost = 0
    for i in range(r-1):
        cost += route[tmp[i]][tmp[i+1]]
    if cost < ans:
        ans = cost
print(int(ans))

Submission status: Accepted

Solution code:
from itertools import permutations as perm
from scipy.sparse.csgraph import dijkstra as di

def warshall(d, n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]

n,m,r = map(int, input().split())
rr = [i-1 for i in map(int, input().split())]

inf = float('INF')
route = [[0 for j in range(n)] for i in range(n)]
for _ in range(m):
    a,b,c = map(int, input().split())
    route[a-1][b-1] = route[b-1][a-1] = c

route = di(route, n)

ans = inf
for tmp in perm(rr):
    cost = 0
    for i in range(r-1):
        cost += route[tmp[i]][tmp[i+1]]
    if cost < ans:
        ans = cost
print(int(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= 10**10
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:
from itertools import permutations

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph._shortest_path import floyd_warshall


def solve():
    N, M, R = map(int, input().split())
    r = list(map(lambda x: int(x)-1, input().split()))
    dist = [[0 for _ in range(N)] for _ in range(N)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        dist[A-1][B-1] = C
        dist[B-1][A-1] = C
    fw = floyd_warshall(csr_matrix(dist))
    
    ans = 10**12
    for visit in permutations(r, R):
        m_sum = 0
        for i in range(R-1):
            m_sum += fw[visit[i]][visit[i+1]]
        ans = min(ans, m_sum)
    print(int(ans))


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
import itertools
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = 10 ** 15
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return "".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

def warshall_floyd(n,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 = m()

R = l()

di = [[Max for i in range(N)] for j in range(N)]

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

for i in range(M):
    a,b,c = m()
    a -= 1
    b -= 1
    di[a][b] = c
    di[b][a] = c


di = warshall_floyd(N,di)

Ma = Max


te = list(itertools.permutations(R))
for i in range(len(te)):
    co = 0
    RR = te[i]
    for j in range(r-1):
        co += di[RR[j]-1][RR[j+1]-1]
    Ma = min(co,Ma)
print(Ma)

Submission status: Accepted

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


def warshal_floyd(d):
    # d[i][j] := iからjへの最短距離
    global 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])
    # "今現在求まっているiからjへの最短距離"と"今現在求まっているiからkへの最短距離 + 今現在求まっているkからjへの最短距離 の和"を比較する
    return d


N, M, R = map(int, input().split())  # N個の町, M本の道, R個の町を訪れることになった
town = list(map(lambda x: int(x)-1, input().split()))
distant = [[float('inf')]*N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    distant[a][b] = c
    distant[b][a] = c
for i in range(N):
    distant[i][i] = 0
distant = floyd_warshall(distant)
# warshal_floyd(distant)
# print(distant)  # Rは最大8だから全てを試しても大丈夫
ans = 10**9
for x in itertools.permutations(town):
    x = list(x)
    now = x[0]
    tmp = 0
    for i in range(1, len(x)):
        tmp += distant[now][x[i]]
        now = x[i]
    ans = min(ans, tmp)
print(int(ans))

Submission status: Accepted

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


def warshal_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])
    # "今現在求まっているiからjへの最短距離"と"今現在求まっているiからkへの最短距離 + 今現在求まっているkからjへの最短距離 の和"を比較する
    return d


N, M, R = map(int, input().split())  # N個の町, M本の道, R個の町を訪れることになった
town = list(map(lambda x: int(x)-1, input().split()))
distant = [[float('inf')]*N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    distant[a][b] = c
    distant[b][a] = c
for i in range(N):
    distant[i][i] = 0

warshal_floyd(distant)
# print(distant)  # Rは最大8だから全てを試しても大丈夫
ans = 10**9
for x in itertools.permutations(town):
    x = list(x)
    now = x[0]
    tmp = 0
    for i in range(1, len(x)):
        tmp += distant[now][x[i]]
        now = x[i]
    ans = min(ans, tmp)
print(ans)

Submission status: Accepted

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

import sys

from scipy.sparse.csgraph import floyd_warshall

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, M, R = MAP()
A = [a-1 for a in LIST()]
G = list2d(N, N, INF)
for i in range(M):
    a, b, c = MAP()
    a -= 1; b -= 1
    G[a][b] = c
    G[b][a] = c

# 全体グラフの最短距離(ここから必要な頂点間だけ使う)
wf = floyd_warshall(G)

ans = INF
for r in range(R):
    # TSP(巡回セールスマン)
    dp = list2d(1<<R, R, INF)
    dp[1<<r][r] = 0
    for bit in range(1, (1<<R)-1):
        for i in range(R):
            if not (bit >> i & 1):
                continue
            for j in range(R):
                if bit >> j & 1:
                    continue
                a, b = A[i], A[j]
                dp[bit|1<<j][j] = min(dp[bit|1<<j][j], dp[bit][i] + int(wf[a,b]))
    ans = min(ans, min(dp[-1]))
print(ans)

Submission status: Accepted

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

I = np.array(sys.stdin.read().split(), dtype=np.int64)
n, m, R = I[:3]
r = I[3:3+R] - 1
a, b, c = I[3+R:].reshape(-1, 3).T
graph = csr_matrix((c, (a-1, b-1)), shape=(n, n))

def main():
    dist = floyd_warshall(graph, directed=False).astype(np.int64)
    
    perms = np.array(list(permutations(r)))
    res = dist[perms[:, :-1], perms[:, 1:]]
    ans = np.amin(np.sum(res, axis=1))
    return ans

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

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

I = np.array(sys.stdin.read().split(), dtype=np.int64)
n, m, R = I[:3]
r = I[3:3+R] - 1
a, b, c = I[3+R:].reshape(-1, 3).T
a -= 1; b -= 1
graph = csr_matrix((c, (a, b)), shape=(n, n))

def main():
    dist = floyd_warshall(graph, directed=False).astype(np.int64)
    *perms, = permutations(r)
    perms = np.array(perms)
    res = dist[perms[:, :-1], perms[:, 1:]]
    ans = np.amin(np.sum(res, axis=1))
    return ans

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
def main():
    from sys import stdin
    input = stdin.readline
    n, m, r = map(int, input().split())
    root = list(map(int, input().split()))
    abc = [list(map(int, input().split())) for _ in [0]*m]

    import numpy as np
    import scipy.sparse.csgraph as sp
    inf = float('inf')
    d = np.full((n, n), inf)
    for i in range(n):
        d[i][i] = 0
    for a, b, c in abc:
        d[a-1][b-1] = c
        d[b-1][a-1] = c
    # indices=xでxからの単一始点に,return_predecessors=Trueで経路が出る
    s = sp.shortest_path(d)

    from itertools import permutations

    p = list(permutations(root))

    D = 10**10
    for i in p:
        d = 0
        for j in range(len(i)-1):
            d += s[i[j]-1][i[j+1]-1]
        D = min(D, d)
    print(int(D))


main()

Submission status: Accepted

Solution code:
def main():
  import numpy as np
  import itertools
  from scipy.sparse import csr_matrix
  from scipy.sparse.csgraph import floyd_warshall
  import sys
  readline = sys.stdin.readline
  readlines = sys.stdin.readlines

  N, M, R= map(int, readline().split())
  r = list(map(int,input().split()))
  lines = readlines()
  edge = np.array([line.split() for line in lines], dtype = np.int64).T
  graph = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
  distance_mat = floyd_warshall(graph,directed = False)
  #print(distance_mat)
  ans = float("inf")
  for town in itertools.permutations(r,R):
    #print(town)
    tmp = 0
    for i in range(R-1):
      tmp += distance_mat[town[i]-1][town[i+1]-1]
    ans = min(ans,tmp)
  print(int(ans))
main()

Submission status: Accepted

Solution code:
def main():
  import numpy as np
  import itertools
  from scipy.sparse import csr_matrix
  from scipy.sparse.csgraph import dijkstra
  import sys
  readline = sys.stdin.readline
  readlines = sys.stdin.readlines

  N, M, R= map(int, readline().split())
  r = list(map(int,input().split()))
  lines = readlines()
  edge = np.array([line.split() for line in lines], dtype = np.int64).T
  #print(r)
  #print(edge)
  graph = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
  ans = float("inf")
  distance_mat = {}
  for i in r:
    distance_mat[i-1] = (dijkstra(graph, directed = False, indices = i-1))

  for town in itertools.permutations(r,R):
    #print(town)
    tmp = 0
    for i in range(R-1):
      tmp += distance_mat[town[i]-1][town[i+1]-1]
    ans = min(ans,tmp)
  print(int(ans))
main()

Submission status: Accepted

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

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

s = [[10**9]*N for i in range(N)]
t = list(map(int, input().split()))
for i in range(M):
    a, b, c = map(int, input().split())
    s[a-1][b-1] = c
    s[b-1][a-1] = c
    
s = floyd_warshall(s)
ans = float('inf')
for i in permutations(t):
    A_n = 0
    for j in range(R-1):
        A_n += s[i[j] - 1][i[j+1] - 1]
    ans = min(ans, A_n)
    
print(int(ans))

Submission status: Accepted

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

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

W = [[10**10 for _ in range(N+1)] for _ in range(N+1)]
for i in range(M):
  a, b, c = map(int, input().split())
  W[a][b], W[b][a] = c, c
#print(W)
  
for k in range(N+1):
  for i in range(N+1):
    for j in range(N+1):
      W[i][j] = min(W[i][j], W[i][k] + W[k][j])
#print(W)

answer = 10**10
for v in itertools.permutations(r, R):
  tmp = 0
  for i in range(1, R):
    tmp += W[v[i]][v[i-1]]
  answer = min(answer, tmp)
print(answer)

Submission status: Accepted

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

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

import heapq

def Dijkstra(N, v_st, v_go):
    cost = [float('inf') for i in range(N)]

    pq = []
    heapq.heappush(pq, (0, v_st))

    while pq:
        c, v_now = heapq.heappop(pq)

        if v_now == v_go:
            return c

        if cost[-v_now] < c:
            continue

        cost[-v_now] = c

        for v, c2 in adj[-v_now]:
            if cost[-v_now] + c2 < cost[-v]:
                cost[-v] = cost[-v_now] + c2
                heapq.heappush(pq, (cost[-v], v))

cost_min = [[float('inf') for i in range(R)] for j in range(R)]

for i in range(R):
    for j in range(i, R):
        cost_min[i][j] = Dijkstra(N, r[i], r[j])
        cost_min[j][i] = cost_min[i][j]

import itertools
p = list(itertools.permutations(range(R)))

ans = float('inf')
for pp in p:
    c = 0
    for i in range(R - 1):
        c += cost_min[pp[i]][pp[i + 1]]

    ans = min(ans, c)
    
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
def warshal_floyd(weights,N):
    d=weights
    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])
    return d

if __name__ == '__main__':
    N,M,R=list(map(int,input().split()))
    cities=[r-1 for r in list(map(int,input().split()))]
    weights=[[1e10 for i in range(N)] for j in range(N)]
    for i in range(M):
        a,b,c=list(map(int,input().split()))
        a-=1
        b-=1
        weights[a][b]=c
        weights[b][a]=c

    d=warshal_floyd(weights,N)
    mini_count=1e12
    for c in permutations(cities):
        count=sum(d[i][j] for i,j in zip(c,c[1:]))
        mini_count=min(mini_count,count)
    print(mini_count)

Submission status: Accepted

Solution code:
import itertools


def dijkstra(v, G):
    import heapq

    ret = [10 ** 10] * len(G)
    ret[v] = 0
    q = [(ret[i], i) for i in range(len(G))]
    heapq.heapify(q)

    while len(q):
        tmpr, u = heapq.heappop(q)
        if tmpr == ret[u]:
            for w, l in G[u]:
                if ret[w] > ret[u] + l:
                    ret[w] = ret[u] + l
                    heapq.heappush(q, (ret[w], w))
    return ret


N, M, R = map(int, input().split())
r = list(map(int, input().split()))
NE = [[] for _ in range(N)]
for _ in range(M):
    A, B, C = map(int, input().split())
    NE[A - 1].append((B - 1, C))
    NE[B - 1].append((A - 1, C))

RE = [[0] * R for _ in range(R)]
for iR in range(R):
    for jR in range(iR + 1, R):
        lR = dijkstra(r[iR] - 1, NE)[r[jR] - 1]
        RE[iR][jR] = lR
        RE[jR][iR] = lR

ans = 10 ** 10
for p in itertools.permutations(range(R)):
    ans = min(ans, sum([RE[p[i]][p[i + 1]] for i in range(R - 1)]))

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import itertools

def solve(N: int, M: int, R: int, r: "List[int]", A: "List[int]", B: "List[int]", C: "List[int]"):
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph import floyd_warshall
    matrix = [[0]*N for _ in range(N)]
    for i in range(M):
        matrix[A[i]-1][B[i]-1] = C[i]
        matrix[B[i]-1][A[i]-1] = C[i]
    
    dist_matrix = floyd_warshall(csgraph=matrix, directed=False)

    perm = list(itertools.permutations(r)) 

    answer = float('inf')
    for p in perm:
        a = 0
        for index in range(len(p)-1):
            a += dist_matrix[p[index]-1][p[index+1]-1]
        answer = min(answer,a)
    print(int(answer))
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    R = int(next(tokens))  # type: int
    r = [int(next(tokens)) for _ in range(R)]  # type: "List[int]"
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    C = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    solve(N, M, R, r, A, B, C)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import permutations

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

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

#INF = float("inf")
route_list=[[10**8]*N for _ in range(N)]

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

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

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

print(ans)

Submission status: Accepted

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

n, m, R = [int(i) for i in sys.stdin.readline().split()]
r_ls = [int(i) - 1 for i in sys.stdin.readline().split()]
INF = 10**18
graph = [[0 for i in range(n)] for j in range(n)]
for i in range(m):
    a, b, c = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a][b] = c
    graph[b][a] = c

graph_new = csgraph_from_dense(graph)
res = floyd_warshall(graph_new)
res = res[r_ls][:,r_ls]

from itertools import permutations
best = INF
for p in permutations(range(R)):
    score = 0
    for i in range(R-1):
        score += res[p[i]][p[i+1]]
    best = min(best, score)
print(int(best))

Submission status: Accepted

Solution code:
import sys
from scipy.sparse.csgraph import floyd_warshall
from itertools import permutations
read = sys.stdin.read
readline = sys.stdin.readline

N, M, R = map(int, readline().split())
r = list(map(int, readline().split()))
ABC = map(int, read().split())

INF = float('inf')
graph = [[INF] * (N + 1) for _ in range(N + 1)]

for i in range(N + 1):
    graph[i][i] = 0

for A, B, C in zip(*[iter(ABC)] * 3):
    graph[A][B] = C
    graph[B][A] = C

distance = floyd_warshall(graph)
answer = 10 ** 9
for tour in permutations(r):
    tmp = 0
    for i, j in zip(tour, tour[1:]):
        tmp += distance[i][j]

    if tmp < answer:
        answer = tmp

print(int(answer))

Submission status: Accepted

Solution code:
import sys
from scipy.sparse.csgraph import floyd_warshall
from itertools import permutations
read = sys.stdin.read
readline = sys.stdin.readline

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

INF = float('inf')
graph = [[INF] * (N + 1) for _ in range(N + 1)]
ABC = map(int, read().split())

for i in range(N + 1):
    graph[i][i] = 0

for A, B, C in zip(*[iter(ABC)] * 3):
    graph[A][B] = C
    graph[B][A] = C

distance = floyd_warshall(graph, directed=False)
answer = 10 ** 9
for tour in permutations(r):
    tmp = 0
    for i, j in zip(tour, tour[1:]):
        tmp += distance[i][j]

    if tmp < answer:
        answer = tmp

print(int(answer))