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

Solution code:
import itertools
n, m, R = map(int, input().split())
r = list(map(int, input().split()))
INF = float("inf")
G = [[INF] * n for i 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][k] + G[k][j], G[i][j])

num = INF
for per in itertools.permutations(r):
    rec = 0
    pre = per[0] - 1
    for j in range(1, len(r)):
        rec += G[pre][per[j] - 1]
        pre = per[j] - 1

    num = min(rec, num)

print(num)

Submission status: Time Limit Exceeded

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 ls:
            x = G[i][k] + G[k][j]
            if x < G[i][j]:
                G[i][j] = G[j][i] = 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[R[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[pre][(1<<K) - 1])
print (ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
def Warshall_Floyd(edges,N):
  for k in range(N):
    for i in range(N):
      for j in range(N):
        edges[i][j]=min(edges[i][j],edges[i][k]+edges[k][j])
  return edges
n,m,r = map(int,input().split())
a = list(map(int,input().split()))
b = [list(map(int,input().split())) for l in range(m)]
d = [[float("inf")]*n for i in range(n)]
for i in range(m):
  d[b[i][0]-1][b[i][1]-1] = min(b[i][2],d[b[i][0]-1][b[i][1]-1])
  d[b[i][1]-1][b[i][0]-1] = min(b[i][2],d[b[i][1]-1][b[i][0]-1])
d = Warshall_Floyd(d,n)
kumi = list(itertools.permutations(a, r))
kota = float("inf")
for i in kumi:
  ans = 0
  for j in range(1,r):
    ans += d[i[j-1]-1][i[j]-1]
  kota = min(ans,kota)
print(kota)

Submission status: Time Limit Exceeded

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

fn = lambda: [int(x) for x in input().split()]
N, M, R = fn()
r = [int(ri) - 1 for ri in input().split()]
A, B, C = [0]*M, [0]*M, [0]*M
for i in range(M):
    A[i], B[i], C[i] = fn()
    A[i], B[i] = A[i] - 1, B[i] - 1

G = csr_matrix((C, (A, B)), shape=(N, N), dtype=float)
dist_matrix = G.todense()
dist_matrix[dist_matrix == 0] = float('inf')
dist_matrix.flat[::N + 1] = 0
for i in range(N):
    for j in range(i + 1, N):
        if dist_matrix[j, i] <= dist_matrix[i, j]:
            dist_matrix[i, j] = dist_matrix[j, i]
        else:
            dist_matrix[j, i] = dist_matrix[i, j]
for k in range(N):
    for i in range(N):
        if dist_matrix[i, k] == float('inf'):
            continue
        for j in range(N):
            d_ijk = dist_matrix[i, k] + dist_matrix[k, j]
            if d_ijk < dist_matrix[i, j]:
                dist_matrix[i, j] = d_ijk

D = dist_matrix

# D = floyd_warshall(G, directed=False)

routes = permutations(r)
result = float('inf')
for route in routes:
    d = sum([D[route[i], route[i+1]] for i in range(len(route) - 1)])
    result = min(result, d)
print(int(result))

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations, product

N, M, R = map(int, input().split())
r = [int(x) for x in input().split()]
abc = [[int(x) for x in input().split()] for _ in range(M)]

dist = [[float('inf') for _ in range(N)] for _ in range(N)]
for a, b, c in abc:
    dist[a - 1][b - 1] = c
    dist[b - 1][a - 1] = c

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

ans = float('inf')
for route in permutations(r):
    d = 0
    for i in range(R - 1):
        s = route[i] - 1
        g = route[i + 1] - 1
        d += dist[s][g]
    ans = min(ans, d)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N, M, R = map(int, raw_input().split())
r = [int(x)-1 for x in raw_input().split()]
D = []
for i in range(N):
  D.append([200000000]*N)
  D[i][i]=0
A = [0]*M
B = [0]*M
C = [0]*M
for i in range(M):
  a, b, C[i] = map(int, raw_input().split())
  A[i] = a-1
  B[i] = b-1
  D[A[i]][B[i]] = C[i]
  D[B[i]][A[i]] = C[i]
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])
ml = 2000000000
for p in itertools.permutations(r):
  l = 0
  for i in range(R-1):
    l += D[p[i]][p[i+1]]
  ml = min(ml, l)
print ml

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

inf = float("inf")
n,m,r = map(int,raw_input().split())
arr = map(int,raw_input().split())
d = [[inf for i in range(n)] for j in range(n)]

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

for i in range(m):
	f,t,c = map(int,raw_input().split())
	d[f-1][t-1] = c
	d[t-1][f-1] = c

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


ans = inf
for i in permutations(arr):
	distance = 0
	for j in range(r-1):
		distance += d[i[j]-1][i[j+1]-1]

	ans = min(ans,distance)

print ans

Submission status: Time Limit Exceeded

Solution code:
import itertools

inf = float("inf")
n,m,r = map(int,raw_input().split())
arr = map(int,raw_input().split())
d = [[inf for i in range(n)] for j in range(n)]

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

for i in range(m):
	f,t,c = map(int,raw_input().split())
	d[f-1][t-1] = c
	d[t-1][f-1] = c

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


per = list(itertools.permutations(range(r)))

ans = inf
for i in per:
	distance = 0
	for j in range(1,r):
		distance += d[arr[i[j-1]]-1][arr[i[j]]-1]

	ans = min(ans,distance)

print ans

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import*
from itertools import permutations as pm

n,m,h = map(int,input().split())
r = [int(i) for i in input().split()]

A = csr_matrix((n+1,n+1))
for i in range(m):
  u,v,l = map(int,input().split())
  A[u,v] = l

A=csgraph.dijkstra(A,0)

s=min(sum(A[i][j] for i,j in zip(a[:-1],a[1:])) for a in pm(r))
print(int(s))

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import*
from itertools import permutations as pm

n,m,h = map(int,input().split())
r = [int(i) for i in input().split()]

A = lil_matrix((n+1,n+1))
for i in range(m):
  u,v,l = map(int,input().split())
  A[u,v] = l

A=csgraph.dijkstra(A.tocsr(),0)

s=min(sum(A[i][j] for i,j in zip(a[:-1],a[1:])) for a in pm(r))
print(int(s))

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import*
from itertools import permutations as pm

n,m,h = map(int,input().split())
r = [int(i) for i in input().split()]

A = lil_matrix((n+1,n+1))
for i in range(m):
  u,v,l = map(int,input().split())
  A[u,v] = l

A=csgraph.dijkstra(A.tocsr(),0)

s=min(sum([A[i][j] for i,j in zip(a[:-1],a[1:])]) for a in pm(r))
print(int(s))

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import*
from itertools import permutations as pm

n,m,h = map(int,input().split())
r = [int(i) for i in input().split()]

A = lil_matrix((n+1,n+1))
for i in range(m):
  u,v,l = map(int,input().split())
  A[u,v] = l

A=csgraph.shortest_path(A.tocsr(),method='D',directed=False)

s=min(sum([A[i][j] for i,j in zip(a[:-1],a[1:])]) for a in pm(r))
print(int(s))

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import*
from itertools import permutations as pm

n,m,h = map(int,input().split())
r = [int(i) for i in input().split()]

A = lil_matrix((n+1,n+1))
for i in range(m):
  u,v,l = map(int,input().split())
  A[u,v] = l

A=csgraph.shortest_path(A,method='D',directed=False)

s=min(sum([A[i][j] for i,j in zip(a[:-1],a[1:])]) for a in pm(r))
print(int(s))

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import*
from itertools import permutations as pm

n,m,h = map(int,input().split())
r = [int(i) for i in input().split()]

A = lil_matrix((n+1,n+1))
for i in range(m):
  u,v,l = map(int,input().split())
  A[u,v] = l

A=csgraph.shortest_path(A,method='D',directed=False)
s=1e9
for a in pm(r):
  s=min(s,sum([A[i][j] for i,j in zip(a[:-1],a[1:])]))

print(int(s))

Submission status: Time Limit Exceeded

Solution code:
N,M,C=[int(x) for x in str(input()).split()]
r=[int(x) for x in str(input()).split()]
ABC=[[0 for i in range(4)]]

dis=[[100001 for i in range(N+1)]]

for i in range(N):
  dis.append([100001 for i in range(N+1)])


for i in range(M):
  x=[0]+[int(x) for x in str(input()).split()]
  ABC.append(x)
  dis[x[1]][x[2]]=x[3]
  dis[x[2]][x[1]]=x[3]
  y=[0,x[2],x[1],x[3]]
  ABC.append(y)

for i in range(1,N+1):
  dis[i][i]=0


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


mi=100000000000000
def perm(a,i):
  global mi
  if i==len(a):      

    p=0
    for x in range(len(a)-1):
      p+=dis[a[x]][a[x+1]]

    mi=min(mi,p)


  else:
    for j in range(i,len(a)):
      a[i],a[j]=a[j],a[i]
      perm(a,i+1)
      a[i],a[j]=a[j],a[i]


perm(r,0)

print(mi)

Submission status: Time Limit Exceeded

Solution code:
N,M,C=[int(x) for x in str(input()).split()]
r=[int(x) for x in str(input()).split()]
ABC=[[0 for i in range(4)]]

dis=[[100001 for i in range(N+1)]]

for i in range(N):
  dis.append([100001 for i in range(N+1)])


for i in range(M):
  x=[0]+[int(x) for x in str(input()).split()]
  ABC.append(x)
  dis[x[1]][x[2]]=x[3]
  dis[x[2]][x[1]]=x[3]
  y=[0,x[2],x[1],x[3]]
  ABC.append(y)

for i in range(1,N+1):
  dis[i][i]=0


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


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

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 k in range(1,N+1):
  for i in range(1,N+1):
    for j in range(1,N+1):
      dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j])

def permutList(l):
    if not l:
            return [[]]
    res = []
    for e in l:
            temp = l[:]
            temp.remove(e)
            res.extend([[e] + r for r in permutList(temp)])

    return res

N=permutList(r)

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

Submission status: Time Limit Exceeded

Solution code:
import heapq
from itertools import permutations

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

visit = list(map(int, input().split()))
g = [[float('inf')] * N for _ in range(N)]
for i in range(N):
    g[i][i] = 0

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

def dijkstra(start):
    c_l = [float('inf') for i in range(N)]
    c_l[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while len(q) != 0:
        prov_cost, src = heapq.heappop(q)  # pop
        if c_l[src] < prov_cost:
            continue
        for d in range(N):
            cost = g[src][d]
            if cost != float('inf') and c_l[d] > c_l[src] + cost:
                c_l[d] = c_l[src] + cost
                heapq.heappush(q, (c_l[d], d))
    else:
        return c_l


cost_list = []
for i in range(N):
    cost_list.append(dijkstra(i))

cost = float('inf')
for town in permutations(visit):
    c = 0
    for i in range(R - 1):
        c += cost_list[town[i] - 1][town[i + 1] - 1]
    cost = min(cost, c)
print(cost)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

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

visit = list(map(int, input().split()))
g = [[float('inf')] * N for _ in range(N)]
for i in range(N):
    g[i][i] = 0

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):
    for j in range(N):
        for k in range(N):
            g[i][j] = min(g[i][j], g[i][k] + g[k][j])

cost = float('inf')

for town in permutations(visit):
    c = 0
    for i in range(R - 1):
        c += g[town[i] - 1][town[i + 1] - 1]
    cost = min(cost, c)
print(cost)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

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

visit = list(map(int, input().split()))
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):
    for j in range(N):
        for k in range(N):
            g[i][j] = min(g[i][j], g[i][k] + g[k][j])

cost = float('inf')
visit = permutations(visit)
for town in visit:
    c = 0
    for i in range(len(town) - 1):
        c += g[town[i] - 1][town[i + 1] - 1]
    cost = min(cost, c)
print(cost)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

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

visit = list(map(int, input().split()))
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):
    for j in range(N):
        for k in range(N):
            g[i][j] = min(g[i][j], g[i][k] + g[k][j])

cost = float('inf')
visit = permutations(visit)
for town in visit:
    c = 0
    for i in range(len(town)-1):
        if g[town[i] - 1][town[i + 1] - 1] == float('inf'):
            break
        else:
            c += g[town[i] - 1][town[i + 1] - 1]
    else:
        cost = min(cost, c)
print(cost)

Submission status: Time Limit Exceeded

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[j][k] = min(D[j][k], D[j][i] + D[i][k])

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

Solution code:
import itertools

n,m,R = map(int,input().split())
r = list(map(int,input().split()))
data = []
for i in range(0,m):
    a,b,c = map(int,input().split())
    data.append((a,b,c))
    data.append((b,a,c))

d = [[] for _ in range(0,R)]

def bellmanFord(start,num):
    g = [float("inf") for _ in range(0,n+1)]
    g[start] = 0
    for i in range(0,n):
        for j in range(0,m*2):
            a,b,c = data[j]
            if g[a] != float("inf") and g[b] > g[a] + c:
                g[b] = g[a] + c
    for i in range(0,R):
        d[num].append(g[r[i]])

for i in range(0,R):
    bellmanFord(r[i],i)
    # print(d[i])
ans = float("inf")
seq = itertools.permutations([i for i in range(0,R)])
for i in seq:
    dis = 0
    for j in range(0,len(i)-1):
        dis += d[i[j]][i[j+1]]
    if ans > dis:
        ans = dis
print(ans)

Submission status: Time Limit Exceeded

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

from collections import defaultdict
from itertools import permutations

INF = 10**10

D = defaultdict(lambda:INF)

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

result = INF

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

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

Solution code:
N, M, Rs = map(int, input().split())
R = list(map(int, input().split()))
D = [[float("inf")] * (N+1) for i in range(N+1)]
for i in range(M):
    a, b, c = map(int, input().split())
    D[a][b] = D[b][a] = c

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


def full(L):
    if len(L) == 1:
        return [L]
    else:
        L2 = []
        for i in range(len(L)):
            L2.extend([[L[i]] + Lc for Lc in full(L[:i] + L[i+1:])])
        return L2


L = full(R)
ans = float("inf")
for l in L:
    a = 0
    for i in range(Rs-1):
        a += D[l[i]][l[i+1]]
    ans = min(ans, a)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
A = []
B = []
C = []
D = [[] for _ in range(N)]
inf = float("inf")
for i in range(N):
    for j in range(N):
        if i == j:
            D[i].append(0)
        else:
            D[i].append(inf)


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


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


p = list(permutations(r))
D = WarshallFloyd(D, N)
Min = inf
for e in p:
    s = 0
    for i in range(R - 1):
        s += D[e[i] - 1][e[i + 1] - 1]
        if s > Min:
            break
    Min = min(s, Min)

print(Min)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
A = []
B = []
C = []
D = [[] for _ in range(N)]
inf = float("inf")
for i in range(N):
    for j in range(N):
        if i == j:
            D[i].append(0)
        else:
            D[i].append(inf)


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


def WarshallFloyd(D):
    """
    >>> WarshallFloyd([[0, 1, 4], [1, 0, 1], [4, 1, 0]])
    [[0, 1, 2], [1, 0, 1], [2, 1, 0]]
    """
    for k in range(len(D)):
        for i in range(len(D)):
            for j in range(i, len(D)):
                D[i][j] = min(D[i][j], D[i][k] + D[k][j])
                D[j][i] = D[i][j]
    return D


D = WarshallFloyd(D)
Min = inf
for e in permutations(r):
    s = 0
    for i in range(R - 1):
        s += D[e[i] - 1][e[i + 1] - 1]
        if s > Min:
            break
    Min = min(s, Min)

print(Min)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
A = []
B = []
C = []
D = [[] for _ in range(N)]
inf = float("inf")
for i in range(N):
    for j in range(N):
        if i == j:
            D[i].append(0)
        else:
            D[i].append(inf)


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


def WarshallFloyd(D):
    """
    >>> WarshallFloyd([[0, 1, 4], [1, 0, 1], [4, 1, 0]])
    [[0, 1, 2], [1, 0, 1], [2, 1, 0]]
    """
    for k in range(len(D)):
        for i in range(len(D)):
            for j in range(len(D)):
                D[i][j] = min(D[i][j], D[i][k] + D[k][j])
    return D


D = WarshallFloyd(D)
Min = inf
for e in permutations(r):
    s = 0
    for i in range(R - 1):
        s += D[e[i] - 1][e[i + 1] - 1]
    Min = min(s, Min)

print(Min)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
N,M,R=map(int,input().split())
r = [int(i) for i in input().split()]
inf=10**10
#[k][j][i]
dp=[[[inf]*N for i in range(N)]for i in range(N+1)]
for i in range(M):
    a,b,c=map(int,input().split())
    dp[0][a-1][b-1]=c
    dp[0][b-1][a-1]=c
for k in range(1,N+1):
    for j in range(N):
        for i in range(N):
            dp[k][j][i]=min(dp[k-1][j][i],dp[k-1][j][k-1]+dp[k-1][k-1][i])

ans =inf
for elem in permutations(r, R):
    dis=0
    for i in range(R-1):
        dis+=dp[N][elem[i+1]-1][elem[i]-1]
    ans=min(ans,dis)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools

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

ROAD=[None]*M

for i in range(M):
    ROAD[i]=list(map(int,input().split()))


Dis=np.full((N+1,N+1),float("inf"))

for i in range(M):
    Dis[ROAD[i][0]][ROAD[i][1]]=ROAD[i][2]
    Dis[ROAD[i][1]][ROAD[i][0]]=ROAD[i][2]




#ワーシャル–フロイド法を使って最短距離Disを求める

for k in range(1,N+1):#k個までの町を使ってのDisが知れているときに
    for i in range(1,N+1):#町iと
        for j in range(1,N+1):#町jとの最短距離は、
            if Dis[i][j]>Dis[i][k]+Dis[j][k]:
                Dis[i][j]=Dis[i][k]+Dis[j][k]
    
PERM=list(itertools.permutations(r))

ANS=float("inf")
for i in range(len(PERM)):
    DIST=0
    for k in range(1,R):
        DIST+=Dis[PERM[i][k]][PERM[i][k-1]]
        if DIST>ANS:
            break
    if ANS>DIST:
        ANS=DIST


print(int(ANS))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

ROAD=[None]*M

for i in range(M):
    ROAD[i]=list(map(int,input().split()))


Dis=np.full((N+1,N+1),float("inf"))

for i in range(M):
    Dis[ROAD[i][0]][ROAD[i][1]]=ROAD[i][2]
    Dis[ROAD[i][1]][ROAD[i][0]]=ROAD[i][2]




#ワーシャル–フロイド法を使って最短距離Disを求める

for k in range(1,N+1):#k個までの町を使ってのDisが知れているときに
    for i in range(1,N+1):#町iと
        for j in range(1,N+1):#町jとの最短距離は、
            Dis[i][j]=min(Dis[i][j],Dis[i][k]+Dis[j][k])
    
        
import itertools
    
PERM=list(itertools.permutations(r,R))

ANS=float("inf")
for i in range(len(PERM)):
    DIST=0
    for k in range(1,R):
        DIST+=Dis[PERM[i][k]][PERM[i][k-1]]
        if DIST>ANS:
            break
    ANS=min(ANS,DIST)


print(int(ANS))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

ROAD=[None]*M

for i in range(M):
    ROAD[i]=list(map(int,input().split()))



Dis=[None]*(N+1)

for i in range(N+1):
    Dis[i]=[float("inf")]*(N+1)

for i in range(M):
    Dis[ROAD[i][0]][ROAD[i][1]]=ROAD[i][2]
    Dis[ROAD[i][1]][ROAD[i][0]]=ROAD[i][2]


#ワーシャル–フロイド法を使って最短距離Disを求める

for k in range(1,N+1):#k個までの町を使ってのDisが知れているときに
    for i in range(1,N+1):#町iと
        for j in range(1,N+1):#町jとの最短距離は、
            Dis[i][j]=min(Dis[i][j],Dis[i][k]+Dis[j][k])
    
        
import itertools
    
PERM=list(itertools.permutations(r,R))

ANS=10**8
for i in range(len(PERM)):
    DIST=0
    for k in range(1,R):
        DIST+=Dis[PERM[i][k]][PERM[i][k-1]]
        if DIST>ANS:
            break
    ANS=min(ANS,DIST)


print(ANS)

Submission status: Time Limit Exceeded

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

ROAD=[None]*M

for i in range(M):
    ROAD[i]=list(map(int,input().split()))



Dis=[10**8]*(N+1)

for i in range(N+1):
    Dis[i]=[10**8]*(N+1)

for i in range(M):
    Dis[ROAD[i][0]][ROAD[i][1]]=ROAD[i][2]
    Dis[ROAD[i][1]][ROAD[i][0]]=ROAD[i][2]


#ワーシャル–フロイド法を使って最短距離Disを求める

for k in range(1,N+1):#k個までの町を使ってのDisが知れているときに
    for i in range(1,N+1):#町iと
        for j in range(1,N+1):#町jとの最短距離は、
            Dis[i][j]=min(Dis[i][j],Dis[i][k]+Dis[j][k])
    
        
import itertools
    
PERM=list(itertools.permutations(r,R))

ANS=10**8
for i in range(len(PERM)):
    DIST=0
    for k in range(1,R):
        DIST+=Dis[PERM[i][k]][PERM[i][k-1]]
    ANS=min(ANS,DIST)


print(ANS)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
A = [0] * M
B = [0] * M
C = [0] * M
for i in range(M):
	A[i], B[i], C[i] = map(int, input().split())

d = [[float("inf") for _ in range(N)] for _ in range(N)]

for i in range(M):
	d[A[i] - 1][B[i] - 1] = C[i]
	d[B[i] - 1][A[i] - 1] = C[i]

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]

p = permutations(r)
ans = float("inf")
for route in p:
	l = 0
	for i in range(R - 1):
		l += d[route[i] - 1][route[i + 1] - 1]

	if l < ans:
		ans = l

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
A = [0] * M
B = [0] * M
C = [0] * M
for i in range(M):
	A[i], B[i], C[i] = map(int, input().split())

d = [[float("inf") for _ in range(N)] for _ in range(N)]

for i in range(M):
	d[A[i] - 1][B[i] - 1] = C[i]
	d[B[i] - 1][A[i] - 1] = C[i]

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]
				d[j][i] = d[i][k] + d[k][j]

p = permutations(r)
ans = float("inf")
for route in p:
	l = 0
	for i in range(R - 1):
		l += d[route[i] - 1][route[i + 1] - 1]

	if l < ans:
		ans = l

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

def hoge():
  N, M, R = map(int, input().split())
  r = map(int, input().split())
  r = [x - 1 for x in r]
  inf = 1e18
  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())
      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):
              t = d[i][k] + d[k][j]
              d[i][j] = min(d[i][j], t)


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

  print(ans)
hoge()

Submission status: Time Limit Exceeded

Solution code:
def hoge():
  from itertools import permutations
  N, M, R = map(int, input().split())
  r = map(int, input().split())
  inf = 1e18
  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
      t = min(c, d[a][b])
      if d[a][b] > c:
          d[a][b], d[b][a] = t, t


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


  ans = inf
  for 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)
hoge()

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

def hoge():
  N, M, R = map(int, input().split())
  r = map(int, input().split())
  r = [x - 1 for x in r]
  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())
      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):
              t = d[i][k] + d[k][j]
              d[i][j] = min(d[i][j], t)


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

  print(ans)
hoge()

Submission status: Time Limit Exceeded

Solution code:
def hoge():
  from itertools import permutations
  N, M, R = map(int, input().split())
  r = map(int, input().split())
  r = [x - 1 for x in r]
  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())
      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):
              t = d[i][k] + d[k][j]
              d[i][j] = min(d[i][j], t)


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

  print(ans)
hoge()