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:
# -*- coding: utf-8 -*-
"""
Created on Sun Oct  7 22:06:12 2018
ABC073D
@author: maezawa
"""
import itertools as itr
import sys
input = sys.stdin.readline

n, m, r = list(map(int, input().split()))
rarray = list(map(int, input().split()))
#abc = []
adjmatrix = [[10**10]*(n+1) for _ in range(n+1)]
for i in range(m):
    a, b, c = list(map(int, input().split()))
    #abc.append(abci)
    if adjmatrix[a][b] > c:
        adjmatrix[a][b] = c
        adjmatrix[b][a] = c

#print(abc)

# Warshall-Floyd Algorithm
for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(i,n+1):
            if i == j:
                adjmatrix[i][j] = 0
            if adjmatrix[i][j] > adjmatrix[i][k] + adjmatrix[k][j]:
                adjmatrix[i][j] = adjmatrix[i][k] + adjmatrix[k][j]
                adjmatrix[j][i] = adjmatrix[j][k] + adjmatrix[k][i]
        
#print(*adjmatrix, sep='\n')
    
# search for ri to rj
mincnt = 10*10
for route in itr.permutations(rarray):
    cnt = 0
    for i in range(len(rarray)-1):
        cnt += adjmatrix[route[i]][route[i+1]]
    if cnt < mincnt:
        mincnt = cnt

print(mincnt)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Oct  7 22:06:12 2018
ABC073D
@author: maezawa
"""
import itertools as itr
import sys
input = sys.stdin.readline

n, m, r = list(map(int, input().split()))
rarray = list(map(int, input().split()))
#abc = []
adjmatrix = [[10**10]*(n+1) for _ in range(n+1)]
for i in range(m):
    a, b, c = list(map(int, input().split()))
    #abc.append(abci)
    if adjmatrix[a][b] > c:
        adjmatrix[a][b] = c
        adjmatrix[b][a] = c

#print(abc)

# Warshall-Floyd Algorithm
for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(i,n+1):
            if i == j:
                adjmatrix[i][j] = 0
            if adjmatrix[i][j] > adjmatrix[i][k] + adjmatrix[k][j]:
                adjmatrix[i][j] = adjmatrix[i][k] + adjmatrix[k][j]
        
#print(*adjmatrix, sep='\n')
    
# search for ri to rj
mincnt = 10*10
for route in itr.permutations(rarray):
    cnt = 0
    for i in range(len(rarray)-1):
        cnt += adjmatrix[route[i]][route[i+1]]
    if cnt < mincnt:
        mincnt = cnt

print(mincnt)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Oct  7 22:06:12 2018
ABC073D
@author: maezawa
"""
import itertools as itr
import sys
input = sys.stdin.readline

n, m, r = list(map(int, input().split()))
rarray = list(map(int, input().split()))
#abc = []
adjmatrix = [[10**10]*(n+1) for _ in range(n+1)]
for i in range(m):
    abci = list(map(int, input().split()))
    #abc.append(abci)
    adjmatrix[abci[0]][abci[1]] = abci[2]
    adjmatrix[abci[1]][abci[0]] = abci[2]

#print(abc)

# Warshall-Floyd Algorithm
for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(i,n+1):
            if i == j:
                adjmatrix[i][j] = 0
            if adjmatrix[i][j] > adjmatrix[i][k] + adjmatrix[k][j]:
                adjmatrix[i][j] = adjmatrix[i][k] + adjmatrix[k][j]
        
#print(*adjmatrix, sep='\n')
    
# search for ri to rj
mincnt = 10*10
for route in itr.permutations(rarray):
    cnt = 0
    for i in range(len(rarray)-1):
        cnt += adjmatrix[route[i]][route[i+1]]
    if cnt < mincnt:
        mincnt = cnt

print(mincnt)

Submission status: Wrong Answer

Solution code:
from itertools import permutations

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

graph = [[0 for i in range(N)] for j in range(N)]
for i in range(M):
    A, B, C = map(int, input().split())
    graph[A-1][B-1] = C
    graph[B-1][A-1] = C

ans = 10**9
for p in permutations(r, len(r)):
    dist = 0
    flag = 0
    for i in range(len(r) - 1):
        if graph[p[i]-1][p[i+1]-1] == 0:
            flag = 1
        dist += graph[p[i]-1][p[i+1]-1]
    if flag == 0:
        ans = min(ans, dist)

print(ans)

Submission status: Wrong Answer

Solution code:
n,m,r= map(int,input().split())
li = input().rstrip().split()
le =[0]*r
for i in range(0,r):
    le[i]=int(li[i])
a = [input().rstrip().split() for j in range(m)]
INF = 1000000

cost = [[INF for i in range(n)] for j in range(n)]
for i in range(0,m):
    x = int(a[i][0])-1
    y = int(a[i][1])-1
    cost[x][y]=cost[y][x]=int(a[i][2])

d = [INF]*n
#ダイクストラ法を実施
def dijkstra(s):
    d[s]=0
    used=[False]*n
    while(1):
        v = -1
        for i in range(0,n):
            if(used[i]==False)and((v==-1)or(d[i]<d[v])):
                v = i
        if (v==-1):
            break
        used[v]=True
        for i in range(0,n):
            d[i]=min(d[i],d[v]+cost[v][i])
dijkstra(le[0]-1)
mx = 0
for  i in range(0,len(le)-1):
    if mx<d[le[i+1]-1]:
        mx = d[le[i+1]-1]
print(mx)

Submission status: Wrong Answer

Solution code:
import itertools
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
DP = [[1000000 for i in range(N)] for j in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    DP[a - 1][b - 1] = c
    DP[b - 1][a - 1] = c

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

root = list(itertools.permutations(r))
finalans = 100000000
#for i in root:
 #   ans = 0
  #  for j in range(1, R):
   #     ans += DP[i[j - 1] - 1][i[j] - 1]
    #if ans < finalans:
     #   finalans = ans
        
print(finalans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
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())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
for i in range(N):
    d[i][i]=0
from scipy.sparse import csgraph
d = csgraph.floyd_warshall(d)
ans = float('inf')
for seq in permutations(r):
    s = 0
    for j in range(R-1):
        s += d[seq[j]-1][seq[j+1]-1]
    ans = min(ans,s)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
import heapq

INF = float('inf')
n, m, R = list(map(int, input().split()))
r = list(map(int, input().split()))

cost = {}
for i in range(m):
    a, b, c = list(map(int, input().split()))
    if not a in cost.keys():
        cost[a] = [(b, c)]
    else:
        cost[a].append((b, c))
    if not b in cost.keys():
        cost[b] = [(a, c)]
    else:
        cost[b].append((a, c))
        
dist = [[INF]*(n+1) for _ in range(n+1)]
for st in range(1, n+1):
    d = [INF]*(n+1)
    d[st] = 0
    path = [(0, st)]
    heapq.heapify(path)
    while len(path) > 0:
        c, node = heapq.heappop(path)
        d[node] = c
        for node_next, c_next in cost[node]:
            if d[node]+c_next < d[node_next]:
                heapq.heappush(path, (d[node]+c_next, node_next))
    dist[st] = d
# for d in dist: print(d)

ans = INF
for p in permutations(r):
    ans_ = 0
    for i in range(R-1):
        ans_ += dist[p[i]][p[i+1]]
    ans = min(ans, ans_)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
INF = float('inf')
n, m, R = map(int, input().split())
r = list(map(int, input().split()))
dist = [[INF]*(n+1) for _ in range(n+1)]
for i in range(n+1):
    dist[i][i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    dist[a][b] = c
    dist[b][a] = c
    
for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(i, n+1):
            dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
            dist[j][i] = dist[i][j]
# for d in dist: print(d)

ans = INF
for p in permutations(r):
    ans_ = 0
    for i in range(R-1):
        ans_ += dist[p[i]-1][p[i+1]-1]
    ans = min(ans, ans_)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
INF = float('inf')
n, m, R = map(int, input().split())
r = list(map(int, input().split()))
dist = [[INF]*(n+1) for _ in range(n+1)]
for i in range(n+1):
    dist[i][i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    dist[a][b] = c
    dist[b][a] = c
    
for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
# for d in dist: print(d)

ans = INF
for p in permutations(r):
    ans_ = 0
    for i in range(R-1):
        ans_ += dist[p[i]-1][p[i+1]-1]
        if ans_ > ans:
            break
    ans = min(ans, ans_)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
INF = 10**8
n, m, R = list(map(int, input().split()))
r = list(map(int, input().split()))
dist = [[INF]*(n+1) for _ in range(n+1)]
for i in range(1, n+1):
    dist[i][i] = 0
for i in range(m):
    a, b, c = list(map(int, input().split()))
    dist[a][b] = c
    dist[b][a] = c
    
for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
# for d in dist: print(d)

ans = INF
# for p in permutations(r):
#     ans_ = 0
#     for i in range(R-1):
#         ans_ += dist[p[i]][p[i+1]]
#     ans = min(ans, ans_)
print(ans)

Submission status: Wrong Answer

Solution code:
"""
atcoder workspace
"""
from itertools import permutations

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

Dmat = [[1e9] * N for i in range(N)]

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

for i in range(M):
    f, t, c = map(int, input().split())
    Dmat[f-1][t-1] = c
    Dmat[t-1][f-1] = c

for i in range(N): #mid
    for j in range(N): #from
        for k in range(j,N): #to
            Dmat[j][k] = min(Dmat[j][k], Dmat[j][i] + Dmat[i][k])

ans = 1e9
for p in permutations(Rlist):
    ans = min(ans, sum([Dmat[p[i]-1][p[i+1]-1] for i in range(R-1)]))

print(ans)

Submission status: Wrong Answer

Solution code:
INF = int(1e9)
N, M, K = list(map(int, input().split()))
R = list(map(lambda x: int(x) - 1, input().split()))

G = [[INF] * N for i in range(N)]
for i in range(N):
    G[i][i] = 0


            
for i in range(M):
    a, b, c = list(map(int, input().split()))
    a = a - 1
    b = b - 1
    G[a][b] = G[b][a] = c
    
ls = range(N)
for k in ls:
    for i in ls:
        for j in range(i+1, N):
            x = G[i][k] + G[k][j]
        if x < G[i][j]:
            G[j][i] = G[i][j] = x

dp = [[INF] * (1<<K) for i in range(K)]
for i in range(K):
    dp[i][1<<i] = 0
    
for bit in range(1<<K):
    for pre in range(K):
        if (bit >> pre) & 1 == 0:
            continue
        for to in range(K):
            if (bit >> to) & 1 == 1:
                continue
            cost = dp[pre][bit] + G[pre][R[to]]
            nbit = bit | (1<<to)
            if dp[to][nbit] > cost:
                dp[to][nbit] = cost


ans = INF     
for pre in range(K):
    ans = min(ans, dp[to][(1<<K) - 1])
print (ans)

Submission status: Wrong Answer

Solution code:
import itertools
N, M, R = map(int, input().split())
r = [int(x) - 1 for x in input().split()]
G = [[10 ** 7 for j in range(N)] for i in range(N)]
for i in range(N):
  G[i][i] = 0
for i in range(M):
  a, b, c = map(int, input().split())
  G[a - 1][b - 1] = c
  G[b - 1][a - 1] = c
def warshall_floyd(G):
  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
G = warshall_floyd(G)
D = 10 ** 7
for L in itertools.permutations(r):
  d = 0
  pre = L[0]
  for l in L[1:]:
    d += G[pre][l]
    pre = l
  D = min(d, D)
print(D)

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




from itertools import permutations
mi=1000000
BASH=[]
for item in permutations(r):
    BASH.append(list(item))

for i in BASH:

  p=0
  for j in range(0,len(i)-1):
    p+=dis[i[j]][i[j+1]]
  mi=min(mi,p)





for i in range(1,max(r)+1):
  O=r
  if i not in r:
    O.append(i)
    BASH=[]
    for item in permutations(O):
        BASH.append(list(item))

    for i in BASH:

      p=0
      for j in range(0,len(i)-1):
        p+=dis[i[j]][i[j+1]]
      mi=min(mi,p)






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




from itertools import permutations
mi=1000000
BASH=[]
for item in permutations(r):
    BASH.append(list(item))



for i in BASH:

  p=0
  for j in range(0,len(i)-1):
    p+=dis[i[j]][i[j+1]]

  mi=min(mi,p)
print(mi)

Submission status: Wrong Answer

Solution code:
import heapq

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

INF = 2 << 21
G, dist = [[] for i in range(N)], [[INF for k in range(N)] for j in range(N)]


def dijkstra(s):
    check = [0 for i in range(N)]
    dist[s][s], pq = 0, []
    heapq.heappush(pq, (0, s))

    while len(pq) != 0:
        u = heapq.heappop(pq)
        check[u[1]] = 2

        if dist[s][u[1]] < u[0]:
            continue

        for v in G[u[1]]:
            if dist[s][u[1]] + v[1] < dist[s][v[0]]:
                dist[s][v[0]], check[v[0]] = dist[s][u[1]] + v[1], 1
                heapq.heappush(pq, (dist[s][v[0]], v[0]))


check_dfs, cost_lst = [0 for m in range(R)], []


def dfs(s, cnt, cost):
    if cnt == 0:
        cost_lst.append(cost)
        return

    for i in range(R):
        if check_dfs[i] == 0:
            check_dfs[i] = 1
            dfs(r[i]-1, cnt-1, cost+dist[s][r[i]-1])
            check_dfs[i] = 0


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

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

    for i in range(R):
        check_dfs[i] = 1
        dfs(r[i]-1, R-1, 0)
        check_dfs[i] = 0

    print(min(cost_lst))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
from itertools import permutations
#グラフの作成   
def make_list(V,E):
 
    edges = []
    path=[[0]*E for i in range(V) ]   #ルート作成に必要になる
    
    for i in range(V):
        a=[int(x) for x in str(input()).split()]
        for j in range(len(a)):
            #print("j",j)
            path[i][j]=i
           # if j!= i and a[j]==0:
                #a[j]=2000
                #path[i][j]=-2000
	
        edges.append((a))    #  有効辺グラフ
	

   
     
    return edges ,path


#フロイド・ワーシャル
def warshall_floyd(glath):
	
	for k in range(len(glath)):
		for i in range(len(glath)):
			for j in range(len(glath[i])):
				if glath[i][j] > glath[i][k] + glath[k][j]:
                                   glath[i][j] = glath[i][k] + glath[k][j]
                                   glath[j][i] = glath[i][k] + glath[k][j]
				#glath[i][j]= min(int(glath[i][j]),int(glath[i][k])+int(glath[k][j]))
				
	return glath





N, M ,R= [int(x) for x in str(input()).split()]  #グラフの大きさ 

r=[int(x) for x in str(input()).split()]


graph=[[0]*N for i in range(N)]


for i in range(M):
	a,b,c=[int(x) for x in str(input()).split()]
	#if a in r and b in r:
	graph[a-1][b-1]=c
	graph[b-1][a-1]=c



#all_cost=warshall_floyd(select_graph)
all_cost=warshall_floyd(graph)


#print(all_cost)
#print(all_cost[r[0]-1-a][r[-1]-1-a])
#print(r[-1]-1-a)

max_count=float("inf")


for i in permutations(r):
        cost=0
        for j in range(len(i)-1):
                
                cost+= all_cost[i[j]-1][i[j+1]-1]
       
        max_count=min(max_count,cost)


#			max_count=min(max_count,all_cost[i-a-1][j-a-1]+all_cost[j-a-1][j-a-1])


print(max_count)

Submission status: Wrong Answer

Solution code:
import math
from itertools import permutations
#グラフの作成   
def make_list(V,E):
 
    edges = []
    path=[[0]*E for i in range(V) ]   #ルート作成に必要になる
    
    for i in range(V):
        a=[int(x) for x in str(input()).split()]
        for j in range(len(a)):
            #print("j",j)
            path[i][j]=i
           # if j!= i and a[j]==0:
                #a[j]=2000
                #path[i][j]=-2000
	
        edges.append((a))    #  有効辺グラフ
	

   
     
    return edges ,path


#フロイド・ワーシャル
def warshall_floyd(glath):
	
	for k in range(len(glath)):
		for i in range(len(glath)):
			for j in range(len(glath[i])):
				if glath[i][j] > glath[i][k] + glath[k][j]:
                                   glath[i][j] = glath[i][k] + glath[k][j]
  
				#glath[i][j]= min(int(glath[i][j]),int(glath[i][k])+int(glath[k][j]))
				
	return glath





N, M ,R= [int(x) for x in str(input()).split()]  #グラフの大きさ 

r=[int(x) for x in str(input()).split()]


graph=[[0]*N for i in range(N)]


for i in range(M):
	a,b,c=[int(x) for x in str(input()).split()]
	#if a in r and b in r:
	graph[a-1][b-1]=c
	graph[b-1][a-1]=c



#all_cost=warshall_floyd(select_graph)
all_cost=warshall_floyd(graph)


#print(all_cost)
#print(all_cost[r[0]-1-a][r[-1]-1-a])
#print(r[-1]-1-a)

max_count=float("inf")


for i in permutations(r):
        cost=0
        for j in range(len(i)-1):
                
                cost+= all_cost[i[j]-1][i[j+1]-1]
       
        max_count=min(max_count,cost)


#			max_count=min(max_count,all_cost[i-a-1][j-a-1]+all_cost[j-a-1][j-a-1])


print(max_count)

Submission status: Wrong Answer

Solution code:
import math
from itertools import permutations
#グラフの作成   
def make_list(V,E):
 
    edges = []
    path=[[0]*E for i in range(V) ]   #ルート作成に必要になる
    
    for i in range(V):
        a=[int(x) for x in str(input()).split()]
        for j in range(len(a)):
            #print("j",j)
            path[i][j]=i
           # if j!= i and a[j]==0:
                #a[j]=2000
                #path[i][j]=-2000
	
        edges.append((a))    #  有効辺グラフ
	

   
     
    return edges ,path


#フロイド・ワーシャル
def warshall_floyd(glath):
	
	for k in range(len(glath)):
		for i in range(len(glath)):
			for j in range(len(glath[i])):
				if glath[i][j] > glath[i][k] + glath[k][j]:
                                   glath[i][j] = glath[i][k] + glath[k][j]
  
				#glath[i][j]= min(int(glath[i][j]),int(glath[i][k])+int(glath[k][j]))
				
	return glath





N, M ,R= [int(x) for x in str(input()).split()]  #グラフの大きさ 

r=[int(x) for x in str(input()).split()]


graph=[[0]*N for i in range(N)]


for i in range(M):
	a,b,c=[int(x) for x in str(input()).split()]
	#if a in r and b in r:
	graph[a-1][b-1]=c
	graph[b-1][a-1]=c



#all_cost=warshall_floyd(select_graph)
all_cost=warshall_floyd(graph)


#print(all_cost)
#print(all_cost[r[0]-1-a][r[-1]-1-a])
#print(r[-1]-1-a)

max_count=9999999


for i in permutations(r):
        cost=0
        for j in range(len(i)-1):
                
                cost+= all_cost[i[j]-1][i[j+1]-1]
       
        max_count=min(max_count,cost)


#			max_count=min(max_count,all_cost[i-a-1][j-a-1]+all_cost[j-a-1][j-a-1])


print(max_count)

Submission status: Wrong Answer

Solution code:
import math
from itertools import permutations
#グラフの作成   
def make_list(V,E):
 
    edges = []
    path=[[0]*E for i in range(V) ]   #ルート作成に必要になる
    
    for i in range(V):
        a=[int(x) for x in str(input()).split()]
        for j in range(len(a)):
            #print("j",j)
            path[i][j]=i
           # if j!= i and a[j]==0:
                #a[j]=2000
                #path[i][j]=-2000
	
        edges.append((a))    #  有効辺グラフ
	

   
     
    return edges ,path


#フロイド・ワーシャル
def warshall_floyd(glath):
	
	for k in range(len(glath)):
		for i in range(len(glath)):
			for j in range(len(glath[i])):
				if glath[i][j] > glath[i][k] + glath[k][j]:
                                   glath[i][j] = glath[i][k] + glath[k][j]
  
				#glath[i][j]= min(int(glath[i][j]),int(glath[i][k])+int(glath[k][j]))
				
	return glath





N, M ,R= [int(x) for x in str(input()).split()]  #グラフの大きさ 

r=[int(x) for x in str(input()).split()]


graph=[[0]*N for i in range(N)]


for i in range(M):
	a,b,c=[int(x) for x in str(input()).split()]
	#if a in r and b in r:
	graph[a-1][b-1]=c
	graph[b-1][a-1]=c



#all_cost=warshall_floyd(select_graph)
all_cost=warshall_floyd(graph)


#print(all_cost)
#print(all_cost[r[0]-1-a][r[-1]-1-a])
#print(r[-1]-1-a)

max_count=10000000


for i in permutations(r):
        cost=0
        for j in range(len(i)-1):
                
                cost+= all_cost[i[j]-1][i[j+1]-1]
       
        max_count=min(max_count,cost)


#			max_count=min(max_count,all_cost[i-a-1][j-a-1]+all_cost[j-a-1][j-a-1])


print(max_count)

Submission status: Wrong Answer

Solution code:
import math
from itertools import permutations
#グラフの作成   
def make_list(V,E):
 
    edges = []
    path=[[0]*E for i in range(V) ]   #ルート作成に必要になる
    
    for i in range(V):
        a=[int(x) for x in str(input()).split()]
        for j in range(len(a)):
            #print("j",j)
            path[i][j]=i
           # if j!= i and a[j]==0:
                #a[j]=2000
                #path[i][j]=-2000
	
        edges.append((a))    #  有効辺グラフ
	

   
     
    return edges ,path


#フロイド・ワーシャル
def warshall_floyd(glath):
	
	for k in range(len(glath)):
		for i in range(len(glath)):
			for j in range(len(glath[i])):
				if glath[i][j] > glath[i][k] + glath[k][j]:
                                   glath[i][j] = glath[i][k] + glath[k][j]
  
				#glath[i][j]= min(int(glath[i][j]),int(glath[i][k])+int(glath[k][j]))
				
	return glath





N, M ,R= [int(x) for x in str(input()).split()]  #グラフの大きさ 

r=[int(x) for x in str(input()).split()]


graph=[[0]*N for i in range(N)]


for i in range(M):
	a,b,c=[int(x) for x in str(input()).split()]
	#if a in r and b in r:
	graph[a-1][b-1]=c
	graph[b-1][a-1]=c



#all_cost=warshall_floyd(select_graph)
all_cost=warshall_floyd(graph)



#print(all_cost[r[0]-1-a][r[-1]-1-a])
#print(r[-1]-1-a)

max_count=10000


for i in permutations(r):
        cost=0
        for j in range(len(i)-1):
                
                cost+= all_cost[i[j]-1][i[j+1]-1]
       
        max_count=min(max_count,cost)


#			max_count=min(max_count,all_cost[i-a-1][j-a-1]+all_cost[j-a-1][j-a-1])


print(max_count)

Submission status: Wrong Answer

Solution code:
import math
from itertools import permutations
#グラフの作成   
def make_list(V,E):
 
    edges = []
    path=[[0]*E for i in range(V) ]   #ルート作成に必要になる
    
    for i in range(V):
        a=[int(x) for x in str(input()).split()]
        for j in range(len(a)):
            #print("j",j)
            path[i][j]=i
           # if j!= i and a[j]==0:
                #a[j]=2000
                #path[i][j]=-2000
	
        edges.append((a))    #  有効辺グラフ
	

   
     
    return edges ,path


#フロイド・ワーシャル
def warshall_floyd(glath):
	
	for k in range(len(glath)):
		for i in range(len(glath)):
			for j in range(len(glath[i])):
				if glath[i][j] > glath[i][k] + glath[k][j]:
                                   glath[i][j] = glath[i][k] + glath[k][j]
  
				#glath[i][j]= min(int(glath[i][j]),int(glath[i][k])+int(glath[k][j]))
				
	return glath





N, M ,R= [int(x) for x in str(input()).split()]  #グラフの大きさ 

r=[int(x) for x in str(input()).split()]


graph=[[0]*N for i in range(N)]


for i in range(M):
	a,b,c=[int(x) for x in str(input()).split()]
	#if a in r and b in r:
	graph[a-1][b-1]=c
	graph[b-1][a-1]=c



#all_cost=warshall_floyd(select_graph)
all_cost=warshall_floyd(graph)


print(all_cost)
#print(all_cost[r[0]-1-a][r[-1]-1-a])
#print(r[-1]-1-a)

max_count=10000


for i in permutations(r):
        cost=0
        for j in range(len(i)-1):
                
                cost+= all_cost[i[j]-1][i[j+1]-1]
       
        max_count=min(max_count,cost)


#			max_count=min(max_count,all_cost[i-a-1][j-a-1]+all_cost[j-a-1][j-a-1])


print(max_count)

Submission status: Wrong Answer

Solution code:

import math

#グラフの作成   
def make_list(V,E):
 
    edges = []
    path=[[0]*E for i in range(V) ]   #ルート作成に必要になる
    
    for i in range(V):
        a=[int(x) for x in str(input()).split()]
        for j in range(len(a)):
            #print("j",j)
            path[i][j]=i
           # if j!= i and a[j]==0:
                #a[j]=2000
                #path[i][j]=-2000
	
        edges.append((a))    #  有効辺グラフ
	

   
     
    return edges ,path


#フロイド・ワーシャル
def warshall_floyd(glath):
	
	for k in range(len(glath)):
		for i in range(len(glath)):
			for j in range(len(glath[i])):
				if glath[i][j] > glath[i][k] + glath[k][j]:
                                   glath[i][j] = glath[i][k] + glath[k][j]
  
				#glath[i][j]= min(int(glath[i][j]),int(glath[i][k])+int(glath[k][j]))
				
	return glath





N, M ,R= [int(x) for x in str(input()).split()]  #グラフの大きさ 

r=[int(x) for x in str(input()).split()]


graph=[[0]*N for i in range(N)]


for i in range(M):
	a,b,c=[int(x) for x in str(input()).split()]
	if a in r and b in r:
		graph[a-1][b-1]=c
		graph[b-1][a-1]=c

select_graph=[[0]*len(r) for i in range(len(r))]


#グラフを抽出
for i in range(len(r)):
       for j in range(len(r)):
      
              #print("i,j",i,j)
              select_graph[i][j]=graph[r[i]-1][r[j]-1]


all_cost=warshall_floyd(select_graph)

max_count=0
for i in all_cost:
	max_count=max(a,max_count)



print(max_count)

Submission status: Wrong Answer

Solution code:
import math

#グラフの作成   
def make_list(V,E):
 
    edges = []
    path=[[0]*E for i in range(V) ]   #ルート作成に必要になる
    
    for i in range(V):
        a=[int(x) for x in str(input()).split()]
        for j in range(len(a)):
            #print("j",j)
            path[i][j]=i
           # if j!= i and a[j]==0:
                #a[j]=2000
                #path[i][j]=-2000
	
        edges.append((a))    #  有効辺グラフ
	

   
     
    return edges ,path


#フロイド・ワーシャル
def warshall_floyd(glath):
	
	for k in range(len(glath)):
		for i in range(len(glath)):
			for j in range(len(glath[i])):
				if glath[i][j] > glath[i][k] + glath[k][j]:
                                   glath[i][j] = glath[i][k] + glath[k][j]
  
				#glath[i][j]= min(int(glath[i][j]),int(glath[i][k])+int(glath[k][j]))
				
	return glath





N, M ,R= [int(x) for x in str(input()).split()]  #グラフの大きさ 

r=[int(x) for x in str(input()).split()]


graph=[[0]*N for i in range(N)]


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


    #print(cost_graph)
 
all_cost=warshall_floyd(graph)

print(all_cost[r[0]-1][r[-1]-1])

Submission status: Wrong Answer

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

from collections import defaultdict
from itertools import permutations

INF = 10**10

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

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

result = INF

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

for xs in permutations(r):
    r = 0
    for i in range(R - 1):
        st, ed = xs[i], xs[i + 1]
        r += D[st][ed]
    result = min(result, r)

print(result)

Submission status: Wrong Answer

Solution code:
from itertools import permutations

def main():
    N, M, R = map(int, input().split())
    r = map(int, input().split())
    inf = float('inf')
    d = [[inf] * N for i 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
        if d[a][b] > c:
            d[a][b], d[b][a] = c, c

    for i in range(N):
        for j in range(N):
            for k in range(N):
                temp = d[i][k] + d[k][j]
                if d[i][j] > temp:
                    d[i][j] = temp

    ans = inf
    for i in permutations(r):
        temp = 0
        for j in range(len(i)-1):
            temp += d[i[j] - 1][i[j + 1] - 1]
            if temp > ans:
                break
        if ans > temp:
            ans = temp
        # ans = min(ans, temp)

    print(ans)


main()

Submission status: Wrong Answer

Solution code:
from itertools import permutations

def main():
    N, M, R = map(int, input().split())
    r = map(int, input().split())
    inf = float('inf')
    d = [[inf] * N for i 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
        if d[a][b] > c:
            t = min(c, d[a][b])
            d[a][b], d[b][a] = t, t

    for i in range(N):
        for j in range(N):
            for k in range(N):
                temp = d[i][k] + d[k][j]
                if d[i][j] > temp:
                    d[i][j] = temp

    ans = inf
    for i in permutations(r):
        temp = 0
        for j in range(len(i)-1):
            temp += d[i[j] - 1][i[j + 1] - 1]
            if temp > ans:
                break
        ans = min(ans, temp)

    print(ans)


main()

Submission status: Wrong Answer

Solution code:
from itertools import permutations

def main():
    N, M, R = map(int, input().split())
    r = map(int, input().split())
    inf = float('inf')
    d = [[inf for j in range(N)] for i 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
        if d[a][b] > c:
            t = min(c, d[a][b])
            d[a][b], d[b][a] = t, t

    for i in range(N):
        for j in range(N):
            for k in range(N):
                temp = d[i][k] + d[k][j]
                if d[i][j] > temp:
                    d[i][j] = temp

    ans = inf
    for i in permutations(r):
        temp = 0
        for j in range(len(i)-1):
            temp += d[i[j] - 1][i[j + 1] - 1]
            if temp > ans:
                break
        ans = min(ans, temp)

    print(ans)


main()