Problem:


Score : 400 points

Problem Statement

There are N towns in the State of Atcoder, connected by M bidirectional roads.

The i-th road connects Town A_i and B_i and has a length of C_i.

Joisino is visiting R towns in the state, r_1,r_2,..,r_R (not necessarily in this order).

She will fly to the first town she visits, and fly back from the last town she visits, but for the rest of the trip she will have to travel by road.

If she visits the towns in the order that minimizes the distance traveled by road, what will that distance be?

Constraints

2≤N≤200

1≤M≤N×(N-1)/2

2≤R≤min(8,N) (min(8,N) is the smaller of 8 and N.)

r_i≠r_j (i≠j)

1≤A_i,B_i≤N, A_i≠B_i

(A_i,B_i)≠(A_j,B_j),(A_i,B_i)≠(B_j,A_j) (i≠j)

1≤C_i≤100000

Every town can be reached from every town by road.

All input values are integers.

Input

Input is given from Standard Input in the following format:

N M R
r_1 ... r_R
A_1 B_1 C_1
:
A_M B_M C_M

Output

Print the distance traveled by road if Joisino visits the towns in the order that minimizes it.

Sample Input 1

3 3 3
1 2 3
1 2 1
2 3 1
3 1 4

Sample Output 1

2

For example, if she visits the towns in the order of 1, 2, 3, the distance traveled will be 2, which is the minimum possible.

Sample Input 2

3 3 2
1 3
2 3 2
1 3 6
1 2 2

Sample Output 2

4

The shortest distance between Towns 1 and 3 is 4. Thus, whether she visits Town 1 or 3 first, the distance traveled will be 4.

Sample Input 3

4 6 3
2 3 4
1 2 4
2 3 3
4 3 1
1 4 1
4 2 2
3 1 6

Sample Output 3

3



Sample input:
3 3 3
1 2 3
1 2 1
2 3 1
3 1 4


Sample output:
2

Submission status: Accepted

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

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
graph = [[INF]*N for _ 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_matrix = floyd_warshall(graph)

ans = INF
for root in permutations(r):
    cnt = 0
    for j in range(R-1):
        cnt += dist_matrix[root[j]-1][root[j+1]-1]
    ans = min(ans, cnt)
print(int(ans))

Submission status: Accepted

Solution code:
n,m,z = map(int, input().split())
r = list(map(int, input().split()))
wf=[[10**10 for i in range(n)] for j in range(n)]
for i in range(m):
    a,b,c = list(map(int,input().split()))
    wf[a-1][b-1] = c
    wf[b-1][a-1] = c

for i in range(n):
    wf[i][i]=0

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

from itertools import *
ans=10**10
for vils in list(permutations(r)):
    cnt=0
    for i in range(z-1):
        cnt+=wf[vils[i]-1][vils[i+1]-1]
    if ans>cnt:
        ans=cnt
print(ans)

Submission status: Accepted

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

n, m, r = map(int,input().split()) #n:頂点数　m:辺の数 r:訪れる町の数
R = list(map(int,input().split()))

d = np.array([[float("inf") for i in range(n)] for i in range(n)])
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(m):
    x, y, z = map(int,input().split())
    d[x-1][y-1] = z
    d[y-1][x-1] = z
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
wa = floyd_warshall(d)

# 訪れる町の順番を順列で用意
from itertools import permutations
ptn = permutations(R)

ans = 10**19
for p in ptn:
  cost = 0
  roots = [(j-1, i-1) for i, j in zip(p, p[1:])]
  for i, j in roots:
    cost += wa[i][j]
  ans = min(ans, cost)
  
print(int(ans))

Submission status: Accepted

Solution code:
N,M,R=map(int, input().split())
r=map(lambda x:int(x)-1, input().split())
dp=[[10**9]*N for _ in range(N)]
for _ in range(M):
    A,B,C=map(int, input().split())
    A-=1
    B-=1
    dp[A][B]=C
    dp[B][A]=C
for z in range(N):
    for x in range(N):
        for y in range(N):
            dp[x][y]=min(dp[x][y], dp[x][z]+dp[z][y])

import itertools
ans=10**9
for rp in itertools.permutations(r):
    t=0
    for i in range(R-1):
        t+=dp[rp[i]][rp[i+1]]
    ans=min(ans,t)
print(ans)

Submission status: Accepted

Solution code:
N,M,R=map(int, input().split())
r=list(map(lambda x:int(x)-1, input().split()))
dp=[[10**9]*N for _ in range(N)]
for _ in range(M):
    A,B,C=map(int, input().split())
    A-=1
    B-=1
    dp[A][B]=C
    dp[B][A]=C
for z in range(N):
    for x in range(N):
        for y in range(N):
            dp[x][y]=min(dp[x][y], dp[x][z]+dp[z][y])

import itertools
ans=10**9
for p in itertools.permutations(range(R)):
    t=0
    rp=[r[i] for i in p]
    for i in range(R-1):
        t+=dp[rp[i]][rp[i+1]]
    ans=min(ans,t)
print(ans)

Submission status: Accepted

Solution code:
N,M,R=map(int, input().split())
r=list(map(int, input().split()))
dp=[[10**9]*N for _ in range(N)]
for _ in range(M):
    A,B,C=map(int, input().split())
    A-=1
    B-=1
    dp[A][B]=C
    dp[B][A]=C
for z in range(N):
    for x in range(N):
        for y in range(N):
            dp[x][y]=min(dp[x][y], dp[x][z]+dp[z][y])

import itertools
ans=10**9
for p in itertools.permutations(range(R)):
    t=0
    rp=[r[i] for i in p]
    for i in range(R-1):
        t+=dp[rp[i]-1][rp[i+1]-1]
    ans=min(ans,t)
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def MI(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

from itertools import permutations

N,M,R = LI()
r = LI()
A,B,C = MI(M,3)

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

E = [[float('inf')]*N for _ in range(N)]
for i in range(N):
    E[i][i] = 0         #自分との距離は0にしておく
for i in range(M):
    E[A[i]-1][B[i]-1] = C[i]
    E[B[i]-1][A[i]-1] = C[i]     #無向枝の場合両方格納

E2 = WF(E,N) #全ての点の組み合わせの距離を2次元配列で返す

X = list(permutations(r))
ans = float('inf')

for x in X:
    now = 0
    for i in range(1,len(x)):
        now += E2[x[i-1]-1][x[i]-1]
    if now < ans:
        ans = now

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


sys.setrecursionlimit(1000000)
MOD = int(1e09) + 7
INF = int(1e15)


def main():
    # sys.stdin = open("Sample.txt")
    N, M, R = Scanner.map_int()
    r = Scanner.map_int()
    for i in range(R):
        r[i] -= 1
    G = [[] for _ in range(N)]
    d = [[INF for _ in range(N)]for _ in range(N)]
    for i in range(N):
        d[i][i] = 0
    for i in range(M):
        a, b, c = Scanner.map_int()
        a -= 1
        b -= 1
        G[a].append((b, c))
        G[b].append((a, 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])
    r.sort()
    ans = INF
    for v in itertools.permutations(r):
        now = 0
        for i in range(len(v)-1):
            now += d[v[i]][v[i+1]]
        ans = min(ans, now)
    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import permutations
N, M, R = map(int, input().split())
r = [int(c)-1 for c in input().split()]
cost = [[float('inf')]*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
def warshall_floyd(d,n):
    #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
dist = warshall_floyd(cost,N)
ls = list(permutations(r))
ans = -1
for l in ls:
  m = 0
  p = l[0]
  flag = False
  for q in l[1:]:
    m += dist[p][q]
    p = q
  if ans==-1 or ans>m:
    ans = m
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n,m,r = map(int,readline().split())

lst1 = [[float("inf")]*n for _ in range(n)]

lst2 = list(map(int,readline().split()))
for i in range(len(lst2)):
    lst2[i] -= 1

for i in range(m):
    x,y,w = map(int,readline().split())
    lst1[x-1][y-1] = w
    lst1[y-1][x-1] = w

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

lst1 = warshall_floyd(lst1)

ans = 10**10
for i in list(itertools.permutations(lst2)):
    res = 0
    before = i[0]
    for j in i[1:]:
        res += lst1[before][j]
        before = j

    ans = min(res,ans)
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())
vis=list(map(int,input().split()))
INF=10**18
path=[[INF]*n for i in range(n)]
for i in range(m):
  a,b,c=map(int,input().split())
  path[a-1][b-1]=c
  path[b-1][a-1]=c
path=floyd_warshall(path)
ans=10**18
for root in permutations(vis):
  cnt=0
  for j in range(1,r):
    cnt+=path[root[j-1]-1][root[j]-1]
  ans=min(ans,cnt)
print(int(ans))

Submission status: Accepted

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

INF = 10 ** 18
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
dp = [[INF for _ in range(N)] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j:
            dp[i][j] = 0

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

wf = floyd_warshall(dp)
ans = INF
for i in permutations(r):
    tmp = 0
    for j in range(1, len(i)):
        tmp += wf[i[j - 1] - 1][i[j] - 1]
    ans = min(ans, tmp)

print(int(ans))

Submission status: Accepted

Solution code:
from itertools import permutations

N, M, R = map(int, input().split())
r = list(map(lambda x: int(x) - 1, input().split()))
d = [[float("inf") for _ in range(N)] for _ in range(N)] 
for i in range(M):
    x, y, z = map(int, input().split())
    d[x-1][y-1] = min(d[x-1][y-1], z)
    d[y-1][x-1] = min(d[x-1][y-1], z)
for i in range(N):
    d[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

short_dist = warshall_floyd(d)

ans = float('inf')
for ptn in permutations(r):
    dist = 0
    for x, y in zip(ptn, ptn[1:]):
        dist += short_dist[x][y]
    ans = min(ans, dist)
        
print(ans)

Submission status: Accepted

Solution code:
from collections import *
from itertools import *
import copy
from heapq import *


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

data=[[] for i in range(N+1)]
nagasa={}
for a,b,c in ABC:
    data[a].append(b)
    data[b].append(a)
    A,B=min(a,b),max(a,b)
    nagasa.update({str(A)+" "+str(B):c})
mokutekiti=[[100000*200+1 for i in range(R)] for m in range(R)]
for r1i in range(R-1):
    for r2i in range(r1i+1,R):
        r1=Rlst[r1i]
        r2=Rlst[r2i]
        visited=set()
        stack=[0]
        heapify(stack)
        dic={0:[r1]}
        kyori=set([0])
        while stack:
            m=heappop(stack)
            #if not m in visited:
            #visited.add(m)
            a=dic[m].pop()
            if a==r2:
                break
            if not a in visited:
                visited.add(a)
                for b in data[a]:
                    if not b in visited or b==r2:
                        A,B=min(a,b),max(a,b)
                        tempm=m+nagasa[str(A)+" "+str(B)]
                        if b==r2:
                            if mokutekiti[r1i][r2i]>tempm:
                                mokutekiti[r1i][r2i]=tempm
                                mokutekiti[r2i][r1i]=tempm
                            heappush(stack,tempm)
                            if tempm in kyori:
                                dic[tempm].append(b)
                            else:
                                kyori.add(tempm)
                                dic.update({tempm:[b]})

                        else:
                            heappush(stack,tempm)
                            if tempm in dic:
                                dic[tempm].append(b)
                            else:
                                dic.update({tempm:[b]})



value=[]
for lst in permutations([i for i in range(R)],R):
    nagasa=0
    for i in range(R-1):
        nagasa+=mokutekiti[lst[i]][lst[i+1]]
    value.append(nagasa)
print(min(value))

Submission status: Accepted

Solution code:
N,M,R = map(int,input().split())
r = list(map(int,input().split()))
r.sort()
G = [[10**9 for i in range(N+1)] for j in range(N+1)]
for i in range(M):
    a,b,c = map(int,input().split())
    G[a][b] = min(G[a][b],c)
    G[b][a] = G[a][b]
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
warshall_floyd(G)
import itertools
ans = 10**9
for v in itertools.permutations(r):
    v = list(v)
    a = 0
    s = v.pop(0)
    for i in range(R-1):
        t = v[i]
        a += G[s][t]
        s = t
    ans = min(a,ans)
print(ans)

Submission status: Accepted

Solution code:
import itertools
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
m = [[10**10]*N for i in range(N)]

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

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

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

ans = 10**10
for l in itertools.permutations(r):
  cost = 0
  for i in range(1, R):
    cost += m[l[i-1]-1][l[i]-1]
  ans = min(ans, cost)

print(ans)

Submission status: Accepted

Solution code:
import heapq
from itertools import permutations
def dijkstra(n, tc_edges, s):
    
    min_dist = [float('inf')] * n
    min_dist[s] = 0
    next_v = []
    heapq.heappush(next_v, (0, s))
    
    while True:
        if len(next_v) == 0: break
        d, v = heapq.heappop(next_v)
        
        for u, d in tc_edges[v]:
            if min_dist[u] > min_dist[v] + d:
                min_dist[u] = min_dist[v] + d
                heapq.heappush(next_v, (min_dist[u], u))
                
    return min_dist
    
n, m, r = map(int, input().split())
r = list(map(int, input().split()))
edge = [[] for _ in range(n)]

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

dist = [dijkstra(n, edge, i) for i in range(n)]

ans = float('inf')
for pr in permutations(r):
    temp = 0
    for i in range(len(r)-1):
        temp += dist[pr[i]-1][pr[i+1]-1]
        if temp >= ans: break
    
    ans = min(ans, temp)
    
print(ans)

Submission status: Accepted

Solution code:
from collections import *
from itertools import *
import copy
from heapq import *


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

data=[[] for i in range(N+1)]
nagasa={}
for a,b,c in ABC:
    data[a].append(b)
    data[b].append(a)
    A,B=min(a,b),max(a,b)
    nagasa.update({str(A)+" "+str(B):c})
mokutekiti=[[100000*200+1 for i in range(R)] for m in range(R)]
for r1i in range(R-1):
    for r2i in range(r1i+1,R):
        r1=Rlst[r1i]
        r2=Rlst[r2i]
        visited=set()
        stack=[0]
        heapify(stack)
        dic={0:[r1]}
        while stack:
            m=heappop(stack)
            #if not m in visited:
            #visited.add(m)
            a=dic[m].pop()
            if a==r2:
                break
            if not a in visited:
                visited.add(a)
                for b in data[a]:
                    if not b in visited or b==r2:
                        A,B=min(a,b),max(a,b)
                        tempm=m+nagasa[str(A)+" "+str(B)]
                        if b==r2:
                            if mokutekiti[r1i][r2i]>tempm:
                                mokutekiti[r1i][r2i]=tempm
                                mokutekiti[r2i][r1i]=tempm
                            heappush(stack,tempm)
                            if tempm in dic:
                                dic[tempm].append(b)
                            else:
                                dic.update({tempm:[b]})

                        else:
                            heappush(stack,tempm)
                            if tempm in dic:
                                dic[tempm].append(b)
                            else:
                                dic.update({tempm:[b]})



value=[]
for lst in permutations([i for i in range(R)],R):
    nagasa=0
    for i in range(R-1):
        nagasa+=mokutekiti[lst[i]][lst[i+1]]
    value.append(nagasa)
print(min(value))

Submission status: Accepted

Solution code:
from collections import *
from itertools import *
import copy
from heapq import *


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

data=[[100000*200+1 for i in range(N)] for i in range(N)]
for a,b,c in ABC:
    data[a-1][b-1]=c
    data[b-1][a-1]=c

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



value=[]
for lst in permutations([i for i in range(R)],R):
    nagasa=0
    for i in range(R-1):
        nagasa+=data[Rlst[lst[i]]-1][Rlst[lst[i+1]]-1]
    value.append(nagasa)
print(min(value))

Submission status: Accepted

Solution code:
from collections import *
from itertools import *
import copy
from heapq import *


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

data=[[] for i in range(N+1)]
nagasa={}
for a,b,c in ABC:
    data[a].append(b)
    data[b].append(a)
    A,B=min(a,b),max(a,b)
    nagasa.update({str(A)+" "+str(B):c})
mokutekiti=[[100000*200+1 for i in range(R)] for m in range(R)]
for r1i in range(R-1):
    for r2i in range(r1i+1,R):
        r1=Rlst[r1i]
        r2=Rlst[r2i]
        visited=set()
        stack=[0]
        heapify(stack)
        dic={0:[r1]}
        while stack:
            m=heappop(stack)
            #if not m in visited:
            #visited.add(m)
            a=dic[m].pop()
            if not a in visited:
                visited.add(a)
                for b in data[a]:
                    if not b in visited or b==r2:
                        A,B=min(a,b),max(a,b)
                        tempm=m+nagasa[str(A)+" "+str(B)]
                        if b==r2:
                            if mokutekiti[r1i][r2i]>tempm:
                                mokutekiti[r1i][r2i]=tempm
                                mokutekiti[r2i][r1i]=tempm
                        else:
                            heappush(stack,tempm)
                            if tempm in dic:
                                dic[tempm].append(b)
                            else:
                                dic.update({tempm:[b]})



value=[]
for lst in permutations([i for i in range(R)],R):
    nagasa=0
    for i in range(R-1):
        nagasa+=mokutekiti[lst[i]][lst[i+1]]
    value.append(nagasa)
print(min(value))

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense,dijkstra,floyd_warshall
N,M,R = map(int,input().split())

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

List = [[10**6]*(N) for i in range(N)]
for i in range(M):
  a,b,c = map(int,input().split())
  
  if List[a-1][b-1] > c:
    List[a-1][b-1] = c
    List[b-1][a-1] = c
G = csgraph_from_dense(List, null_value=10**6)
d = floyd_warshall(G)

import itertools
a = list(itertools.permutations(machi))
arr = []
for i in a:
  ans = 0
  for j in range(R):
    if j != R-1 :
      ans += d[i[j]-1][i[j+1]-1]
  arr.append(ans) 
  
print(int(min(arr)))

Submission status: Accepted

Solution code:
import itertools

N, M, r = map(int, input().split())
R = list(map(int, input().split()))
E = [[10 ** 20 if i != j else 0 for i in range(N)] for j in range(N)]
for _ in range(M):
    A, B, C = map(int, input().split())
    A -= 1
    B -= 1
    E[A][B] = C
    E[B][A] = C

for d in range(N):
    for v in range(N):
        for w in range(N):
            E[v][w] = min(E[v][w], E[w][v], E[v][d] + E[d][w])
            E[w][v] = E[v][w]

res = 10 ** 20
for case in itertools.permutations(R):
    tmp = 0
    c = list(case)
    for i in range(r - 1):
        tmp += E[c[i] - 1][c[i + 1] - 1]
    res = min(res, tmp)

print(res)

Submission status: Accepted

Solution code:
from sys import stdout
import itertools
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,m,rr = inm()
r = inl()
r = [x-1 for x in r]
dst = [ [] for i in range(n) ]
for i in range(m):
    a,b,c = inm()
    dst[a-1].append((b-1,c))
    dst[b-1].append((a-1,c))

ddprint("n {} m {} r {}".format(n,m,rr))
ddprint(dst)

# warshal floyd
dist = [ [BIG]*n for i in range(n) ]
for i in range(n):
    dist[i][i] = 0
    for j,c in dst[i]:
        dist[i][j] = 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])

ddprint("dist")
ddprint(dist)

pm = itertools.permutations(r,rr)
mn = BIG
for p in pm:
    sm = 0
    #ddprint(p)
    for i in range(rr-1):
        sm += dist[p[i]][p[i+1]]
    mn = min(mn,sm)
print(mn)

Submission status: Accepted

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

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

connections = np.zeros((N,N))
for i in range(M):
    A,B,C = list(map(int,input().split()))
    A,B = A-1,B-1
    
    connections[A][B] = C
    connections[B][A] = C

connections = dijkstra(connections)

def explore(unvisited,total,start):
    if unvisited:
        ret = float('inf')
        for town in unvisited:
            ret = min(ret,explore(unvisited-set([town]),
                total+connections[start][town],town))
        return ret
    else:
        return total

ans = float('inf')
targets = set(r)
for s in r:
    ans = min(ans,explore(targets-set([s]),0,s))
print(int(ans))

Submission status: Accepted

Solution code:
import itertools
import sys
from scipy.sparse.csgraph import csgraph_from_dense
from scipy.sparse.csgraph import dijkstra
input = sys.stdin.readline


n, m, r = map(int, input().split())
visiting_town = list(map(int, input().split()))
edges = [[float('INF')]*n for _ in range(n)]

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

G = csgraph_from_dense(edges, null_value=float('INF'))
comp_dist = {}
for node in visiting_town:
    dist_list = dijkstra(G, directed=False, indices=node-1)
    comp_dist[node-1] = dist_list

candidates = []
for route in itertools.permutations(visiting_town):
    result = 0
    for _from, to in zip(route[:-1], route[1:]):
        dist = comp_dist[_from-1][to-1]
        result += dist
    candidates.append(result)

print(int(min(candidates)))

Submission status: Accepted

Solution code:
import itertools
import sys
from scipy.sparse.csgraph import csgraph_from_dense
from scipy.sparse.csgraph import dijkstra
input = sys.stdin.readline


n, m, r = map(int, input().split())
visiting_town = list(map(int, input().split()))
edges = [[float('INF')]*n for _ in range(n)]

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

G = csgraph_from_dense(edges, null_value=float('INF'))
comp_dist = dijkstra(G, directed=False)

candidates = []
for route in itertools.permutations(visiting_town):
    result = 0
    for _from, to in zip(route[:-1], route[1:]):
        dist = comp_dist[_from-1][to-1]
        result += dist
    candidates.append(result)

print(int(min(candidates)))

Submission status: Accepted

Solution code:
import itertools
import sys
from scipy.sparse.csgraph import csgraph_from_dense
from scipy.sparse.csgraph import floyd_warshall
input = sys.stdin.readline


n, m, r = map(int, input().split())
visiting_town = list(map(int, input().split()))
edges = [[float('INF')]*n for _ in range(n)]

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

G = csgraph_from_dense(edges, null_value=float('INF'))
comp_dist = floyd_warshall(G, directed=False)

candidates = []
for route in itertools.permutations(visiting_town):
    result = 0
    for _from, to in zip(route[:-1], route[1:]):
        dist = comp_dist[_from-1][to-1]
        result += dist
    candidates.append(result)

print(int(min(candidates)))

Submission status: Accepted

Solution code:
import heapq
import itertools
from collections import defaultdict


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

edges = [[] for i in range(n+1)]
for _ in range(m):
    _from, to, distance = map(int, input().split())
    edges[_from].append([to, distance])
    edges[to].append([_from, distance])


comp_edges = defaultdict(dict)
for _from in visiting_town:
    seen = [False] * (n+1)
    todo = []
    for to, dist in edges[_from]:
        heapq.heappush(todo, [dist, to])

    while todo:
        dist, node = heapq.heappop(todo)
        if seen[node]:
            continue

        seen[node] = dist
        for to, add_dist in edges[node]:
            if seen[to] or to == _from:
                continue
            new_dist = dist + add_dist
            heapq.heappush(todo, [new_dist, to])

    for to in visiting_town:
        if to == _from:
            continue
        comp_edges[_from][to] = seen[to]

candidates = []
for route in itertools.permutations(visiting_town):
    result = 0
    for _from, to in zip(route[:-1], route[1:]):
        if to in comp_edges[_from]:
            dist = comp_edges[_from][to]
            result += dist
        else:
            break
    candidates.append(result)

print(min(candidates))

Submission status: Accepted

Solution code:
import itertools
n, m, r = map(int, input().split())
t = list(map(int, input().split()))
t.sort()
d = [[10 ** 18]*n for j in range(n)]
for i in range(n):
    d[i][i] = 0

for i in range(m):
    a, b, c = map(int, input().split())
    a -= 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 = 10**18
for p in itertools.permutations(t):
    now = 0
    for i in range(r-1):
        now += d[p[i]-1][p[i + 1]-1]
    ans = min(ans, now)
print(ans)

Submission status: Accepted

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

def main():
    N, M, RR = map(int, input().split())
    R = list(map(int, input().split()))
    INF = float("inf")
    T = [[INF] * N for _ in range(N)]
    for _ in range(M):
        a, b, c = tuple(map(int, input().split()))
        T[a-1][b-1] = c
        T[b-1][a-1] = c
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if T[i][j] > T[i][k]+T[k][j]:
                    T[i][j] = T[i][k]+T[k][j]
    print(min(sum(T[rs[i]-1][rs[i+1]-1] for i in range(RR-1)) for rs in permutations(R)))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    N, M, RR = map(int, input().split())
    R = list(map(int, input().split()))
    INF = float("inf")
    T = [[INF] * N for _ in range(N)]
    for _ in range(M):
        a, b, c = tuple(map(int, input().split()))
        T[a-1][b-1] = c
        T[b-1][a-1] = c
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if T[i][j] > T[i][k]+T[k][j]:
                    T[i][j] = T[i][k]+T[k][j]
    ans = INF
    for rs in permutations(R):
        cost = 0
        for i in range(RR-1):
            cost += T[rs[i]-1][rs[i+1]-1]
        ans = min(ans, cost)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    import itertools
    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()