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: Wrong Answer

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([r1])
        stack=[0]
        heapify(stack)
        dic={0:[r1]}
        while stack:
            m=heappop(stack)
            a=dic[m].pop()
            for b in data[a]:
                if not b in visited or b==r2:
                    visited.add(b)
                    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: Wrong Answer

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

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=[[0 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]
        stack=deque([[r1,set([r1]),r1]])
        visited=set([r1])
        ikulst=set()
        while stack:
            a,miti,mae=stack.popleft()
            for b in data[a]:
                if b!=mae:
                    if not b in visited:
                        visited.add(b)
                        tempmiti=copy.copy(miti)
                        tempmiti.add(b)
                        if b==r2:
                            ikulst=ikulst|tempmiti
                        else:
                            stack.append([b,tempmiti,a])
                    elif b in ikulst:
                        ikulst=ikulst|miti



        stack=[[r1,0]]
        minpoint=[100000*200+1 for i in range(N+1)]
        """
        while stack:
            a,m=stack.pop()
            for b in data[a]:
                if b in ikulst:
                    A,B=min(a,b),max(a,b)
                    tempm=m+nagasa[str(A)+" "+str(B)]
                    if tempm<minpoint[b]:
                        minpoint[b]=tempm
                        if b==r2:
                            pass
                        else:
                            stack.append([b,tempm])"""
        mokutekiti[r1i][r2i]=minpoint[r2]
        mokutekiti[r2i][r1i]=minpoint[r2]

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: Wrong Answer

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

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=[[0 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]
        stack=deque([[r1,[r1]]])
        visited=set([r1])
        ikulst=set()
        while stack:
            a,miti=stack.popleft()
            for b in data[a]:
                if not b in visited:
                    visited.add(b)
                    tempmiti=copy.copy(miti)
                    tempmiti.append(b)
                    if b==r2:
                        for i in tempmiti:
                            ikulst.add(i)
                    else:
                        stack.append([b,tempmiti])
                elif b in ikulst:
                    for i in tempmiti:
                        ikulst.add(i)



        stack=[[r1,0]]
        minpoint=[100000*200+1 for i in range(N+1)]
        while stack:
            a,m=stack.pop()
            for b in data[a]:
                if b in ikulst:
                    A,B=min(a,b),max(a,b)
                    tempm=m+nagasa[str(A)+" "+str(B)]
                    if tempm<minpoint[b]:
                        minpoint[b]=tempm
                        if b==r2:
                            pass
                        else:
                            stack.append([b,tempm])
        mokutekiti[r1i][r2i]=minpoint[r2]
        mokutekiti[r2i][r1i]=minpoint[r2]

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: Wrong Answer

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

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=[[0 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]
        stack=[[r1,0]]
        minpoint=[100001 for i in range(N+1)]
        while stack:
            a,m=stack.pop()
            for b in data[a]:
                A,B=min(a,b),max(a,b)
                tempm=m+nagasa[str(A)+" "+str(B)]
                if tempm<minpoint[b]:
                    minpoint[b]=tempm
                    if b==r2:
                        pass
                    else:
                        stack.append([b,tempm])
        mokutekiti[r1i][r2i]=minpoint[r2]
        mokutekiti[r2i][r1i]=minpoint[r2]

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: Wrong Answer

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

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=[[0 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]
        stack=[[r1,0]]
        minpoint=[100000 for i in range(N+1)]
        while stack:
            a,m=stack.pop()
            for b in data[a]:
                A,B=min(a,b),max(a,b)
                tempm=m+nagasa[str(A)+" "+str(B)]
                if tempm<minpoint[b]:
                    minpoint[b]=tempm
                    if b==r2:
                        pass
                    else:
                        stack.append([b,tempm])
        mokutekiti[r1i][r2i]=minpoint[r2]
        mokutekiti[r2i][r1i]=minpoint[r2]

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: Wrong Answer

Solution code:
import itertools

N, M, _ = 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 v in range(N):
    for d 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(len(R) - 1):
        tmp += E[c[i] - 1][c[i + 1] - 1]
    res = min(res, tmp)

print(res)

Submission status: Wrong Answer

Solution code:
import itertools

N, M, _ = 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 v in range(N):
    for d in range(N):
        for w in range(N):
            E[v][w] = min(E[v][w], 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(len(R) - 1):
        tmp += E[c[i] - 1][c[i + 1] - 1]
    res = min(res, tmp)

print(res)

Submission status: Wrong Answer

Solution code:
import itertools

N, M, _ = map(int, input().split())
R = list(map(int, input().split()))
E = [[10 ** 12 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 v in range(N):
    for d in range(N):
        for w in range(N):
            E[v][w] = min(E[v][w], E[v][d] + E[d][w])
            E[w][v] = E[v][w]
res = 10 ** 12
for case in itertools.permutations(R):
    tmp = 0
    c = list(case)
    for i in range(len(R) - 1):
        tmp += E[c[i] - 1][c[i + 1] - 1]
    res = min(res, tmp)

print(res)

Submission status: Wrong Answer

Solution code:
import itertools

N, M, _ = map(int, input().split())
R = list(map(int, input().split()))
E = [[10 ** 12 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 v in range(N):
    for d in range(N):
        for w in range(N):
            E[v][w] = min(E[v][w], E[v][d] + E[d][w])
            E[v][w] = E[w][v]
res = 10 ** 12
for case in itertools.permutations(R):
    tmp = 0
    c = list(case)
    for i in range(len(R) - 1):
        tmp += E[c[i] - 1][c[i + 1] - 1]
    res = min(res, tmp)

print(res)

Submission status: Wrong Answer

Solution code:
import itertools

N, M, _ = map(int, input().split())
R = list(map(int, input().split()))
E = [[10 ** 12 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 v in range(N):
    for d in range(N):
        for w in range(N):
            E[v][w] = min(E[v][w], E[v][d] + E[d][w])
res = 10 ** 12
for case in itertools.permutations(R):
    tmp = 0
    c = list(case)
    for i in range(len(R) - 1):
        tmp += E[c[i] - 1][c[i + 1] - 1]
    res = min(res, tmp)

print(res)

Submission status: Wrong Answer

Solution code:
import itertools

N, M, _ = map(int, input().split())
R = list(map(int, input().split()))
E = [[10 ** 8 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 v in range(N):
    for d in range(N):
        for w in range(N):
            E[v][w] = min(E[v][w], E[v][d] + E[d][w])
            E[w][v] = E[v][w]
res = 10 ** 8
for case in itertools.permutations(R):
    tmp = 0
    c = list(case)
    for i in range(len(R) - 1):
        tmp += E[c[i] - 1][c[i + 1] - 1]
    res = min(res, tmp)

print(res)

Submission status: Wrong Answer

Solution code:
import itertools

N, M, _ = map(int, input().split())
R = list(map(int, input().split()))
E = [[10 ** 8 for _ in range(N)] for __ 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 v in range(N):
    for d in range(N):
        for w in range(N):
            E[v][w] = min(E[v][w], E[v][d] + E[d][w])

res = 10 ** 8
for case in itertools.permutations(R):
    tmp = 0
    p = None
    for v in case:
        v -= 1
        if p is None:
            p = v
            continue
        tmp += E[p][v]
        p = v
    res = min(res, tmp)

print(res)

Submission status: Wrong Answer

Solution code:
import itertools

N, M, _ = map(int, input().split())
R = list(map(int, input().split()))
E = [[10 ** 8 for _ in range(N)] for __ 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 v in range(N):
    for d in range(N):
        for w in range(N):
            E[v][w] = min(E[v][w], E[v][d] + E[d][w])

res = 10 ** 8
for case in itertools.permutations(range(len(R))):
    tmp = 0
    p = None
    for v in case:
        v -= 1
        if p is None:
            p = v
            continue
        tmp += E[p][v]
        p = v
    res = min(res, tmp)

print(res)

Submission status: Wrong Answer

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: Wrong Answer

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**3
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: Wrong Answer

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: Wrong Answer

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)]
dist=[inf]*N
visited=[False]*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 i in range(N):
    for j in range(N):
        for k 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(ans)

Submission status: Wrong Answer

Solution code:
N,M,R=[int(x) for x in str(input()).split()]
r=[int(x) for x in str(input()).split()]
A=[[100001 for j in range(N)] for i in range(N)]
for i in range(N):
  A[i][i]=0

for i in range(M):
  temp=[int(x) for x in str(input()).split()]
  
  A[min(temp[0],temp[1])-1][max(temp[0],temp[1])-1]=temp[2]

for k in range(0,N):
    for i in range(0,N):
        for j in range(0,N):
            if A[i-1][j-1] > A[i-1][k-1] + A[k-1][j-1]:
                A[i-1][j-1] = A[i-1][k-1] + A[k-1][j-1]


s=""
for i in range(R):
  s+=str(r[i])


def perm(st):
  if len(st)==1:
    return st
  else:
    ANS=[]
    for i in range(len(st)):
      t=perm(st[:i]+st[i+1:])
      for j in range(len(t)):
        ANS.append(st[i]+t[j])
    return ANS


T=perm(s)


mi=10000000000000
for i in range(len(T)):
  ans=T[i]
  tm=0
  for j in range(len(r)-1):
    a=int(ans[j])
    b=int(ans[j+1])
    tm+=A[min(a,b)-1][max(a,b)-1]


    
  mi=min(mi,tm)
print(mi)

Submission status: Wrong Answer

Solution code:
N,M,R=[int(x) for x in str(input()).split()]
r=[int(x) for x in str(input()).split()]
A=[[100001 for j in range(N)] for i in range(N)]
for i in range(N):
  A[i][i]=0

for i in range(M):
  temp=[int(x) for x in str(input()).split()]
  
  A[min(temp[0],temp[1])-1][max(temp[0],temp[1])-1]=temp[2]

for k in range(0,N):
    for i in range(0,N):
        for j in range(0,N):
            if A[i-1][j-1] > A[i-1][k-1] + A[k-1][j-1]:
                A[i-1][j-1] = A[i-1][k-1] + A[k-1][j-1]

s=""
for i in range(R):
  s+=str(r[i])


def perm(st):
  if len(st)==1:
    return st
  else:
    ANS=[]
    for i in range(len(st)):
      t=perm(st[:i]+st[i+1:])
      for j in range(len(t)):
        ANS.append(st[i]+t[j])
    return ANS


T=perm(s)


mi=20000001
for i in range(len(T)):
  ans=T[i]
  tm=0
  for j in range(len(r)-1):
    a=int(ans[j])
    b=int(ans[j+1])
    tm+=A[min(a,b)-1][max(a,b)-1]

    
  mi=min(mi,tm)
print(mi)

Submission status: Wrong Answer

Solution code:
N,M,R=[int(x) for x in str(input()).split()]
r=[int(x) for x in str(input()).split()]
A=[[100001 for j in range(N+1)] for i in range(N+1)]
for i in range(N+1):
  A[i][i]=0

for i in range(M):
  temp=[int(x) for x in str(input()).split()]
  A[temp[0]][temp[1]]=temp[2]
  A[temp[1]][temp[0]]=temp[2]


for k in range(0,N+1):
    for i in range(0,N+1):
        for j in range(0,N+1):
            if A[i][j] > A[i][k] + A[k][j]:
                A[i][j] = A[i][k] + A[k][j]

s=""
for i in range(R):
  s+=str(r[i])


def perm(st):
  if len(st)==1:
    return [st]
  else:
    ANS=[]
    for i in range(len(st)):
      t=perm(st[:i]+st[i+1:])
      for j in range(len(t)):
        ANS.append(st[i]+t[j])
    return ANS

T=perm(s)

mi=900000
for i in range(len(T)):
  ans=T[i]
  tm=0
  for j in range(len(r)-1):

    tm+=A[int(ans[j])][int(ans[j+1])]
  mi=min(mi,tm)
print(mi)

Submission status: Wrong Answer

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=[[100001 for i in range(N+1)]]

for i in range(N):
  dis.append([100001 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=100000000000000
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: Wrong Answer

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 = 10**6
    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: Wrong Answer

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 = 10**6
    root = np.full((N,N),INF)
    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):
                root[j][k] = min(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: Wrong Answer

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 = [[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

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: Wrong Answer

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)

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

Submission status: Wrong Answer

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 = 10000000
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: Wrong Answer

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 = list(map(lambda x : int(x) - 1, input().split()))

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)

ans = 10000000
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: Wrong Answer

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 = list(map(lambda x : int(x) - 1, 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 = 10000000
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: Wrong Answer

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 = list(map(lambda x : int(x) - 1, input().split()))

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 = 10000000
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(ans)

Submission status: Wrong Answer

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 = list(map(lambda x : int(x) - 1, 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

warshall(route, n)

ans = 10000000
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(ans)

Submission status: Wrong Answer

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())
city = list(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
for i in range(n):
    route[i][i] = 0

warshall(route, n)

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

Submission status: Wrong Answer

Solution code:
from itertools import permutations as perm

def warshall(d, n):
    for k in range(n):
        for i in range(n):
            if d[i][k] == 0:
                continue
            for j in range(n):
                if d[k][j] == 0:
                    continue
                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())
city = list(map(int, input().split()))

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

warshall(route, n)

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

Submission status: Wrong Answer

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
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: Wrong Answer

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