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.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 in range(R - 1):
        tmp += distance[tour[i]][tour[i + 1]]

    if tmp < answer:
        answer = tmp

print(int(answer))

Submission status: Accepted

Solution code:
# ABC073D - joisino's travel
from heapq import heappop, heappush
from itertools import permutations

inf = 1 << 30

def dijkstra(source: int, edges: "List[Tuple[int, int]]") -> "List[int]":
    """
    Compute the distance of the shortest path from V_source to each vertex.

    Args:
        source: V_source
        edges: Edges info
    Returns:
        dist: A list of distance from V_source
    """
    edges_count = len(edges)
    dist = [inf] * edges_count
    dist[source] = 0
    undetermined = edges_count - 1  # V_0 is determined in 1-idx graph
    queue = [(0, source)]
    while queue:
        cost, v = heappop(queue)
        if cost > dist[v]:
            continue
        for next_cost, u in edges[v]:
            if cost + next_cost < dist[u]:
                dist[u] = cost + next_cost
                heappush(queue, (dist[u], u))
        undetermined -= 1
        if not undetermined:
            break
    return dist  # There may be no path from V_source to some vertices.

def main():
    N, M, R, *RABC = map(int, open(0).read().split())
    visit, ABC = RABC[:R], RABC[R:]
    edges = [[] for _ in range(N + 1)]
    for v, u, cost in zip(*[iter(ABC)] * 3):
        edges[v].append((cost, u)), edges[u].append((cost, v))
    dist = {v: dijkstra(v, edges) for v in visit}
    ans = inf
    for perm in permutations(visit):
        cur = sum(dist[v][u] for v, u in zip(perm, perm[1:]))
        ans = min(ans, cur)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools
N, M, r = map(int, input().split())
R = [int(a)-1 for a in input().split()]

X = [[0 if i == j else 1<<100 for j in range(N)] for i in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    X[a-1][b-1] = c
    X[b-1][a-1] = c

for k in range(N):
    for i in range(N):
        for j in range(N):
            X[i][j] = min(X[i][j], X[i][k] + X[k][j])
mi = 1<<100
for A in itertools.permutations(R, r):
    mi = min(mi, sum([X[A[i-1]][A[i]] for i in range(1, r)]))

print(mi)

Submission status: Accepted

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

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

edge = np.zeros((N+1,N+1))
for _ in range(M):
    A,B,C = map(int,input().split())
    edge[A,B] = C

dist = shortest_path(edge,directed = False).astype(int)

answer = 10**18
for visit in itertools.permutations(r):
    p = 0
    prev = visit[0]
    for x in visit[1:]:
        if prev != None:
            p += dist[prev,x]
        prev = x
    answer = min(answer,p)

print(answer)

Submission status: Accepted

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

N,M,R=map(int,input().split())
r=[int(x)-1 for x in input().split()]
dist=[[0 for _ in range(N)] for _ in range(N)]
for i in range(M):
    x,y,z=map(int,input().split())
    dist[x-1][y-1]=z
    dist[y-1][x-1]=z
tr=floyd_warshall(dist)
ans=10**12
for tmp in permutations(r):
    cnt=0
    for i in range(R-1):
        cnt+=tr[tmp[i]][tmp[i+1]]
    ans=min(ans,cnt)

print(int(ans))

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    def dfs(i=-1,s=0,cnt=1):
        if cnt==rn:return s
        if i==-1:
            return min(dfs(j) for j in range(rn))
        vis[i]=True
        ri=rr[i]
        res=inf
        for j in range(rn):
            if vis[j]:continue
            rj=rr[j]
            res=min(res,dfs(j,s+dist[ri][rj],cnt+1))
        vis[i]=False
        return res


    inf=10**9
    n, m, rn = MI()
    rr = LI()
    to = defaultdict(list)
    dist=[[inf]*n for _ in range(n)]
    for _ in range(m):
        a, b, c = MI()
        a, b = a - 1, b - 1
        to[a].append((b, c))
        to[b].append((a, c))
        dist[a][b]=dist[b][a]=c
    for w in range(n):
        distw=dist[w]
        for u in range(n):
            for v in range(n):
                duv=distw[u]+distw[v]
                if duv<dist[u][v]:dist[u][v]=dist[v][u]=duv
    vis=[False]*rn
    print(dfs())

main()

Submission status: Accepted

Solution code:
import itertools

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

D = [[float('inf') for _ in range(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

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 = float('inf')
for p in list(itertools.permutations(r)):
  d = 0
  for i in range(R-1):
    d += D[p[i]-1][p[i+1]-1]
  ans = min(d,ans)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

def main():
    N, M, R = map(int, input().split())
    r = list(map(int, input().split()))
    d = [[float('inf')] * 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 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 = float('inf')
    for D in list(permutations(r)):
        tmp = 0
        for i in range(len(D)-1):
            tmp += d[D[i]-1][D[i+1]-1]
        ans = min(ans, tmp)

    print(ans)



           



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:


from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]

def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
#ts=time.time()
#sys.setrecursionlimit(10**6)
input=sys.stdin.readline
show_flg=False
#show_flg=True

n,m,R=MI()
r=LI_()
g,_=GI(n,m)

show(g)
inf=float('inf')
def wf(e):
    n=len(e)
    d=[[inf]*n for _ in range(n)]
    for a in range(n):
        for b,c in g[a]:
            d[a][b]=c
            d[b][a]=c
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j]>d[i][k]+d[j][k]:
                    d[i][j]=d[i][k]+d[j][k]
    
    return d

ans=inf
md=wf(g)
dists=[]
def search(st,d,ls):
    if len(ls)==1:
        dists.append(d+md[st][ls[0]])
        return
    for gl in ls:
        search(gl,d+md[st][gl],[i for i in ls if i!=gl])
    return

for i in r:search(i,0,[j for j in r if i!=j])
print(min(dists))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect_left
from heapq import heappush, heappop
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M, R = MAP()
r = LIST()
ABC = [LIST() for _ in range(M)]

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

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

for A, B, C in ABC:
    dist[A-1][B-1] = C
    dist[B-1][A-1] = C

graph = csr_matrix(dist)
dist_mat = floyd_warshall(graph, directed=False)

ans = INF
for n in permutations(r):
    tmp = 0  
    for i in range(1, len(r)):
        tmp += dist_mat[n[i-1]-1][n[i]-1]
    ans = min(ans, tmp)
print(int(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()))
s=[[0]*n for i in range(n)]
for i in range(m):
    a, b, c = list(map(int, input().split()))
    a, b = a-1, b-1
    s[a][b] = c
    s[b][a] = c
s=floyd_warshall(s)   

ans=float('inf')
for i in permutations(r):
    an=0
    for j in range(R-1):
        an+=s[i[j]-1][i[j+1]-1]
    ans=min(ans,an)
print(int(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 _ in range(M)]

cost = [[float('inf')] * N for _ in range(N)]
for i in range(M):
    a, b, c = abc[i][0], abc[i][1], abc[i][2]
    cost[a-1][b-1] = c
    cost[b-1][a-1] = c

from scipy.sparse.csgraph import floyd_warshall
dist = floyd_warshall(cost)

mindist = float('inf')
import itertools
for it in itertools.permutations(r):
    it = list(it)
    d = 0
    for i in range(R - 1):
        d += int(dist[it[i]-1][it[i+1]-1])
    # print(it)
    mindist = min(mindist, d)
print(mindist)

Submission status: Accepted

Solution code:
from itertools import permutations
from scipy.sparse.csgraph import dijkstra, csgraph_from_dense
N, M, R = map(int, input().split())
t = set(map(int, input().split()))
ABC = [map(int, input().split()) for i in range(M)]

root = [[10**9]*N for i in range(N)]
for a, b, c in ABC:
    root[a-1][b-1] = c
    root[b-1][a-1] = c
g = csgraph_from_dense(root, null_value=10**9)
G = dijkstra(g)
ans = 10**9
for l in permutations(t):
    tmp = 0
    for i in range(1, R):
        tmp += min(root[l[i-1]-1][l[i]-1], G[l[i-1]-1][l[i]-1])
    ans = min(tmp, ans)
print(int(ans))

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def sortx(x,n,k):
    if k == 0:x.sort(key=lambda y:y[1,n])
    else:x.sort(reversed=True, key=lambda y:y[1,n])

def graphm():
    n,m=inpm()
    g=[[] for _ in range(n)]
    for _ in range(m):
        a,b,w=inpm()
        a-=1
        b-=1
        g[a].append((w,b))
        g[b].append((w,a))
    return n,m,g

def warshall_floyd(): # d[i][j]: iからjへの最短距離
    n,m,r = map(int,input().split()) #n:頂点数　w:辺の数
    R=inpl()
    d=[[10**10 for _ in range(n)] for _ in range(n)]
    for i in range(m):
        x,y,z = inpm()
        x -= 1
        y -= 1
        d[x][y] = z
        d[y][x] = z
    for i in range(n):
        d[i][i] = 0 #自身のところに行くコストは0
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    ans = float('inf')
    for com in permutations(R,r):
        ans_pre = 0
        for i in range(r-1):
            ans_pre += d[com[i]-1][com[i+1]-1]
        ans = min(ans,ans_pre)
    print(ans)

def main(): 
    warshall_floyd()

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import permutations as per
input = sys.stdin.readline
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
d = [[float("inf")] * (N + 1) for _ in range(N + 1)]
for i in range(N + 1):
  d[i][i] = 0
for _ in range(M):
  a, b, c = map(int, input().split())
  d[a][b] = c
  d[b][a] = c

for k in range(1, N + 1):
  for i in range(1, N + 1):
    for j in range(1, N + 1):
      d[i][j] = min(d[i][k] + d[k][j], d[i][j])
res = float("inf")
for p in per(r, R):
  t = 0
  for i in range(R - 1):
    t += d[p[i]][p[i + 1]]
  res = min(t, res)
print(res)

Submission status: Accepted

Solution code:
from itertools import permutations
def wf(d):
  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=map(int,input().split());R=min(r,8)
d = [[10**12for i in range(n)]for j in range(n)]
l=[int(i)-1 for i in input().split()]
for i in range(m):
  a,b,c=map(int,input().split())
  d[a-1][b-1]=d[b-1][a-1] = c
d=wf(d)
#print(d)
ans=30**8
for v in permutations(l):
  cnt=sum(d[v][u] for v, u in zip(v, v[1:]))
  ans=min(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
# import itertools
# r = list(range(4))
# for indices in itertools.permutations(r):
#     print(list(indices))
# exit()


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

INF = float("inf")
table = [[INF for _ in range(N)] for _ in range(N)]
for i in range(N):
    table[i][i] = 0

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

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

# print(table)
import itertools
ans = INF
len_r = len(r)
for indices in itertools.permutations(r):
    indices = list(indices)
    ans = min(ans, sum([table[indices[i]][indices[i+1]] for i in range(len_r-1)]))

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop
import itertools
n,m,r=map(int,input().split())
l1=list(map(int,input().split()))
inf=10**10
l=[[] for i in range(n+1)]
for i in range(m):
  a,b,c=map(int,input().split())
  l[a].append([b,c])
  l[b].append([a,c])
def dijkstra(s):
  q=[(0,s)]
  dist=[inf]*(n+1)
  dist[s]=0
  while q:
    c,v=heappop(q)
    if dist[v]<c:
      continue
    for i in l[v]:
      t=i[0]
      cost=i[1]
      if dist[v]+cost<dist[t]:
        dist[t]=dist[v]+cost
        heappush(q,[dist[t],t])
  return dist
dic={}
for i in range(r):
  d=dijkstra(l1[i])
  dic[l1[i]]=d
p=itertools.permutations(l1,r)
ans=inf
for i in p:
  p1=i
  ans1=0
  for j in range(r-1):
    num1=p1[j]
    num2=p1[j+1]
    ans1+=dic[num1][num2]
  if ans>ans1:
    ans=ans1
print(ans)

Submission status: Accepted

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

#warshall_floyd法
def warshall_floyd(dist):
    #dist[i][j]: iからjへの最短距離
    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])
    return dist

inf = float("inf")
dist = [[inf for i in range(N)] for j in range(N)]
for i in range(N):
    dist[i][i] = 0

for i in range(M):
    a,b,c = map(int,input().split())
    dist[a-1][b-1] = c
    dist[b-1][a-1] = c
    
dist = warshall_floyd(dist)
per = [i for i in range(R)]
ind = list(itertools.permutations(per,R))

MIN = inf
for index in ind:
    now = 0
    for i in range(R-1):
        f = index[i]
        b = index[i+1]
        now+=dist[rlist[f]-1][rlist[b]-1]
    MIN = min(MIN,now)
    
print(MIN)

Submission status: Accepted

Solution code:
N, M, R = map(int, input().split())
towns = list(map(int, input().split()))
allEdges = [[float('inf') for i in range(N)] for i in range(N)]
for i in range(M):
    A, B, C = map(int, input().split())
    allEdges[A-1][B-1] = C
    allEdges[B-1][A-1] = C

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

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

for i in range(R):
    for j in range(R):
        graph[i][j] = allEdges[towns[i] - 1][towns[j] - 1]

dp = [[-1 for i in range(R)] for j in range(1 << R)]

def recurse(seen, cur):
    if seen == (1 << R) - 1:
        return 0
    if dp[seen][cur] != -1:
        return dp[seen][cur]
    
    cost = float('inf')
    for i in range(R):
        if seen & (1 << i) == 0:
            cost = min(cost, recurse(seen | (1 << i), i) + graph[cur][i])
    dp[seen][cur] = cost
    return dp[seen][cur]

cost = float('inf')
for i in range(R):
    cost = min(cost, recurse(1 << i, i))

print(cost)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m,r=map(int,input().split())
    R=list(map(lambda x:int(x)-1,input().split()))
    A=[[INF]*n for _ in range(n)]
    for _ in range(m):
        a,b,c=map(int,input().split())
        a-=1; b-=1
        A[a][b]=A[b][a]=c

    from itertools import product
    for k,i,j in product(range(n),repeat=3):
        A[i][j]=min(A[i][j],A[i][k]+A[k][j])

    # dp[V][x] : 経過済みの頂点V 最後の到達地点x
    N=2**r
    dp=[[INF]*r for _ in range(N)]

    # initialize dp[1<<x][x]=0
    for x in range(r):
        dp[1<<x][x]=0

    # iterate
    for V in range(N):
        for x in range(r):
            if(not (V>>x)&1): continue
            for y in range(r):
                if((V>>y)&1): continue # 既に y に到達している場合は考えない
                dp[V+(1<<y)][y]=min(dp[V+(1<<y)][y],dp[V][x]+A[R[x]][R[y]])

    # output
    print(min(dp[N-1][x] for x in range(r)))
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m,r=map(int,input().split())
    R=list(map(lambda x:int(x)-1,input().split()))
    A=[[INF]*n for _ in range(n)]
    for _ in range(m):
        a,b,c=map(int,input().split())
        a-=1; b-=1
        A[a][b]=A[b][a]=c

    from itertools import product
    for k,i,j in product(range(n),repeat=3):
        A[i][j]=min(A[i][j],A[i][k]+A[k][j])

    from itertools import permutations
    ans=INF
    for p in permutations(R):
        score=0
        for i in range(r-1):
            score+=A[p[i+1]][p[i]]
        ans=min(ans,score)
    print(ans)
resolve()

Submission status: Accepted

Solution code:
import itertools

N,M,R = map(int, input().split())
rlist = [int(r) for r in input().split()]
INF = 10**9
E = [[INF]*N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    E[a-1][b-1] = c
    E[b-1][a-1] = c
    
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])
            
ans = 10**9

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

Submission status: Accepted

Solution code:
import sys
from itertools import permutations
input = sys.stdin.buffer.readline
inf = float('inf')

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
adj = [[inf for _ in range(N+1)] for _ in range(N+1)]
for _ in range(M):
    a, b, c = map(int, input().split())
    adj[a][b] = c
    adj[b][a] = c

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

ans = inf
for r_list in permutations(r):
    ans_new = 0
    for i in range(R-1):
        ans_new += adj[r_list[i]][r_list[i+1]]
    ans = min(ans, ans_new)

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
import heapq
N,M,R=map(int,input().split())
r=list(map(int,input().split()))
abc=[[] for _ in range(N)]
for _ in range(M):
  a,b,c=map(int,input().split())
  abc[a-1].append([b,c])
  abc[b-1].append([a,c])

l=[]
for s in r:
  nseen=[i for i in r]
  dist=[float("inf")]*N
  dist[s-1]=0
  q=[[dist[i],i] for i in range(N)]
  heapq.heapify(q)
  while q:
    d,ind=heapq.heappop(q)
    if d<=dist[ind]:
      for n,c in abc[ind]:
        if dist[n-1]>d+c:
          dist[n-1]=d+c
          heapq.heappush(q,[dist[n-1],n-1])
  l.append(dist)

ans=float("inf")
seen=[]
dis=0
def dfs(pos):
  global dis
  global ans
  seen.append(pos)
  if len(seen)==R:
    ans=min(ans,dis)
  else:
    for i in r:
      if i not in seen:
        dis+=l[r.index(pos)][i-1]
        dfs(i)
        dis-=l[r.index(pos)][i-1]
  seen.remove(pos)

for i in r:
  dfs(i)
  
print(ans)

Submission status: Accepted

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

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

edge=np.zeros((n+1,n+1))
for i in range(m):
    a,b,c=map(int,input().split())
    edge[a,b]=c

dist=shortest_path(edge,directed=False).astype(int)

ans=10**18
for v in itertools.permutations(r):
    ans2=0
    p=v[0]
    for x in v[1:]:
        if p!=None:
            ans2+=dist[p,x]
        p=x
    ans=min(ans,ans2)

print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m,R = LI()
    r = LI()
    for i in range(R):
        r[i] -= 1
    v = [[float("inf")]*n for i in range(n)]
    for i in range(m):
        a,b,c = LI()
        a -= 1
        b -= 1
        v[a][b] = c
        v[b][a] = c
    l = 1<<R
    for k in range(n):
        for i in range(n):
            for j in range(n):
                nv = v[i][k]+v[j][k]
                if nv < v[i][j]:
                    v[i][j] = nv
    dp = [[float("inf")]*R for i in range(l)]
    for i in range(R):
        dp[1<<i][i] = 0
    for b in range(l):
        for i in range(R):
            if not (1<<i)&b:
                continue
            x = r[i]
            for j in range(R):
                bj = 1<<j
                if bj&b:
                    continue
                y = r[j]
                nd = dp[b][i]+v[x][y]
                nb = b|bj
                if nd < dp[nb][j]:
                    dp[nb][j] = nd
    print(min(dp[-1]))
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n, m, R = LI()
    r = LI_()
    edg = [[inf] * n for i in range(n)]
    for _ in range(m):
        a, b, c = LI_()
        c += 1
        edg[a][b] = c
        edg[b][a] = c
    for i in range(n):
        edg[i][i] = 0
    for k in range(n):
        for i in range(n):
            for j in range(n):
                edg[i][j] = min(edg[i][j], edg[i][k] + edg[k][j])
    fulls = itertools.permutations(range(R), R)
    ans = inf
    for full in fulls:
        b = -1
        tmp = 0
        for f in full:
            if b == -1:
                b = r[f]
                continue
            tmp += edg[r[f]][b]
            b = r[f]
        ans = min(ans, tmp)
    print(ans)

    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    A()

Submission status: Accepted

Solution code:
import sys, copy
from itertools import permutations

def wf(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())
Rs = list(map(int,input().split()))

d = [[float('inf') for i in range(N)] for i in range(N)]
for _ in range(M):
  a,b,c = map(int,sys.stdin.readline().split())
  d[a-1][b-1] = c
  d[b-1][a-1] = c

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

wf(d)

ans = float('inf')
for prm in permutations(Rs, R):
  ans = min(ans, sum([d[prm[i-1]-1][prm[i]-1] for i in range(1,R)]))
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    wn, wm, r = list(map(int, input().rstrip('\n').split()))
    rl = list(map(int, input().rstrip('\n').split()))
    inf = 10 ** 13
    wl = [[inf] * wn for _ in range(wn)]
    for i in range(wn):
        wl[i][i] = 0

    for i in range(wm):
        wa, wb, wc = list(map(int, input().rstrip('\n').split()))
        wl[wa - 1][wb - 1] = wc
        wl[wb - 1][wa - 1] = wc

    for i in range(wn):
        for j in range(wn):
            for k in range(wn):
                wl[j][k] = min(wl[j][k], wl[j][i] + wl[i][k])
    mt = 10 ** 10
    for v in itertools.permutations(rl):
        t = 0
        for i in range(1, r):
            t += wl[v[i]-1][v[i-1]-1]
        mt = min(mt, t)
    print(mt)


if __name__ == '__main__':
    solve()

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:
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=[[INF]*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:
from itertools import product, permutations


def warshall_floyd(d):
    # d        : nxn adjacent matrix
    for k, i, j in product(range(n), repeat=3):
        if d[i][j] > d[i][k] + d[k][j]:
            d[i][j] = d[i][k] + d[k][j]


INF = float("inf")
n, m, r = map(int, input().split())
r_list = list(map(lambda x: int(x) - 1, input().split()))
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())
    a, b = a - 1, b - 1
    d[a][b] = d[b][a] = c
warshall_floyd(d)

ans = float("inf")
for np in permutations(r_list):
    cand = sum([d[np[i]][np[i + 1]] for i in range(r - 1)])
    ans = min(ans, cand)

print(ans)