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

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np 
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix
from itertools import combinations

I = np.array(sys.stdin.read().split(), dtype=np.int64)
n, m, R = I[:3]
r = I[3:3+R] - 1
a, b, c = I[3+R:].reshape(-1, 3).T
a -= 1; b -= 1
graph = csr_matrix((c, (a, b)), shape=(n, n))

def main():
    dist = floyd_warshall(graph, directed=False).astype(np.int64)
    *combs, = combinations(r, 2)
    v, u = np.array(combs).T 
    ans = np.amax(dist[v, u])
    return ans

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
def warshal_floyd(weights,N):
    d=weights
    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])
    return d

if __name__ == '__main__':
    N,M,R=list(map(int,input().split()))
    cities=[r-1 for r in list(map(int,input().split()))]
    weights=[[1e10 for i in range(N)] for j in range(N)]
    for i in range(M):
        a,b,c=list(map(int,input().split()))
        a-=1
        b-=1
        weights[a][b]=c
        weights[b][a]=c

    d=warshal_floyd(weights,N)
    mini_count=1e12
    for c in permutations(cities):
        count=sum(d[i][j] for i,j in zip(c,c[1:]))
        mini_count=min(mini_count,count)
    print(mini_count)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
def warshal_floyd(weights,N):
    d=[[weights[(i,j)] for i in range(N)] for j in range(N)]
    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])
    return d

if __name__ == '__main__':
    N,M,R=list(map(int,input().split()))
    cities=[r-1 for r in list(map(int,input().split()))]
    weights={(i,j):10**7 for i in range(N) for j in range(N)}
    for i in range(M):
        a,b,c=list(map(int,input().split()))
        a-=1
        b-=1
        weights[(a,b)]=c
        weights[(b,a)]=c

    d=warshal_floyd(weights,N)
    mini_count=1e12
    for c in permutations(cities):
        count=sum(d[i][j] for i,j in zip(c,c[1:]))
        mini_count=min(mini_count,count)
    print(mini_count)

Submission status: Wrong Answer

Solution code:
def warshal_floyd(weights,N):
    d=[[weights[(i,j)] for i in range(N)] for j in range(N)]
    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])
    return d

def make_iteration(R,cities):
    S=[[c] for c in cities]
    iteration=[]
    while len(S)>0:
        v=S.pop()
        if len(v)!=len(set(v)):
            continue
        if len(v)==R:
            iteration.append(v)
        else:
            for c in cities:
                S.append(v+[c])
    return iteration

if __name__ == '__main__':
    N,M,R=list(map(int,input().split()))
    cities=[r-1 for r in list(map(int,input().split()))]
    weights={(i,j):10**7 for i in range(N) for j in range(N)}
    graph=[[10*7 for i in range(N)] for j in range(N)]
    for i in range(M):
        a,b,c=list(map(int,input().split()))
        a-=1
        b-=1
        weights[(a,b)]=c
        weights[(b,a)]=c
        graph[a][b]=c
        graph[b][a]=c

    d=warshal_floyd(weights,N)
    iteration=make_iteration(R,cities)
    mini_count=1e12
    for i in iteration:
        count=0
        for r in range(R-1):
            count+=d[i[r]][i[r+1]]
        mini_count=min(mini_count,count)
    print(mini_count)

Submission status: Wrong Answer

Solution code:

def warshal_floyd(weights,N):
    d=[[weights[(i,j)] for i in range(N)] for j in range(N)]
    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])
    return d

def make_iteration(R,cities):
    S=[[c] for c in cities]
    iteration=[]
    while len(S)>0:
        v=S.pop()
        if len(v)!=len(set(v)):
            continue
        if len(v)==R:
            iteration.append(v)
        else:
            for c in cities:
                S.append(v+[c])
    return iteration

if __name__ == '__main__':
    N,M,R=list(map(int,input().split()))
    cities=list(map(int,input().split()))
    weights={(i,j):10**7 for i in range(N) for j in range(N)}
    #graph=[[10*7 for i in range(N)] for j in range(N)]
    for i in range(M):
        a,b,c=list(map(int,input().split()))
        a-=1
        b-=1
        weights[(a,b)]=min(weights[(a,b)],c)
        weights[(b,a)]=min(weights[(b,a)],c)
    d=warshal_floyd(weights,N)
    #d=floyd_warshall(weights)

    iteration=make_iteration(R,cities)
    mini_count=1e12
    for i in iteration:
        count=0
        for r in range(R-1):
            count+=d[i[r]-1][i[r+1]-1]
        mini_count=min(mini_count,count)
    print(mini_count)

Submission status: Wrong Answer

Solution code:
def warshal_floyd(weights,N):
    d=[[weights[(i,j)] for i in range(N)] for j in range(N)]
    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])
    return d

def make_iteration(R,cities):
    S=[[c] for c in cities]
    iteration=[]
    while len(S)>0:
        v=S.pop()
        if len(v)!=len(set(v)):
            continue
        if len(v)==R:
            iteration.append(v)
        else:
            for c in cities:
                S.append(v+[c])
    return iteration

if __name__ == '__main__':
    N,M,R=list(map(int,input().split()))
    cities=list(map(int,input().split()))
    weights={(i,j):1e6 for i in range(N) for j in range(N)}
    for i in range(M):
        a,b,c=list(map(int,input().split()))
        a-=1
        b-=1
        weights[(a,b)]=min(weights[(a,b)],c)
        weights[(b,a)]=min(weights[(b,a)],c)
    d=warshal_floyd(weights,N)
    iteration=make_iteration(R,cities)
    mini_count=1e12
    for i in iteration:
        count=0
        for r in range(R-1):
            count+=d[i[r]-1][i[r+1]-1]
        mini_count=min(mini_count,count)
    print(mini_count)

Submission status: Wrong Answer

Solution code:
def warshal_floyd(weights,N):
    d=[[weights[(i,j)] for i in range(N)] for j in range(N)]
    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])
    return d

def make_iteration(R,cities):
    S=[[c] for c in cities]
    iteration=[]
    while len(S)>0:
        v=S.pop()
        if len(v)!=len(set(v)):
            continue
        if len(v)==R:
            iteration.append(v)
        else:
            for c in cities:
                S.append(v+[c])
    return iteration

if __name__ == '__main__':
    N,M,R=list(map(int,input().split()))
    cities=list(map(int,input().split()))
    weights={(i,j):1e6 for i in range(N) for j in range(N)}
    for i in range(M):
        a,b,c=list(map(int,input().split()))
        a-=1
        b-=1
        weights[(a,b)]=min(weights[(a,b)],c)
        weights[(b,a)]=min(weights[(b,a)],c)
    d=warshal_floyd(weights,N)
    iteration=make_iteration(R,cities)
    mini_count=1e10
    for i in iteration:
        count=0
        for r in range(R-1):
            count+=d[i[r]-1][i[r+1]-1]
        if mini_count>count:
            mini_count=count
    print(mini_count)

Submission status: Wrong Answer

Solution code:
import sys
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall

n, m, R = [int(i) for i in sys.stdin.readline().split()]
r_ls = [int(i) - 1 for i in sys.stdin.readline().split()]
INF = 10**18
graph = [[0 for i in range(n)] for j in range(n)]
for i in range(m):
    a, b, c = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a][b] = c
    graph[b][a] = c

graph_new = csgraph_from_dense(graph)
res = floyd_warshall(graph_new)
res = res[r_ls][:,r_ls]
memo_ls = [[None for i in range(R)] for j in range(2**R)]
def bit_dp(state, pos, cost):
    score = INF
    if state == 2**R - 1:
        return cost
    if memo_ls[state][pos] is not None:
        return memo_ls[state][pos]
    for next_t, next_c in enumerate(res[pos]):
        if next_c == 0:
            continue
        if (state >> next_t) & 1:
            continue
        score = min(score, bit_dp(state | 2**next_t, next_t, cost + next_c))
    memo_ls[state][pos] = score
    return score

best = INF
for i in range(R):
    memo_ls = [[None for i in range(R)] for j in range(2 ** R)]
    hoge = bit_dp(2**i, i, 0)
    best = min(hoge, best)
print(int(best))

Submission status: Wrong Answer

Solution code:
import sys
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall

n, m, R = [int(i) for i in sys.stdin.readline().split()]
r_ls = [int(i) - 1 for i in sys.stdin.readline().split()]
INF = 10**18
graph = [[0 for i in range(n)] for j in range(n)]
for i in range(m):
    a, b, c = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a][b] = c
    graph[b][a] = c

graph_new = csgraph_from_dense(graph)
res = floyd_warshall(graph_new)
res = res[r_ls][:,r_ls]

memo_ls = [[None for i in range(R)] for j in range(2**R)]
def bit_dp(state, pos, cost):
    score = INF
    if state == 2**R - 1:
        memo_ls[state][pos] = cost
        return cost
    if memo_ls[state][pos] is not None:
        return memo_ls[state][pos]
    for next_t, next_c in enumerate(res[pos]):
        if next_c == 0:
            continue
        if (state >> next_t) & 1:
            continue
        score = min(score, bit_dp(state | 2**next_t, next_t, cost + next_c))
    memo_ls[state][pos] = score
    return score

best = INF
for i in range(R):
    memo_ls = [[None for i in range(R)] for j in range(2 ** R)]
    hoge = bit_dp(2**i, i, 0)
    best = min(hoge, best)
print(int(best))

Submission status: Wrong Answer

Solution code:
import sys
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall

n, m, R = [int(i) for i in sys.stdin.readline().split()]
r_ls = [int(i) - 1 for i in sys.stdin.readline().split()]
INF = 10**18
graph = [[0 for i in range(n)] for j in range(n)]
for i in range(m):
    a, b, c = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a][b] = c
    graph[b][a] = c

graph_new = csgraph_from_dense(graph)
res = floyd_warshall(graph_new)
res = res[r_ls][:,r_ls]

memo_ls = [[None for i in range(R)] for j in range(2**R)]
def bit_dp(state, pos, cost):
    score = INF
    if state == 2**R - 1:
        memo_ls[state][pos] = cost
        return cost
    if memo_ls[state][pos] is not None:
        return memo_ls[state][pos]
    for next_t, next_c in enumerate(res[pos]):
        if next_c == 0:
            continue
        if (state >> next_t) & 1:
            continue
        score = min(score, bit_dp(state | 2**next_t, next_t, cost + next_c))
    memo_ls[state][pos] = score
    return score

best = INF
for i in range(R):
    memo_ls = [[None for i in range(R)] for j in range(2 ** R)]
    score = bit_dp(2**i, i, 0)
    best = min(score, best)
print(int(best))

Submission status: Wrong Answer

Solution code:
import sys
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall

n, m, R = [int(i) for i in sys.stdin.readline().split()]
r_ls = [int(i) - 1 for i in sys.stdin.readline().split()]
INF = 10**18
graph = [[0 for i in range(n)] for j in range(n)]
for i in range(m):
    a, b, c = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a][b] = c
    graph[b][a] = c

graph_new = csgraph_from_dense(graph)
res = floyd_warshall(graph_new)
res = res[r_ls][:,r_ls]

memo_ls = [[None for i in range(R)] for j in range(2**R)]
def bit_dp(state, pos, cost):
    score = INF
    if state == 2**R - 1:
        memo_ls[state][pos] = cost
        return cost
    if memo_ls[state][pos] is not None:
        return memo_ls[state][pos]
    for next_t, next_c in enumerate(res[pos]):
        if next_c == 0:
            continue
        if (state >> next_t) & 1:
            continue
        score = min(score, bit_dp(state | 2**next_t, next_t, cost + next_c))
    memo_ls[state][pos] = score
    return score

best = INF
for i in range(R):
    score = bit_dp(2**i, i, 0)
    best = min(score, best)
print(int(best))

Submission status: Wrong Answer

Solution code:
from itertools import permutations

def main():
    N, M, R = map(int, input().split())
    r = list(map(int, input().split()))
    d = [[0] * N for _ in range(N)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        A -= 1
        B -= 1
        d[A][B] = C
        d[B][A] = C
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

    ans = float('inf')
    for D in list(permutations(r)):
        tmp = 0
        for i in range(R-1):
            tmp += d[D[i]-1][D[i+1]-1]
        ans = min(ans, tmp)

    print(ans)



           



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:

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

INF = 200000 * 8
table = [[INF for _ in range(N)] for _ in range(N)]
for i in range(N):
    table[i][i] = 0

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

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
ss = set(r)
r.sort()
d = [[float("inf")] * (N + 1) for _ in range(N + 1)]
for i in range(N + 1):
  d[i][i] = 0
for _ in range(M):
  a, b, c = map(int, input().split())
  d[a][b] = c
  d[b][a] = c
res = float("inf")
for s in range(1, R + 1):
  if not (s in r): continue
  dp = [[float("inf")] * (pow(2, R)) for _ in range(N + 1)]
  if s in r:
    dp[s][1 << bl(r, s)] = 0
  else: continue
  for k in range(1, N + 1):
    for j in range(pow(2, R)):
      for i in range(1, N + 1):
        x = bl(r, k)
        if j & (1 << x):
          if k in ss:
            dp[k][j] = min(dp[k][j], dp[i][j] + d[i][k])
            continue
        #print(j, k, j + (1 << x))
        if k in ss:
          dp[k][j + (1 << x)] = min(dp[k][j + (1 << x)], dp[i][j] + d[i][k])
        else: dp[k][j] = min(dp[k][j], dp[i][j] + d[i][k])
  for k in range(1, N + 1):
    for j in range(pow(2, R)):
      for i in range(1, N + 1):
        x = bl(r, k)
        if j & (1 << x):
          if k in ss:
            dp[k][j] = min(dp[k][j], dp[i][j] + d[i][k])
            continue
        #print(j, k, j + (1 << x))
        if k in ss:
          dp[k][j + (1 << x)] = min(dp[k][j + (1 << x)], dp[i][j] + d[i][k])
        else: dp[k][j] = min(dp[k][j], dp[i][j] + d[i][k])
  for i in range(1, N + 1):
    res = min(res, dp[i][-1])
  #print(dp)
print(res)

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
ss = set(r)
r.sort()
d = [[float("inf")] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
  a, b, c = map(int, input().split())
  d[a][b] = c
  d[b][a] = c
res = float("inf")
for s in range(1, R + 1):
  if not (s in r): continue
  dp = [[float("inf")] * (pow(2, R)) for _ in range(N + 1)]
  if s in r:
    dp[s][1 << bl(r, s)] = 0
  else: continue
  for i in range(1, N + 1):
    for j in range(pow(2, R)):
      for k in range(1, N + 1):
        x = bl(r, k)
        if j & (1 << x):
          continue
        #print(j, k, j + (1 << x))
        if k in ss:
          dp[k][j + (1 << x)] = min(dp[k][j + (1 << x)], dp[i][j] + d[i][k])
        else: dp[k][j] = min(dp[k][j], dp[i][j] + d[i][k])
  for i in range(1, N + 1):
    res = min(res, dp[i][-1])
print(res)

Submission status: Wrong Answer

Solution code:
import sys, copy
from itertools import permutations

def wf(d):
  for k in range(N):
    for i in range(N):
      for j in range(N):
        d[i][j] = min(d[i][j],d[i][k]+d[k][j])
  return d

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

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

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

wf(d)

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

Submission status: Wrong Answer

Solution code:
from itertools import permutations

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    n=len(d[0])
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
    return d

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

#INF = float("inf")
route_list=[[10*9]*N for _ in range(N)]

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

wa_list=warshall_floyd(route_list)
ans=30**9

for perm in permutations(r):
    #print(perm)
    cur = sum(wa_list[v][u] for v, u in zip(perm, perm[1:]))
    ans = min(ans, cur)

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    n=len(d[0])
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
    return d

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

#INF = float("inf")
route_list=[[10*8]*N for _ in range(N)]

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

wa_list=warshall_floyd(route_list)
ans=30**9

for perm in permutations(r):
    #print(perm)
    cur = sum(wa_list[v][u] for v, u in zip(perm, perm[1:]))
    ans = min(ans, cur)

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    n=len(d[0])
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
    return d

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

#INF = float("inf")
route_list=[[0]*N for _ in range(N)]

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

wa_list=warshall_floyd(route_list)
ans=30**9

for perm in permutations(r):
    #print(perm)
    cur = sum(wa_list[v][u] for v, u in zip(perm, perm[1:]))
    ans = min(ans, cur)

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy
import sys
import itertools
input = sys.stdin.readline
inf = 200000000
n, m, r = map(int, input().split())
rs = list(map(int, input().split()))
n1 = n + 1
d = numpy.full((n1, n1), inf)
for i in range(n1):
    d[i, i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    d[a, b] = d[b, + a] = c


def update(k, i, j):
    d[i, j] = d[j, i] = min(
        d[i, j],
        d[i, k] + d[k, j])


[update(k, i, j) for k, i, j in itertools.product(range(1, n1), repeat=3)]
s = inf
for q in itertools.permutations(range(r)):
    t = 0
    for i in range(r-1):
        t += d[rs[q[i]], rs[q[i+1]]]
    if s > t:
        s = t
print(s)

Submission status: Wrong Answer

Solution code:
import numpy
import sys
import itertools
input = sys.stdin.readline
inf = 200000000
n, m, r = map(int, input().split())
rs = list(map(int, input().split()))
n1 = n + 1
d = numpy.full((n1, n1), inf)
for i in range(n1):
    d[i, i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    d[a, b] = d[b, + a] = c
for k, i, j in itertools.product(range(1, n1), repeat=3):
    d[i, j] = d[j, i] = min(
        d[i, j],
        d[i, k] + d[k, j])
s = inf
for q in itertools.permutations(range(r)):
    t = 0
    for i in range(r-1):
        t += d[rs[q[i]], rs[q[i+1]]]
    if s > t:
        s = t
print(s)

Submission status: Wrong Answer

Solution code:
import math
from itertools import permutations

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    n=len(d[0])
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

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

route_list=[[10*9]*N for i in range(N)]

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

wa_list=warshall_floyd(route_list)
ans=30**9

for perm in permutations(r):
    #print(perm)
    cur = sum(wa_list[v][u] for v, u in zip(perm, perm[1:]))
    ans = min(ans, cur)

print(ans)

Submission status: Wrong Answer

Solution code:
import math
from itertools import permutations

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    n=len(d[0])
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

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

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

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

wa_list=warshall_floyd(route_list)
ans=30**9

for perm in permutations(r):
    #print(perm)
    cur = sum(wa_list[v][u] for v, u in zip(perm, perm[1:]))
    ans = min(ans, cur)

print(ans)

Submission status: Wrong Answer

Solution code:
import math
from itertools import permutations

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    n=len(d[0])
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

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

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

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

wa_list=warshall_floyd(route_list)
ans=10**9

for perm in permutations(r):
    #print(perm)
    cur = sum(wa_list[v][u] for v, u in zip(perm, perm[1:]))
    ans = min(ans, cur)

print(ans)

Submission status: Wrong Answer

Solution code:
import math
from itertools import permutations

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    n=len(d[0])
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

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

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

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

wa_list=warshall_floyd(route_list)
ans=10**9

for perm in permutations(r):
    cur = sum(wa_list[v][u] for v, u in zip(perm, perm[1:]))
    ans = min(ans, cur)

print(ans)

Submission status: Wrong Answer

Solution code:
import math
from itertools import permutations

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    n=len(d[0])
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

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

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

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

wa_list=warshall_floyd(route_list)
ans=10**9

for perm in permutations(r):
    print(perm)
    cur = sum(wa_list[v][u] for v, u in zip(perm, perm[1:]))
    ans = min(ans, cur)

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra
import itertools
from scipy.sparse import csr_matrix
inf = 1 + 10**5
n, m, r = list(map(int, input().split()))
r = list(map(int, input().split()))
graph = np.full((n+1,n+1), inf)
for i in range(m):
    a,b,c = list(map(int, input().split()))
    graph[a][b] = c
    graph[b][a] = c
p_list = list(itertools.permutations(r,len(r)))
graph = dijkstra(csr_matrix(graph))
min_cost = inf * 200
for i in p_list:
    candidate = 0
    for j in range(len(i) - 1):
        candidate += graph[i[j]][i[j + 1]]
    if min_cost > candidate:
        min_cost = candidate
print(int(min_cost))

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra
import itertools
from scipy.sparse import csr_matrix
inf = 1 + 10**5
n, m, r = list(map(int, input().split()))
r = list(map(int, input().split()))
graph = np.full((n,n), inf)
for i in range(m):
    a,b,c = list(map(int, input().split()))
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c
p_list = list(itertools.permutations(r,len(r)))
graph = (dijkstra(csr_matrix(graph)))
min_cost = inf * 200
for i in p_list:
    candidate = 0
    for j in range(len(i) - 1):
        candidate += graph[i[j] - 1][i[j + 1] - 1]
    if min_cost > candidate:
        min_cost = candidate
print(int(min_cost))

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra
import itertools
from scipy.sparse import csr_matrix
inf = 1 + 10**5
n, m, r = list(map(int, input().split()))
r = list(map(int, input().split()))
graph = np.full((n,n), inf)
for i in range(m):
    a,b,c = list(map(int, input().split()))
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c
p_list = list(itertools.permutations(r,len(r)))
graph = (dijkstra(csr_matrix(graph)))
min_cost = inf * 8
for i in p_list:
    candidate = 0
    for j in range(len(i) - 1):
        candidate += graph[i[j]-1][i[j + 1] - 1]
    if min_cost > candidate:
        min_cost = candidate
print(int(min_cost))

Submission status: Wrong Answer

Solution code:
from itertools import*
n,m,r = map(int,input().split())
R = [int(i)-1 for i in input().split()]
cost = [[10**6]*n for i in range(n)]
ans = 10**9
for j in range(m):
  a,b,c = map(int,input().split())
  cost[a-1][b-1] = c
  cost[b-1][a-1] = c

for k in range(n):
    for i in range(n):
        for j in range(n):
            if cost[i][k] < 1000000 and cost[k][j] < 1000000:
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
for v in permutations(R):
  temp = 0
  for i in range(1,r):
    temp += cost[v[i-1]][v[i]]
  ans = min(ans,temp)
print(ans)

Submission status: Wrong Answer

Solution code:
def warshall_floyd(d,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])
    return d
    
n,m,r = map(int,input().split())
lstr = list(map(int,input().split()))

g = [[float("inf")]*n for _ in range(n)]
for i in range(m):
    a,b,c = map(int,input().split())
    g[a-1][b-1] = c
    g[b-1][a-1] = c

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

gg = warshall_floyd(g,n)

ans = 0
dist = 0
max_dist = 0
pos = lstr[0]-1

for i in range(1,r):
    dist = gg[pos][lstr[i] - 1]
    max_dist = max(max_dist,dist)
    ans += dist
    pos = lstr[i] - 1

dist = gg[lstr[-1]-1][lstr[0]-1]
ans += dist
max_dist = max(max_dist,dist)

print(ans - max_dist)

Submission status: Wrong Answer

Solution code:
from itertools import permutations

inf = 200 * (10 ** 5) + 10
n, m, r = map(int, input().split())  # 町数、道数、訪問地数
t = tuple(int(x) - 1 for x in input().split())  # 訪問地
g = [[inf] * n for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    g[a][b] = c
    g[b][a] = c

for k in range(n):
    for i in range(n):
        for j in range(n):
            g[i][j] = min(g[i][j], g[i][k] + g[k][j])

ans = inf
for p in permutations(t):
    ans = min(ans, sum(g[a][b] for a, b in zip(p, p[1:])))
print(ans)