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: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

import numpy as np

N,M,R = map(int, input().split())
r = list(map(int, input().split()))
ds = np.zeros([N,N])
neighbors = [[]]*N
for _ in range(M):
    a,b,c = map(int, input().split())
    ds[a-1][b-1] = c
    ds[b-1][a-1] = c
    neighbors[a-1].append(b-1)
    neighbors[b-1].append(a-1)
visitedls = []
totalds = 0
minds = 1e9+7

def dfs(a, prev):
    global visitedls, totalds, ds, minds, neighbors, r
    visitedls.append(a+1)
    totalds += ds[a][prev]
    if set(r) & set(visitedls) == set(r):
        if minds > totalds:
                minds = totalds  
    for nxt in neighbors[a]:
        if nxt+1 not in visitedls:
            dfs(nxt, a)
    del visitedls[-1]
    totalds -= ds[a][prev]

for a in r:
    dfs(a-1, a-1)
print(int(minds))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

import numpy as np

N,M,R = map(int, input().split())
r = list(map(int, input().split()))
ds = np.zeros([N,N])
neighbors = [[]]*N
for _ in range(M):
    a,b,c = map(int, input().split())
    ds[a-1][b-1] = c
    ds[b-1][a-1] = c
    neighbors[a-1].append(b-1)
    neighbors[b-1].append(a-1)
visitedls = []
totalds = 0
minds = 1e9+7

def dfs(a, prev):
    global visitedls, totalds, ds, minds, neighbors, r
    visitedls.append(a+1)
    totalds += ds[a][prev]
    if set(r) & set(visitedls) == set(r):
        if minds > totalds:
                minds = totalds  
    for nxt in neighbors[a]:
        if nxt+1 not in visitedls:
            dfs(nxt, a)
    del visitedls[-1]
    totalds -= ds[a][prev]

def main():
    for a in r:
        dfs(a-1, a-1)
    print(int(minds))
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n,m,r = map(int,input().split())
rl = list(map(int,input().split()))

d = [[float("inf") for i in range(n)] for j 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


#d[i][j]は2頂点間i, j間の移動コストを格納, Vは頂点数
def warshall_floyd(d, V): 
    for k in range(V):
        for i in range(V):
            for j in range(V):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

    return d #d[i][j]に頂点i, j間の最短距離を格納

d = warshall_floyd(d, n)
import itertools
ans = float("inf")
for balls in itertools.permutations(rl):
    a = 0
    for i in range(r-1):
        a += d[balls[i]-1][balls[i+1]-1]
    ans = min(ans, a)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

N, M, R = list(map(int, input().split()))
r = list(map(int, input().split()))
INF=10**30
D = [[INF]*(N+1) for _ in range(N+1)]

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

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

ans = INF
for path in permutations(r):
    length = 0
    for i in range(R-1):
        length += D[path[i]][path[i+1]]
    ans = min(ans, length)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

N, M, R = list(map(int, input().split()))
r = list(map(int, input().split()))
INF=10**30
D = [[INF]*(N+1) for _ in range(N+1)]

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

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

ans = INF
for path in permutations(r):
    length = 0
    for i in range(R-1):
        length += D[path[i]][path[i+1]]
    ans = min(ans, length)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# ABC073d
import sys
import itertools
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n, m, _ = map(int, input().split())
d = [[float("inf") for i in range(n)] for i in range(n)]
for i in range(n):
    d[i][i] = 0  # 自身のところに行くコストは０
r = list(map(int, input().split()))


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


for _ in range(m):
    a, b, c = map(int, input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
warshall_floyd(d)

ans = 10**9
for i in itertools.permutations(r, len(r)):
    t = 0
    for j in range(1, len(i)):
        t += d[i[j]-1][i[j-1]-1]
    #print(i, t)
    ans = min(ans, t)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N,M,R = map(int,input().split())
r = list(map(int,input().split()))
L = []
ans = float('inf')
for i in range(M):
    L.append(list(map(int,input().split())))
cost = []
for i in range(N):
    T = [float('inf') for j in range(N)]
    cost.append(T)
for i in range(M):
    cost[L[i][0]-1][L[i][1]-1] = L[i][2]
    cost[L[i][1]-1][L[i][0]-1] = L[i][2]
for l in range(N):
    for k in range(N):
        for m in range(N):
            cost[k][m] = min(cost[k][l]+cost[l][m], cost[k][m])

junretu = list(itertools.permutations(r))
for i in range(len(junretu)):
    temp = 0
    for j in range(len(r)-1):
        c = junretu[i][j]
        d = junretu[i][j+1]
        temp += cost[c-1][d-1]
    ans = min(ans,temp)
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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, N + 1):
  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: Time Limit Exceeded

Solution code:
def warshall_floyd(cost, num_v):
    """
    ワーシャルフロイド法
    :param cost: 隣接行列
    :param num_v: 頂点数
    :return: 各頂点からの最短距離
    """
    for k in range(num_v):
        for i in range(num_v):
            for j in range(num_v):
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
    return cost


import itertools


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

    cost = warshall_floyd(cost, n)
    ans = inf
    for permutation in itertools.permutations(r):
        c = 0
        b = permutation[0]
        for i in permutation[1:]:
            c += cost[b - 1][i - 1]
            b = i
        ans = min(ans, c)
    print(ans)


if __name__ == '__main__':
    abc073_d()

Submission status: Time Limit Exceeded

Solution code:
import itertools

n,m,R=map(int,input().split())
r=list(map(int,input().split()))
INF = 10**10
d=[[INF for i in range(n)] for i in range(n)]

for i in range(m):
    a,b,c=map(int,input().split())
    d[a-1][b-1]=c
    d[b-1][a-1]=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])

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

res = INF
for rp in itertools.permutations(r):
    tres = 0
    for i in range(R-1):
        tres += d[rp[i]][rp[i+1]]
    res = min(res,tres)

print(res)

Submission status: Time Limit Exceeded

Solution code:
#73d
import itertools

N,M,R = map(int, input().split())
r_list = [int(e) for e in input().split()] #lenは8以下 ∴NPだけど解ける

INF = 100000*200 

#無限で初期化
distance_list = [[INF] * (N+1) for i in range(N+1)]

#距離の表をinput
for _ in range(0,M):
    A,B,C = map(int, input().split())
    
    #from-toが共通している辺があれば短いのを優先
    if C < distance_list[A][B]:
        distance_list[A][B] = C
        distance_list[B][A] = C
        
#from-toがともに自分ならコスト0
for i in range(1,N+1):
    distance_list[i][i] = 0

#入力結果を表示
#for i in range(1,N+1):
#    print(distance_list[i][1:])
#print("#####################################")
    
#ワーシャルフロイド法を使って、すべての町間の移動距離を算出　200*199/2 = 1990通り 200**3 = 8000000 ≒　8 * 10**6
for i in range(1,N+1):
    for j in range(1,N+1):
        for k in range(1,N+1):
            distance_list[i][j] = min(distance_list[i][j],distance_list[i][k] + distance_list[k][j])

#for i in range(1,N+1):
#    print(distance_list[i][1:])

#print("#####################################")
    
#訪問する都市の並び方を全て列挙　8! = 40320 双方向移動可能なので、逆方向は同じ　∴/2して20160通り
#直で行くより迂回したほうが近い可能性があるので注意
visit_list = itertools.permutations(r_list)
ans_all = INF

for visit in visit_list:
    #print(visit,":",end="")
    ans_visit = 0
    
    for i in range(1,len(visit)):
        town_from = visit[i]
        town_to = visit[i-1]
        ans_visit += distance_list[town_from][town_to]
    
    #print(ans_visit)
    
    if ans_visit < ans_all:
        ans_all = ans_visit
        
print(ans_all)

Submission status: Time Limit Exceeded

Solution code:
import sys, copy

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)

from collections import deque

ans = float('inf')
for start_i in Rs:
  q = deque()
  q.append([start_i-1,0,set([start_i-1])])
  while len(q) > 0:
    prv_node, prv_cost, done = q.pop()

    min_cost = float('inf')
    min_nodes = []
    for r in Rs:
      r -= 1
      if r in done: continue
      if min_cost > d[prv_node][r]:
        min_cost = d[prv_node][r]
        min_nodes = [r]
      elif min_cost == d[prv_node][r]:
        min_cost = d[prv_node][r]
        min_nodes.append(r)
    
    for node in min_nodes:   
      tmp_done = copy.deepcopy(done)
      tmp_done.add(node)
      if len(tmp_done) == R:
        if ans > prv_cost+min_cost: ans = prv_cost+min_cost
      else: q.append([node, prv_cost+min_cost, tmp_done])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
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,input().split())
  d[a-1][b-1] = c
  d[b-1][a-1] = c

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

wf(d)

from collections import deque

ans = float('inf')
for start_i in Rs:
  q = deque()
  q.append([start_i-1,0,[start_i-1]])
  while len(q) > 0:
    prv_node, prv_cost, done = q.pop()

    min_cost = float('inf')
    min_nodes = []
    for r in Rs:
      r -= 1
      if r in done: continue
      if min_cost > d[prv_node][r]:
        min_cost = d[prv_node][r]
        min_nodes = [r]
      elif min_cost == d[prv_node][r]:
        min_cost = d[prv_node][r]
        min_nodes.append(r)
    
    for node in min_nodes:      
      if len(done)+1 == R:
        if ans > prv_cost+min_cost: ans = prv_cost+min_cost
      else: q.append([node, prv_cost+min_cost, done+[node]])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,m,r=map(int,input().split())
rr=list(map(int,input().split()))
inf=10000000000
g=[[inf for i in range(n)] for j 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 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=10**10
for i in itertools.permutations(range(0,r),r):
    kai=0
    for j in range(r-1):
        kai+=g[rr[i[j]]-1][rr[i[j+1]]-1]
    ans=min(ans,kai)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline

n,m,r=map(int,input().split())
iku=list(map(int,input().split()))
iku=list(map(lambda x:x-1,iku))
iku="".join(list(map(str,iku)))

g=[[float("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 i in range(n):
    g[i][i]=0

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

from itertools import permutations
x=list(permutations(iku,len(iku)))
ans=float("inf")
for l in x:
    ans2=0
    for i in range(1,r):
        ans2+=g[int(l[i-1])][int(l[i])]
    ans=min(ans,ans2)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
import numpy


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] = numpy.minimum(d[i][j], d[i][k] + d[k][j])
    return d


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

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

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

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

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

print(int(ans))

Submission status: Time Limit Exceeded

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):
              s = d[i][k] + d[k][j]
              d[i][j] = min(d[i][j],s)
    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: Time Limit Exceeded

Solution code:
from itertools import permutations


def warshall_floyd(d):
    m = min
    #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] = m(d[i][j], d[i][k] + d[k][j])
    return d


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

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

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

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations


def warshall_floyd(d):
    global range, min
    #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()]

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

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

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

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

print(ans)

Submission status: Time Limit Exceeded

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):
              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()]
 
#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: Time Limit Exceeded

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):
                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()]

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

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

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
from itertools import permutations
import numpy as np
#from scipy.sparse import*
 
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)]
route_list = np.full((N,N),10**8,dtype=np.int)
 
 
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: Time Limit Exceeded

Solution code:
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 = [inf] * (n1 * n1)
for i in range(n1):
    d[i * n1 + i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    d[a * n1 + b] = d[b * n1 + a] = c
for k, i, j in itertools.product(range(1, n1), repeat=3):
    d[i * n1 + j] = d[j * n1 + i] = min(
        d[i * n1 + j],
        d[i * n1 + k] + d[k * n1 + j])
s = inf
for q in itertools.permutations(range(r)):
    t = 0
    for i in range(r-1):
        t += d[rs[q[i]] * n1 + rs[q[i+1]]]
    if s > t:
        s = t
print(s)

Submission status: Time Limit Exceeded

Solution code:
import math
from itertools import permutations
import numpy as np
#from scipy.sparse import*

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)]
route_list = np.full((N,N),10**8,dtype=np.int)


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: Time Limit Exceeded

Solution code:
from scipy.sparse import *
from itertools import *
 
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(i)-1 for i in input().split()]
route_list = [[0]*n for i in range(n)]
ans = 10**7
for j in range(m):
  a,b,c = map(int,input().split())
  route_list[a-1][b-1] = c
  route_list[b-1][a-1] = c
 
#Co = csgraph.floyd_warshall(csr_matrix(route_list))
Co = warshall_floyd(route_list)
  
for v in permutations(R):
  temp = 0
  for i in range(1,r):
    temp += Co[v[i-1]][v[i]]
  ans = min(ans,temp)
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import *
from itertools import *
 
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(i)-1 for i in input().split()]
route_list = [[0]*n for i in range(n)]
ans = 10**9
for j in range(m):
  a,b,c = map(int,input().split())
  route_list[a-1][b-1] = c
  route_list[b-1][a-1] = c
 
#Co = csgraph.floyd_warshall(csr_matrix(route_list))
Co = warshall_floyd(route_list)
  
for v in permutations(R):
  temp = 0
  for i in range(1,r):
    temp += Co[v[i-1]][v[i]]
  ans = min(ans,temp)
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
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 = [inf] * (n1 * n1)
for i in range(n1):
    d[i * n1 + i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    d[a * n1 + b] = d[b * n1 + a] = c
for k in range(1, n+1):
    for i in range(1, n+1):
        d = d
        for j in range(i+1, n+1):
            d[i * n1 + j] = d[j * n1 + i] = min(
                d[i * n1 + j],
                d[i * n1 + k] + d[k * n1 + j])
s = inf
for q in itertools.permutations(range(r)):
    t = 0
    for i in range(r-1):
        t += d[rs[q[i]] * n1 + rs[q[i+1]]]
    if s > t:
        s = t
print(s)

Submission status: Time Limit Exceeded

Solution code:
import math
from itertools import permutations
#from scipy.sparse import*

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: Time Limit Exceeded

Solution code:
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 = [inf] * (n1 * n1)
for i in range(n1):
    d[i * n1 + i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    d[a * n1 + b] = d[b * n1 + a] = c


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


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

Submission status: Time Limit Exceeded

Solution code:
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 = [inf] * (n1 * n1)
for i in range(n1):
    d[i * n1 + i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    d[a * n1 + b] = d[b * n1 + a] = c


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


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

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
input = sys.stdin.readline
inf = 200000000
n, m, r = map(int, input().split())
rs = list(map(int, input().split()))
d = [[inf] * (n+1) for j in range(n+1)]
for i in range(n+1):
    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(i, j, k):
    d[i][j] = d[j][i] = min(d[i][j], d[i][k] + d[k][j])


[update(i, j, k) for k in range(1, n+1)
 for i in range(1, n+1) for j in range(i+1, n+1)]
p = list(itertools.permutations(range(r)))
s = inf
for q in p:
    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: Time Limit Exceeded

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)