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:
n,m,r = map(int,input().split())
r = list(map(int,input().split()))
node = [list(map(int,input().split())) for _ in range(m)]
dic = {}
for i in range(1,n+1):
    dic[i] = {}
    for j in range(1,n+1):
        dic[i][j]=10**6
for a,b,c in node:
    dic[a][b] = c
    dic[b][a] = c
dp = [[10**8]*(n+1) for _ in range(n+1)]
for i in range(n+1):
    dp[0][i] = 0
for i in range(1,n+1):
    for j in range(1,n+1):
        if i==j:
            dp[i][j] = 0
            continue
        dp[i][j] = dic[i][j]
        for k in range(1,n+1):
            if i==k or k==j:
                continue
            dp[i][j] = min(dp[i][j], dic[i][k]+dic[k][j])
import copy
def dfs(dv,nv,cost):
    if sum(dv)==len(dv):
        return cost
    ret = []
    for i in range(len(dv)):
        if dv[i]==1:
            continue
        dv_ = copy.copy(dv)
        dv_[i] = 1
        ret.append(dfs(dv_,r[i],cost+dp[nv][r[i]]))
    return min(ret)
print(dfs([0]*len(r),0,0))

Submission status: Wrong Answer

Solution code:
n,m,r = map(int,input().split())
r = list(map(int,input().split()))
node = [list(map(int,input().split())) for _ in range(m)]
dic = {}
for i in range(1,n+1):
    dic[i] = {}
    for j in range(1,n+1):
        dic[i][j]=10**6
for a,b,c in node:
    dic[a][b] = c
    dic[b][a] = c
dp = [[10**8]*(n+1) for _ in range(n+1)]
for i in range(n+1):
    dp[0][i] = 0
for i in range(1,n+1):
    for j in range(1,n+1):
        if i==j:
            continue
        dp[i][j] = dic[i][j]
        for k in range(1,n+1):
            dp[i][j] = min(dp[i][j], dic[i][k]+dic[k][j])
import copy
def dfs(dv,nv,cost):
    if sum(dv)==len(dv):
        return cost
    ret = []
    for i in range(len(dv)):
        if dv[i]==1:
            continue
        dv_ = copy.copy(dv)
        dv_[i] = 1
        ret.append(dfs(dv_,r[i],cost+dp[nv][r[i]]))
    return min(ret)
print(dfs([0]*len(r),0,0))

Submission status: Wrong Answer

Solution code:
n,m,r = map(int,input().split())
r = list(map(int,input().split()))
node = [list(map(int,input().split())) for _ in range(m)]
dic = {}
for i in range(1,n+1):
    dic[i] = {}
    for j in range(1,n+1):
        dic[i][j]=10**6
for a,b,c in node:
    dic[a][b] = c
    dic[b][a] = c
dp = [[10**8]*(n+1) for _ in range(n+1)]
for i in range(n+1):
    dp[0][i] = 0
for i in range(1,n+1):
    for j in range(1,n+1):
        dp[i][j] = dic[i][j]
        for k in range(1,n+1):
            dp[i][j] = min(dp[i][j], dic[i][k]+dic[k][j])
import copy
def dfs(dv,nv,cost):
    if sum(dv)==len(dv):
        return cost
    ret = []
    for i in range(len(dv)):
        if dv[i]==1:
            continue
        dv_ = copy.copy(dv)
        dv_[i] = 1
        ret.append(dfs(dv_,r[i],cost+dp[nv][r[i]]))
    return min(ret)
print(dfs([0]*len(r),0,0))

Submission status: Wrong Answer

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

n,m,l=map(int,input().split())
arr=list(map(int,input().split()))
d=[[10**10 for i in range(n)] for j in range(n)]
for i in range(m):
  u,v,w=map(int,input().split())
  d[u-1][v-1]=w
  d[v-1][u-1]=w
for i in range(n):
  d[i][i]=0
d=floyd_warshall(d,directed=False)
c=list(itertools.permutations(arr,min(8,l)))
ans=10**10
for i in c:
  tmp=0
  for j in range(min(8,l)-1):
    tmp+=d[i[j]-1][i[j+1]-1]
  ans=min(tmp,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
N,M,R = [ int(it) for it in input().split() ]
ri = [ int(it) for it in input().split() ]
edge = [ [ int(it) for it in input().split() ]  for i in range(M) ]

li = [ [0]*N for i in range(N) ]
for a,b,c in edge:
  li[a-1][b-1]=c
  li[b-1][a-1]=c

for p in range(10000):
  Flag = True
  for i in range(N):
    for j in range(N):
      for k in range(N):
        li_ikj =  li[i][k]+li[k][j]
        if ( li[i][j] > li_ikj ):
          Flag = False
          li[i][j] = li_ikj
  if Flag:
    break

import itertools as ite
ms = 100000000000000000000000000000000000
for route in ite.permutations( ri ):
  s = 0
  for i in range( len(route)-1 ):
    s += li[route[i]-1][route[i+1]-1]
  ms = min(s,ms)
print ( ms )

Submission status: Wrong Answer

Solution code:
import itertools
n, m, r = map(int, input().split())
distination = set(map(int, input().split()))
inf = 10 ** 9
d = [[inf for _ in range(n)] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
for i in range(n):
    d[i][i] = 0
for i in range(n):
    for j in range(n):
        for k in range(n):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])
ans = inf
for p in itertools.permutations(distination):
    cost = 0
    for i in range(r-1):
        cost += d[p[i]-1][p[i+1]-1]
    ans = min(ans, cost)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
n, m, r = map(int, input().split())
distination = set(map(int, input().split()))
inf = 10 ** 9
d = [[inf for _ in range(n)] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    d[a-1][b-1] = min(d[a-1][b-1], c)
    d[b-1][a-1] = min(d[b-1][a-1], c)
for i in range(n):
    for j in range(n):
        for k in range(n):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])
ans = inf
for p in itertools.permutations(distination):
    cost = 0
    for i in range(r-1):
        cost += d[p[i]-1][p[i+1]-1]
    ans = min(ans, cost)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
n, m, r = map(int, input().split())
distination = set(map(int, input().split()))
inf = 10 ** 9
d = [[inf for _ in range(n)] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
for i in range(n):
    for j in range(n):
        for k in range(n):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])
ans = inf
for p in itertools.permutations(distination):
    cost = 0
    for i in range(r-1):
        cost += d[p[i]-1][p[i+1]-1]
    ans = min(ans, cost)
print(ans)

Submission status: Wrong Answer

Solution code:
N, M, R = map(int, input().split())
R_LIST = list(map(int, input().split()))
ABC = []
for _ in range(M):
    a,b,c = map(int, input().split())
    ABC.append((a,b,c))

edges = ABC[:]

 
# 無効グラフなので双方向にする
graph = {}
for a,b,c in edges:
    if not a in graph:
        graph[a] = {}
    if not b in graph:
        graph[b] = {}
    graph[a][b] = c
    graph[b][a] = c
 
 
from heapq import heappush, heappop
 
def dijkstra(graph, start):
    A = [None] * (N+1)
    queue = [(0, start)]
    while queue:
        path_len, v = heappop(queue)
        if A[v] is None: # v is unvisited
            A[v] = path_len
            for w, edge_len in graph[v].items():
                if A[w] is None:
                    heappush(queue, (path_len + edge_len, w))
 
    # to give same result as original, assign zero distance to unreachable vertices             
    return [0 if x is None else x for x in A]
 

#最短経路
shortest = [[0] * (N+1)]
for i in range(1, N+1):
    shortest.append(dijkstra(graph, i))
    
# 順列全探索
import sys
INT_MAX = sys.maxsize # 9223372036854775807
ans = INT_MAX

import queue

rest = set(R_LIST[:])

import copy  
def dfs(cost,pre,rest):
    if len(rest) == 0:
        return cost
    
    ret = INT_MAX
    for r in rest:
        print(rest)
        if pre == None:
            next_cost = 0
        else:
            next_cost = cost + shortest[pre][r]
        
        if next_cost >= ret:
            continue
            
        next_rest = copy.copy(rest)
        next_rest.remove(r)
        
        tmp_ret = dfs(next_cost, r, next_rest)
        ret = min(ret, tmp_ret)
        
    return ret


print(dfs(0, None, rest))

Submission status: Wrong Answer

Solution code:
INF = float('inf')

N,M,RR = map(int,input().split(" "))
R = list(map(lambda x:int(x)-1,input().split(" ")))
G = [[] for i in range(N)]
sq = [[(x==y)-1 for x in range(RR)] for y in range(RR)]
for i in range(M):
    a,b,c = map(int,input().split(" "))
    a -= 1
    b -= 1
    G[a].append((b,c))
    G[b].append((a,c))

for i in range(RR):
    E = [INF]*N
    F = [0]*N
    E[R[i]] = 0
    F[R[i]] = 1
    q = R[i]
    c = 1
    while c != N:
        for a,b in G[q]:
            if F[a]:
                continue
            E[a] = min(E[a],E[q] + b)
        q = min(range(N),key=lambda x:E[x]+F[x]*INF)
        F[q] = 1
        c += 1
    for j in range(RR):
        sq[i][j] = E[R[j]]

q = [[[],0,0]]
s = []
while len(q):
    a,b,c = q.pop()
    if b == RR:
        s.append(c)
        continue
    for i in range(RR):
        if i in a:
            continue
        d = c + (b and sq[a[-1]][i])
        q.append([a+[i],b+1,d])

print(min(s))

Submission status: Wrong Answer

Solution code:
from itertools import permutations

N, M, R = (int(i) for i in input().split())
#print(N, M, R)

r=[int(i) for i in input().split()]
#print(r)

dist=[[float('inf') for i in range(201)] for j in range(201)]
for i in range(201):
    dist[i][i] = 0

for i in range(M):
  a,b,c=(int(i) for i in input().split())
  dist[a][b]=c
  dist[b][a]=c

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

dict0=float('inf')
mylist=list(permutations(r,len(r)))
print(mylist)

for i in mylist:
  tmp=0
  for j in range(len(i)-1):
    tmp+=dist[i[j]][i[j+1]]
  if tmp < dict0:
    dict0=tmp

print(dict0)

Submission status: Wrong Answer

Solution code:
from itertools import product, permutations

INF=1145141919810

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

road=[[0 if x==y else INF for y in range(N+1)] for x in range(N+1)]

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

for i,j,k in product(range(N+1), repeat=3):
	road[i][j] = min(road[i][j], road[i][k] + road[k][j])

print(min(sum(road[p[i-1]][p[i]] for i in range(1, R)) for p in permutations(r)))

Submission status: Wrong Answer

Solution code:
from itertools import permutations
def warshall_floyd(n,e):
  INF=float("inf")
  g=[[INF]*n for _ in range(n)]
  for i in range(n):g[i][i]=0
  for a,b,c in e:g[a][b],g[b][a]=c,c
  for k in range(n):
    for i in range(n):
      for j in range(n):g[i][j]=min(g[i][k]+g[k][j],g[i][j])
  return g
n,m,rl=map(int,input().split());r,e=list(map(lambda x:int(x)-1,input().split())),[]
for i in range(m):x,y,z=map(int,input().split());e.append([x-1,y-1,z])
d=warshall_floyd(n,e)
a=float("inf")
for i in permutations(range(rl)):
  aa=0
  for x,y in zip(i,i[1:]):aa+=d[r[x]-1][r[y]-1]
  a=min(a,aa)
print(a)

Submission status: Wrong Answer

Solution code:
import itertools

N,M,R = map(int,input().split())
r = list(map(lambda x:int(x)-1,input().split()))
ABC = [list(map(int,input().split())) for _ in range(M)]
INF = 10**7
d = [[INF]*N for _ in range(N)]

for A,B,C in ABC:
    d[A-1][B-1] = C
    d[B-1][A-1] = C
for k in range(N):
    for i in range(k+1):
        for j in range(i+1,k+1):
            d[i][j] = min(d[i][j],d[i][k]+d[k][j])
            d[j][i] = d[i][j]
ans = INF * M
for r in itertools.permutations(r):
    S = 0
    for i,ri in enumerate(r[:-1]):
        S += d[ri][r[i+1]]
    ans = min(ans,S)
print(ans)

Submission status: Wrong Answer

Solution code:
#高速化heapqダイクストラ

from collections import *
from heapq import*
import sys
input=lambda:sys.stdin.readline()

n,m,r=map(int,input().split())
d=defaultdict(list)
*r,=map(int,input().split())
for s in range(m):
    a,b,c=map(int,input().split())
    d[a].append([b,c])
    d[b].append([a,c])
#defaultdict(<class 'list'>, {1: [[2, 1], [3, 1]], 2: [[1, 1], [3, 3]], 3: [[1, 1], [2, 3]]})

def DIJKSTRA(point,d):
    cost      = {node:float("inf") for node in d.keys()}
    Q         = []  #頂点のリスト
    cost[point]=0  #開始地点のコストをゼロとする（当たり前
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost
print(max(max(DIJKSTRA(i,d).values())for i in r))

Submission status: Wrong Answer

Solution code:
#D問題

#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

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

dist = [[float("inf") for i in range(N)] for i in range(N)] 
#dist[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(M):
    a,b,c = map(int,input().split())
    dist[a-1][b-1] = c
    dist[b-1][a-1] = c
for i in range(N):
    dist[i][i] = 0 #自身のところに行くコストは０
dist=warshall_floyd(dist)

ever=[]
MIN=10000000
def ans_func(ever):
    global R
    global r
    global dist
    global MIN
    
    if len(ever) == R:
        if R == 2:
            kari=dist[ever[0]][ever[1]]
            MIN=min(MIN,kari)
        else:
            kari=0
            for i in range(R-1):
                kari+=dist[ever[i]][ever[i+1]]
            MIN=min(MIN,kari)
    else:
        i=0
        for i in range(R):
            if r[i]-1 in ever:
                pass
            else:
                ever.append(r[i]-1)
                ans_func(ever)
                ever.remove(r[i]-1)
    return
ans_func(ever)
print(MIN)

Submission status: Wrong Answer

Solution code:
n, m, r = map(int,input().split())
r_list = list(map(int,input().split()))
INF = float('inf')
edge = []
for _ in range(m):
    a,b,c = map(int,input().split())
    edge.append([a-1,b-1,c])
def warshall_floyd(n,edge):
    graph = [[INF]*n for _ in range(n)]
    for i in range(n):
        graph[i][i] = 0
    for a, b, c in edge:
        graph[a][b] = c
        graph[b][a] = c
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if graph[i][k] + graph[k][j] < graph[i][j] :
                    graph[i][j] = graph[i][k] + graph[k][j]
    return graph
g = warshall_floyd(n,edge)
from itertools import permutations
ans = INF
for arr in permutations(range(r)):
    tmp = 0
    for a,b in zip(arr,arr[1:]):
        t1,t2 = r_list[a],r_list[b]
        tmp += g[t1-1][t2-1]
    ans = min(ans,tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
n, m, r = map(int,input().split())
r_list = list(map(int,input().split()))
INF = float('inf')
edge = []
for _ in range(m):
    a,b,c = map(int,input().split())
    edge.append([a-1,b-1,c])
def warshall_floyd(n,edge):
    graph = [[INF]*n for _ in range(n)]
    for i in range(n):
        graph[i][i] = 0
    for a, b, c in edge:
        graph[a][b] = c
        graph[b][a] = c
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if graph[i][k] + graph[k][j] < graph[i][j] :
                    graph[i][j] = graph[i][k] + graph[k][j]
    return graph
g = warshall_floyd(n,edge)
from itertools import permutations
ans = INF
for arr in permutations(r_list):
    tmp = 0
    for i in range(1,r):
        tmp += g[arr[i-1]-1][arr[i]-1]
    ans = min(ans,tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
n, m, r = map(int,input().split())
r_list = list(map(int,input().split()))
INF = float('inf')
edge = []
for _ in range(m):
    a,b,c = map(int,input().split())
    edge.append([a-1,b-1,c])
def warshall_floyd(n,edge):
    graph = [[INF]*n for _ in range(n)]
    for i in range(n):
        graph[i][i] = 0
    for a, b, c in edge:
        graph[a][b] = c
        graph[b][a] = c
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if graph[i][k] + graph[k][j] < graph[i][j] :
                    graph[i][j] = graph[i][k] + graph[k][j]
    return graph
g = warshall_floyd(n,edge)
print(g)
from itertools import permutations
ans = INF
for arr in permutations(r_list):
    tmp = 0
    for i in range(1,r):
        tmp += g[arr[i-1]-1][arr[i]-1]
    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()))
INF = float('inf')
edge = []
for _ in range(m):
    a,b,c = map(int,input().split())
    edge.append([a-1,b-1,c])
def warshall_floyd(n,edge):
    graph = [[INF]*n for _ in range(n)]
    for i in range(n):
        graph[i][i] = 0
    for a, b, c in edge:
        graph[a][b] = c
        graph[b][a] = c
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if graph[i][k] + graph[k][j] < graph[i][j] :
                    graph[i][j] = graph[i][k] + graph[k][j]
    return graph
g = warshall_floyd(n,edge)
from itertools import permutations
ans = INF
for arr in permutations(r):
    tmp = 0
    for i in range(1,min(len(r),8)):
        tmp += g[arr[i-1]-1][arr[i]-1]
    ans = min(ans,tmp)
print(ans)

Submission status: Wrong Answer

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

graph = {i+1:set() for i in range(N)}
route = []
ans = 10 ** 100

for i in range(M):
    A, B, C = list(map(int, input().split()))
    graph[A].add((B, C))
    graph[B].add((A, C))

    route.extend([[{A}, B, C], [{B}, A, C]])

while len(route):
    r_ = route.pop(-1)
    r_[0].add(r_[1])
    if r_[0] & r == r:
        ans = min(ans, r_[2])
    else:
        for g in graph[r_[1]]:
            if g[0] not in r_[0] and r_[2]+g[1] < ans:
                route.append([r_[0], g[0], r_[2]+g[1]])
print(ans)

Submission status: Wrong Answer

Solution code:
N, M, R = list(map(int, input().split()))
r = set(list(map(int, input().split())))
route = []
ans = 10**30

graph = {i:[] for i in range(1, N+1)}

for i in range(M):
    A, B, C = list(map(int, input().split()))
    graph[A].append((B, C))
    graph[B].append((A, C))
    route.append([[A, B], B, C])
    route.append([[A, B], A, C])

while len(route):
    tmp = route.pop(0)
    if set(tmp[0]) & r == r:
        ans = min(ans, tmp[2])
    else:
        for r_, cost in graph[tmp[1]]:
            if r_ not in tmp[0]:
                tmp[0].append(r_)
                tmp[1] = r_
                tmp[2] += cost
                route.append(tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
from itertools import permutations
n, m, r = [int(item) for item in input().split()]
rs = [int(item) for item in input().split()]
abc = [[int(item) for item in input().split()] for _ in range(m)]
INF = 10**6

class Dijkstra:
    def __init__(self, adj):
        self.adj = adj
        self.num = len(adj)
        self.dist = [INF] * self.num
        self.prev = [INF] * self.num
        self.q = []

    def reset(self):
        self.dist = [INF] * self.num
        self.prev = [INF] * self.num
        self.q = []

    def calc(self, start, goal=None):
        self.dist[start] = 0
        heapq.heappush(self.q, (0, start))
        while len(self.q) != 0:
            prov_cost, src = heapq.heappop(self.q)
            if self.dist[src] < prov_cost:
                continue
            for dest in range(self.num):
                cost = self.adj[src][dest]
                if cost != INF and self.dist[dest] > self.dist[src] + cost:
                    self.dist[dest] = self.dist[src] + cost
                    heapq.heappush(self.q, (self.dist[dest], dest))
                    self.prev[dest] = src
        if goal is not None:
            return self.get_path(goal)
        else:
            return self.dist

    def get_path(self, goal):
        path = [goal]
        dest = goal

        while self.prev[dest] != INF:
            path.append(self.prev[dest])
            dest = self.prev[dest]
        return list(reversed(path))

path = [[INF] * n for _ in range(n)]
short_path = [[INF] * n for _ in range(n)]
for i in range(n):
    path[i][i] = 0
for a, b, c in abc:
    path[a-1][b-1] = path[b-1][a-1] = c

dij = Dijkstra(path)
for item in rs:
    short_path [item-1] = dij.calc(item-1)
    dij.reset()

ans = INF
for pattern in permutations(rs):
    distance = 0
    for i in range(1,r):
        distance += short_path[pattern[i-1]-1][pattern[i]-1]
    ans = min(ans, distance)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations as pe
from scipy.sparse.csgraph import floyd_warshall as wf
n,m,r=map(int,input().split())
s=[[(0 if i==j else float("inf"))for j in range(n+1)]for i in range(n+1)]
g=list(pe(list(map(int,input().split()))))
for i in range(m):
    a,b,c=map(int,input().split())
    s[a][b]=c
    s[b][a]=c
s=wf(s,directed=False)
k=float("inf")
for i in range(len(g)):
    d=g[i]
    c=0
    for j in range(1,len(d)):
        c+=s[d[j-1]][d[j]]
        if c>=k:
            break
    else:
        k=min(c,k)
print(k)

Submission status: Wrong Answer

Solution code:
N,M,R=map(int,input().split())
X=list(map(int,input().split()))
from collections import defaultdict
from collections import deque
branch=defaultdict(set)
for m in range(M):
    a,b,c=map(int,input().split())
    branch[a]|={(b,c)}
    branch[b]|={(a,c)}
def makedist(x):
    dist=[float('inf')]*(N+1)
    dist[x]=0
    check=[x]
    while len(check)>0:
        now=check.pop()
        for b in branch[now]:
            if dist[now]+b[1]<dist[b[0]]:
                dist[b[0]]=dist[now]+b[1]
                check.append(b[0])
    return dist
data=dict()
for x in X:
    data[x]=makedist(x)
print(0)

Submission status: Wrong Answer

Solution code:
import itertools
import math
from collections import deque
from collections import defaultdict
from itertools import permutations
import heapq
INF = float("inf")
#入力
N,M,R = map(int,input().split())
r = list(map(int,input().split()))
adj_cost = defaultdict(set)

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

def dijkstra(v):
    d = [INF] * N
    d[v] = 0
    hq =[(0,v)]

    while hq:
        u = heapq.heappop(hq)[1]
        for (v,c) in adj_cost[u]:
            if d[v] > d[u] + c:
                d[v] = d[u] +c
                heapq.heappush(hq,(d[u]+c,v))
    return d

ans = INF
table = {}
for i in r:
    table[i-1] = dijkstra(i-1)

for each in permutations(r):
    dis = 0
    for i in range(R-1):
        dis += table[each[i]-1][each[i+1]-1]

    ans = min(ans,dis)

Submission status: Wrong Answer

Solution code:
from itertools import permutations as per

n,m,r = map(int,input().split())
rlist = list(map(int,input().split()))
ans = 10**9
A = [[10**8]*n for _ in range(n)]
for i in range(n):
  A[i][i] = 0
for _ in range(m):
  a,b,c = map(int,input().split())
  A[a-1][b-1] = c
  A[b-1][a-1] = c

for i in range(n):
  for j in range(n):
    for k in range(n):
      A[i][j] = max(A[i][j], A[i][k] + A[k][j])
for x in per(rlist):
  cost = 0
  for i in range(r-1):
    cost += A[x[i]-1][x[i+1]-1]
  if cost < ans:
    ans = cost
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations as per

n,m,r = map(int,input().split())
rlist = list(map(int,input().split()))
ans = 10**9
A = [[10**8]*n for _ in range(n)]
for i in range(n):
  A[i][i] = 0
for _ in range(m):
  a,b,c = map(int,input().split())
  A[a-1][b-1] = c
  A[b-1][a-1] = c

for i in range(n-1):
  for j in range(i+1,n):
    for k in range(n):
      newd = A[i][k] + A[k][j]
      if A[i][j] > newd:
        A[i][j] = newd
        A[j][i] = newd
for x in per(rlist):
  cost = 0
  for i in range(r-1):
    cost += A[x[i]-1][x[i+1]-1]
  if cost < ans:
    ans = cost
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

INF = float("inf")


def main():
    N, M, R = map(int, input().split())
    r = list(map(int, input().split()))
    path = [[INF]*(N) for _ in range(N)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        path[A-1][B-1] = C
        path[B-1][A-1] = C
    for i in range(N):
        path[i][i] = 0
    for i in range(N):
        for j in range(N):
            for k in range(N):
                path[i][j] = min(path[i][j], path[i][k] + path[k][j])
    ans = INF
    for p in itertools.permutations(r):
        cost = 0
        for i in range(1, R):
            cost += path[p[i-1]-1][p[i]-1]
        ans = min(ans, cost)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import itertools

INF = float("inf")


def main():
    N, M, R = map(int, input().split())
    r = list(map(int, input().split()))
    path = [[INF]*(N+1) for _ in range(N+1)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        path[A][B] = C
        path[B][A] = C
    for i in range(1, N+1):
        path[i][i] = 0
    for i in range(1, N+1):
        for j in range(1, N+1):
            for k in range(1, N+1):
                path[i][j] = min(path[i][j], path[i][k] + path[k][j])
    ans = INF
    for p in itertools.permutations(r):
        cost = 0
        for i in range(1, R):
            cost += path[p[i-1]][p[i]]
        ans = min(ans, cost)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import itertools

INF = 10**9


def main():
    N, M, R = map(int, input().split())
    r = list(map(int, input().split()))
    path = [[INF]*(N+1) for _ in range(N+1)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        path[A][B] = C
        path[B][A] = C
    for i in range(1, N+1):
        path[i][i] = 0
    for i in range(1, N+1):
        for j in range(1, N+1):
            for k in range(1, N+1):
                path[i][j] = min(path[i][j], path[i][k] + path[k][j])
    ans = INF
    for p in itertools.permutations(r):
        cost = 0
        for i in range(1, R):
            cost += path[p[i-1]][p[i]]
        ans = min(ans, cost)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

#A

#B

#C
"""
n = I()
d = defaultdict(int)
for i in range(n):
    a = I()
    d[a] ^= 1
d = list(d.values())
print(sum(d))
"""
#D
n,m,R = LI()
r = LI()
f = [i for i in range(n)]
for i in range(R):
    r[i] -= 1
    if r[i] != i:
        f[f.index(i)] = r[i]
        f[r[i]] = i
        r[i] = i
v = [[float("inf") for j in range(n)] for i in range(n)]
for i in range(n):
    v[i][i] = 0
po = [1]
for i in range(R):
    po.append(2*po[-1])
for i in range(m):
    a,b,c = LI()
    a -= 1
    b -= 1
    v[f[a]][f[b]] = c
    v[f[b]][f[a]] = c
for k in range(n):
    for i in range(n):
        for j in range(n):
            v[i][j] = min(v[i][j],v[i][k]+v[k][j])
dp = [[float("inf") for i in range(po[R])] for j in range(R)]
for i in range(R):
    dp[i][po[i]] = 0
for k in range(R):
    for i in range(po[R]):
        for j in range(R):
            if i&po[k] > 0 and i&po[j] == 0:
                dp[j][i|po[j]] = min(dp[j][i|po[j]],dp[k][i]+v[k][j])
ans = float("inf")
for i in range(R):
    ans = min(ans, dp[i][po[R]-1])
print(ans)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Wrong Answer

Solution code:
from itertools import permutations
import heapq


def warshall(N, ABCs):
    dists = [[100000 * 200 + 1 for _ in range(N)] for __ in range(N)]
    for i in range(N):
        dists[i][i] = 0

    for a, b, c in ABCs:
        dists[a - 1][b - 1] = c
        dists[b - 1][a - 1] = c

    for s in range(N):
        for e in range(N):
            for i in range(N):
                dists[s][e] = min(dists[s][e], dists[s][i] + dists[i][e])
    return dists


def dijkstra(s, e, N, adjlist):
    q = [(0, s)]
    while len(q):
        d, i = heapq.heappop(q)
        if i == e:
            return d
        for nexti, nextd in adjlist[i - 1]:
            heapq.heappush(q, (d + nextd, nexti))
    return None

def dense_dijkstra(s, e, N, ABCs):
    distsmap = [[-1 for _ in range(N)] for __ in range(N)]
    for a, b, c in ABCs:
        distsmap[a - 1][b - 1] = c
        distsmap[b - 1][a - 1] = c

    M = 100000 * 200 + 1
    dists = [M for _ in range(N)]
    visited = [False for _ in range(N)]
    dists[s - 1] = 0

    while True:
        minW, index = min([(dists[i], i) for i in range(N) if not visited[i]])
        visited[index] = True
        if minW == M:
            return -1
        if index + 1 == e:
            return minW
        for rindex, w in enumerate(distsmap[index]):
            if w == -1:
                continue
            dists[rindex] = min(dists[rindex], minW + w)


def solve(N, M, R, Rs, ABCs):
    dists = [[-1 for _ in range(N)] for __ in range(N)]
    adjlist = [[] for _ in range(N)]
    for a, b, c in ABCs:
        adjlist[a - 1].append((b, c))
        adjlist[b - 1].append((a, c))
    ans = 100000 * 200 + 1
    for way in permutations(Rs):
        tans = 0
        for s, e in zip(way, way[1:]):
            if dists[s - 1][e - 1] == -1:
                d = dense_dijkstra(s, e, N, ABCs)
                dists[s - 1][e - 1] = d
                dists[e - 1][s - 1] = d
            else:
                d = dists[s - 1][e - 1]
            tans += d
        ans = min(ans, tans)

    return ans

if __name__ == "__main__":
    N, M, R = tuple(map(int, input().split(" ")))
    Rs = list(map(int, input().split(" ")))
    ABCs = [tuple(map(int, input().split(" "))) for _ in range(M)]
    print(solve(N, M, R, Rs, ABCs))