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:
n,m,R = map(int,input().split())
r = list(map(int,input().split()))
INF = 10**10
d = [[INF for i in range(n)] for j 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])

from itertools import permutations

ans = INF
for v in permutations(r,R):
    dis = 0
    for i in range(R-1):
        dis += d[v[i]-1][v[i+1]-1]
    ans = min(ans,dis)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

from itertools import permutations

HUGE = 10 ** 18

def main():
    n, m, r = map(int, input().split())
    togo = list(map(int, input().split()))
    adj_mat = [[HUGE for j in range(n)] for i in range(n)]
    for i in range(n):
        adj_mat[i][i] = HUGE
    for i in range(m):
        a, b, c = map(int, input().split())
        a0 = a - 1
        b0 = b - 1
        adj_mat[a0][b0] = c
        adj_mat[b0][a0] = c

    # Warshall-Floyd
    for k in range(n):
        for i in range(n):
            for j in range(n):
                adj_mat[i][j] = min(adj_mat[i][j], adj_mat[i][k] + adj_mat[k][j])

    res = HUGE
    for way in permutations(togo):
        assert len(way) > 1
        x = 0
        for i in range(len(way) - 1):
            x += adj_mat[way[i] - 1][way[i + 1] - 1]
        res = min(res, x)

    print(res)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

n,m,r=map(int,input().split())
D=[[10**10]*n for _ in range(n)]
for i in range(n):
    D[i][i]=0
R=list(map(int,input().split()))
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])

A=[]
for v in itertools.permutations(R,r):
    ans=0
    for i in range(r-1):
        ans+=D[v[i]-1][v[i+1]-1]
    A.append(ans)
print(min(A))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3r
# -*- coding:utf-8 -*-

from itertools import permutations

def main():
  n, m, nr = map(int, input().split())
  lr = list(map(lambda x:int(x)-1, input().split()))
  edges = [[10**9]*n for _ in range(n)]
  for i in range(n):
    edges[i][i] = 0
  for _ in range(m):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    edges[a][b] = edges[b][a] = c
    
  def wf():
    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])
  wf()
          
  def calc_cost(path):
    cost = 0
    for i in range(nr-1):
      cost += edges[path[i]][path[i+1]]
    return cost
  
  print(min([calc_cost(path) for path in permutations(lr)]))

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
import sys

N, M, R = map(int, input().split())
r = [int(i) for i in input().split()]
r.sort()
a = [[sys.maxsize] * N for i in range(N)]
for i in range(M):
	A, B, C = map(int, input().split())
	a[A - 1][B - 1] = C
	a[B - 1][A - 1] = C
for i in range(N):
	a[i][i] = 0
for i in range(N):
	for j in range(N):
		if a[j][i] == sys.maxsize:
			continue
		for k in range(N):
			if a[i][k] == sys.maxsize:
				continue
			a[j][k] = min(a[i][k] + a[j][i], a[j][k])
ans = sys.maxsize
for i in itertools.permutations(r):
	b, j = 0, 1
	while j < R:
		b += a[i[j - 1] - 1][i[j] - 1]
		j += 1
	ans = min(b, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools as it
n,m,r= map(int,input().split())
rl = list(map(int,input().split()))
rg = [[999999999 for _ in range(n)] for _ in range(n)]
for i in range(m):
    a,b,c= map(int,input().split())
    rg[a-1][b-1] = c
    rg[b-1][a-1] = c

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

cpm = it.permutations(rl, r)
gmin = 999999999
for c in cpm:
    l = list(c)
    g = 0
    for i in range(len(l)-1):g += rg[l[i]-1][l[i+1]-1]
    gmin = min(gmin,g)
print(gmin)

Submission status: Time Limit Exceeded

Solution code:
N, M, R = map(int, input().split())
d = [[int(1e18) for __ in range(N)] for _ in range(N)]
r = list(map(int, input().split()))
for i in range(R):
  r[i] -= 1
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):
      if d[i][j] > d[i][k] + d[k][j]:
        d[i][j] = d[i][k] + d[k][j]
fact = 1
for i in range(R):
  fact *= i + 1
M = int(1e18)
for i in range(fact):
  perm = [_ for _ in range(R)]
  L = []
  tmp = i
  time = 0
  for j in range(R):
    L = [tmp%(j+1)] + L[:]
    tmp //= j + 1
  LL = []
  for j in range(R):
    LL.append(perm[L[j]])
    del perm[L[j]]
  for j in range(R-1):
    tmp += d[r[LL[j]]][r[LL[j+1]]]
  if tmp < M:
    M = tmp
print(M)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import itertools
n, m, r = map(int, input().split())
r = list(map(lambda x:int(x)-1, input().split()))
d = [[float('inf')]*n for _ in range(n)]
for _ in range(m):
  a, b, t = map(int, input().split())
  a -= 1
  b -= 1
  d[a][b] = t
  d[b][a] = t
for i in range(n):
  d[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  

d = warshall_floyd(d)

ans = float('inf')
for v in itertools.permutations(r):
  tmp = 0
  for i in range(len(v)-1):
    tmp += d[v[i]][v[i+1]]
  ans = min(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import itertools
n, m, r = map(int, input().split())
r = list(map(lambda x:int(x)-1, input().split()))
graph = [[] for _ in range(n)]
for _ in range(m):
  a, b, c = map(int, input().split())
  a -= 1
  b -= 1 
  graph[a] += [[b, c]]
  graph[b] += [[a, c]]

def dijkstra(s):
  dist = [float('inf')]*n
  dist[s] = 0
  q = [[0, s]]
  heapq.heapify(q)
  while q:
    c, u = heapq.heappop(q)
    if dist[u] < c:
      continue
    for v, weight in graph[u]:
      if dist[v] > dist[u] + weight:
        dist[v] = dist[u] + weight
        heapq.heappush(q, [dist[v], v])
  return dist

ans = float('inf')
for v in itertools.permutations(r):
  tmp = 0
  for i in range(len(v)-1):
    tmp += dijkstra(v[i])[v[i+1]]
  ans = min(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
r = [x - 1 for x in r]
d = [[float("inf")] * N for i 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


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(d)
# print(d)
ans = float('inf')
for x in itertools.permutations(r):
    cost = 0
    # print(x)
    for i in range(len(x) - 1):
        # print(i)
        cost += d[x[i]][x[i+1]]
    ans = min(ans, cost)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
X = [[998244353 for i in range(N)] for j in range(N)]
Y = [[[] for i in range(N)] for j in range(N)]
for i in range(R):
  r[i] -= 1
D = {r[i]: i for i in range(R)}
for i in range(M):
  A, B, C = map(int, input().split())
  X[A-1][B-1] = C
  X[B-1][A-1] = C
  Y[A-1][B-1] = [A-1, B-1]
  Y[B-1][A-1] = [B-1, A-1]
for k in range(N):
  for i in range(N):
    for j in range(N):
      if X[i][j] > X[i][k] + X[k][j]:
        X[i][j] = X[i][k] + X[k][j]
        Y[i][j] = Y[i][k][:] + Y[k][j][1:]
fact = 1
for i in range(R):
  fact *= i + 1
M = int(1e18)
tgt = [1 for _ in range(R)]
if R > 2:
  for i in range(fact):
    perm = [i for i in range(R)]
    LL = []
    for j in range(R):
      LL.append(perm[i % (R - j)])
      perm.remove(perm[i % (R - j)])
    tmp = 0
    pnt = 0
    flg = [0 for _ in range(R)]
    flg[0] = 1
    while flg != tgt:
      s = r[LL[pnt]]
      right = pnt + 1
      while flg[right] == 1:
        right += 1
      t = r[LL[right]]
      tmp += X[s][t]
      for m in Y[s][t]:
        if m in D:
          for x in range(R):
            if LL[x] == D[m]:
              flg[x] = 1
      pnt = right
    if tmp < M:
      M = tmp
else:
  M = X[r[0]][r[1]]
print(M)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from itertools import permutations
def main():
    N,M,R = map(int,stdin.readline().split())
    r = list(map(int,stdin.readline().split()))
    r = tuple(map(lambda x: x-1,r))
    dist = [[2**60]*N for _ in range(N)]
    for _ in range(M):
        A,B,C = map(int,stdin.readline().split())
        A -= 1
        B -= 1
        dist[A][B] = C
        dist[B][A] = C
    for i in range(N):
        dist[i][i] = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j])
    dist = tuple(map(lambda x: tuple(x),dist))
    ans = 2**60
    for t in tuple(permutations(r,R)):
        tmp = 0
        for i in range(R-1):
            tmp += dist[t[i]][t[i+1]] 
        ans = min(ans,tmp)
    
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
def warshall_floyd(g):
    for k in range(len(g)):
        for i in range(len(g)):
            for j in range(len(g)):
                g[i][j] = min(g[i][j], g[i][k]+g[k][j])
    return g

n,m,r = map(int,input().split())
lst = list(map(int,input().split()))
graph = [[float('inf')]*n for _ in range(n)]
for _ in range(m):
    a,b,c = map(int,input().split())
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c
for i in range(n):
    graph[i][i] = 0
d = warshall_floyd(graph)

res = float('inf')
for l in itertools.permutations(lst):
    cnt = 0
    for i in range(1, len(l)):
        cnt += d[l[i-1]-1][l[i]-1]
    res = min(res, cnt)
print(res)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

n, m, r = map(int, input().split())
A = list(map(int, input().split()))
d = [[1e18]*n for i in range(n)]
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])


ans = 1e18
for x in permutations(A):
        l = 0
        for i in range(r-1):
                l += d[x[i]-1][x[i+1]-1]
        ans = min(ans, l)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from itertools import permutations
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, M: int, R: int, r: "List[int]", A: "List[int]", B: "List[int]", C: "List[int]"):
    inf = float("inf")
    md = [[inf] * N for _ in range(N)]
    for i in range(N):
        md[i][i] = 0
    for Ai, Bi, Ci in zip(A, B, C):
        Ai -= 1
        Bi -= 1
        md[Ai][Bi] = md[Bi][Ai] = Ci
    for k in range(N):
        for i in range(N):
            for j in range(N):
                md[i][j] = min(md[i][j], md[i][k] + md[k][j])

    def dist(path):
        return sum(md[p1 - 1][p2 - 1] for p1, p2 in zip(path, path[1:]))

    print(min(dist(path) for path in permutations(r)))


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    R = int(next(tokens))  # type: int
    r = [int(next(tokens)) for _ in range(R)]  # type: "List[int]"
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    C = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    solve(N, M, R, r, A, B, C)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
INF = 10**20
MOD = 10**9 + 7
from itertools import permutations

def main():
    n,m,r = map(int,input().split())
    dest = [int(i) - 1 for i in input().split()]
    dist = [[INF] * n for _ in range(n)]

    for _ in range(m):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        dist[a][b] = c
        dist[b][a] = c
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j] , dist[i][k] + dist[k][j])
    
    ans = INF
    for ptr in permutations(range(r)):
        tmp = 0
        for i in range(r - 1):
            tmp += dist[dest[ptr[i]]][dest[ptr[i + 1]]]
        ans = min (ans, tmp)
    
    print(ans)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

INF = 10**10

d = [[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())

    if d[a][b] > c:
        d[a][b] = c
        d[b][a] = c


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


ans = INF
for p in itertools.permutations(r):
    dist = 0
    for i in range(R-1):
        dist += d[p[i]][p[i+1]]

    ans = min(ans, dist)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

INF = 10**18

d = {}
for i in range(1, N+1):
    for j in range(1, N+1):
        d[(i, j)] = INF
    d[(i, i)] = 0

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

    if d[(a, b)] > c:
        d[(a, b)] = c
        d[(b, a)] = c


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


ans = INF
for p in itertools.permutations(r):
    dist = 0
    for i in range(R-1):
        dist += d[(p[i], p[i+1])]

    ans = min(ans, dist)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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


d = {}
for i in range(1, N+1):
    for j in range(1, N+1):
        d[(i, j)] = -1
    d[(i, i)] = 0

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

    d[(a, b)] = c
    d[(b, a)] = c

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


ans = -1
for p in itertools.permutations(r):
    dist = 0
    for i in range(R-1):
        dist += d[(p[i], p[i+1])]

    if ans < 0:
        ans = dist
    else:
        ans = min(ans, dist)

print(ans)

Submission status: Time Limit Exceeded

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

def Washall_Floyd(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())
R = list(map(int, input().split()))
f_inf = float('inf')
dist = [[f_inf]*n for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    dist[a][b] = c
    dist[b][a] = c

Washall_Floyd(dist)
S = [i for i in itertools.permutations(R, r)]
cnt = f_inf
for s in S:
  tmp = 0
  for i in range(len(s)-1):
    tmp += dist[s[i]-1][s[i+1]-1]
  cnt = min(cnt, tmp)
print(cnt)

Submission status: Time Limit Exceeded

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

inf = 10 ** 18
d = [[inf for _ in range(n)] for _ in range(n)]
for i in range(n):
    d[i][i] = 0
for _ 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])

import itertools
ans = 10 ** 18
for a in itertools.permutations(v):
    dis = 0
    for i in range(r-1):
        dis += d[a[i+1]-1][a[i]-1]
    ans = min(ans, dis)
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()))
l=[[float('inf')]*n for _ in range(n)]
for _ in range(m):
    a,b,c,=map(int,input().split())
    a-=1
    b-=1
    l[a][b]=c
    l[b][a]=c
for i in range(n):
    l[i][i] = 0 #自身のところに行くコストは０
def warshall_floyd(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
F=warshall_floyd(l)
ans=float('inf')
for v in permutations(R):
    temp=0
    for i in range(r-1):
        temp+=F[v[i]-1][v[i+1]-1]
    ans=min(ans,temp)
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
inf=10**9
n,m,R=map(int,input().split())
r=list(map(int,input().split()))
rr=permutations(r,R)
dis=[[inf]*n for _ in range(n)]
for i in range(m):
	a,b,c=map(int,input().split())
	dis[a-1][b-1]=c
	dis[b-1][a-1]=c
for i in range(n):
	for j in range(n):
		for k in range(n):
			dis[j][k]=min(dis[j][i]+dis[i][k],dis[j][k])
ans=10**12
for x in rr:
	e=0
	for i in range(R-1):
		e+=dis[x[i+1]-1][x[i]-1]
	ans=min(ans,e)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
def warshall_floyd(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())
R=list(map(int,input().split()))
for i in range(r):
  R[i]=R[i]-1
d=[[10**10]*n for i in range(n)] 
for i in range(m):
  a,b,c=map(int,input().split())
  a=a-1
  b=b-1
  d[a][b]=c
  d[b][a]=c
for i in range(n):
  d[i][i]=0
D=warshall_floyd(d)
s=1
S=[]
for i in range(1,r+1):
  s=s*i
  S.append(s)
ans=10**10
for i in range(s):
  RR=copy.copy(R)
  E=[]
  for j in range(r-1):
    E.append(RR[i//S[r-j-2]])
    RR.pop(i//S[r-j-2])
    i=i-S[r-j-2]*(i//S[r-j-2])
  E.append(RR[0]) 
  di=0
  for i in range(r-1):
    di=di+D[E[i]][E[i+1]]
  if di<ans:
    ans=di
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools


N,M,R = map(int,input().split())
rs = list(map(lambda x:int(x)-1,input().split()))
cost=[[10**9]*N for i in range(N)]
for i 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(i):  # j<i
            cost[i][j] =  min(cost[i][j],cost[i][k] + cost[k][j])
            cost[j][i] = cost[i][j]

ans = 10**9
for roads in itertools.permutations(rs):
    co = 0
    p = roads[0]
    for r in roads[1:]:
        co += cost[p][r]
        p = r
    ans = min(ans,co)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools


N,M,R = map(int,input().split())
rs = list(map(lambda x:int(x)-1,input().split()))
tree = [[] for i in range(N)]
cost=[[10**9]*N for i in range(N)]
for i 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):  # j<i
            cost[i][j] =  min(cost[i][j],cost[i][k] + cost[k][j])
            cost[j][i] = cost[i][j]

ans = 10**9
for roads in itertools.permutations(rs):
    co = 0
    p = roads[0]
    for r in roads[1:]:
        co += cost[p][r]
        p = r
    ans = min(ans,co)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M,R=map(int,input().split())
r=list(map(int,input().split()))
A=[list(map(int,input().split())) for i in range(M)]
d=[[float("inf")]*N for i in range(N)]

for a,b,c in A:
  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])
      
import itertools 
ans=10**5*8
for i in itertools.permutations(range(R),R):
  D=0
  for j in range(R-1):
    D+=d[r[i[j]]-1][r[i[j+1]]-1]
  ans=min(D,ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n, m, r = map(int, input().split())
R = list(map(int, input().split()))

DP = [[10**10 for _ in range(n+1)] for _ in range(n+1)]
for i in range(1,n+1):
    DP[i][i] = 0

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

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

ans = 10**10
for permutation in itertools.permutations(R, r):
    dist = 0
    for i in range(r-1):
        dist += DP[permutation[i]][permutation[i+1]]
    ans = min(ans, dist)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import sys

N, M, R = map(int, input().split())
r = [int(i) for i in input().split()]
a = [[sys.maxsize for i in range(N)] for i in range(N)]
for i in range(N):
	a[i][i] = 0
for i in range(M):
	A, B, C = map(int, input().split())
	a[A - 1][B - 1] = C
	a[B - 1][A - 1] = C
for i in range(N):
	for j in range(N):
		if a[j][i] == sys.maxsize:
			continue
		for k in range(N):
			if a[i][k] == sys.maxsize:
				continue
			a[j][k] = min(a[i][k] + a[j][i], a[j][k])
r.sort()
ans = sys.maxsize
for i in itertools.permutations(r):
	b = 0
	j = 1
	while j < R:
		b += a[i[j - 1] - 1][i[j] - 1]
		j += 1
	ans = min(b, ans)
print(ans)

Submission status: Time Limit Exceeded

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

#ワーシャルフロイド実装
for k in range(N):
    for i in range(N):
        for j in range(N):
            if i==j:
                Map[i][j] = 0
                Map[j][i] = 0
                continue
            Map[i][j] = min(Map[i][j],Map[i][k]+Map[k][j])



kouho = list(itertools.permutations(r))
ans = float('inf')
for i in range(len(kouho)):
    cnt = 0
    for j in range(len(kouho[i])):
        if j == 0 :
            pre = kouho[i][j]
            continue
        if j == len(kouho[i])-1:
            cnt += Map[pre-1][kouho[i][j]-1]
            ans = min(ans,cnt)
        cnt += Map[pre-1][kouho[i][j]-1]
        pre = kouho[i][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
# coding: utf-8
# Your code here!
import sys
import copy
import itertools

sys.setrecursionlimit(10**7)

def dfs(num,hiyo):
    ans[num]=min(hiyo,ans[num])
    for to,cos in way[num]:
        if ans[to]>ans[num]+cos:
            dfs(to,hiyo+cos)
    
    return 

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

r=list(map(int,input().split()))

way=[[] for i in range(N)]

for _ in range(M):
    A,B,C=map(int,input().split())
    way[A-1].append([B-1,C])
    way[B-1].append([A-1,C])

root=[[] for i in range(N)]
for item in r:
    ans=[10**10]*N
    dfs(item-1,0)
    root[item-1].append(copy.deepcopy(ans))

#print(root)

ans=10**9
for order in itertools.permutations(r):
    temp=0
    for i in range(len(order)-1):
        #print("YES")
        #print(order[i]-1,order[i+1]-1)
        #print(root[order[i]-1][0])
        temp+=root[order[i]-1][0][order[i+1]-1]
    ans=min(ans,temp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations


def warshall_floyd(d, n):
    # 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


N, M, R = map(int, input().split())
r = list(map(int, input().split()))
d = [[float('inf')] * N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c

d = warshall_floyd(d, N)

ans = float('inf')
for p in permutations(r):
    total = 0
    for i in range(1, len(p)):
        total += d[p[i-1]-1][p[i]-1]
    ans = min(ans, total)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

def warshall_floyd(d, n):
    # 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

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())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
d = warshall_floyd(d, N)
ans = float('inf')
for perm in permutations(r):
    total = 0
    for i in range(1, len(perm)):
        total += d[perm[i-1]-1][perm[i]-1]
    ans = min(ans, total)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M, R = map(int,input().split())
r = list(map(lambda x:int(x)-1,input().split()))
from itertools import permutations
perm = permutations(r, R)
INF = float("inf")
dp = [[INF]*N for _ in range(N)]
for _ in range(M):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    dp[a][b] = c
    dp[b][a] = c
for k in range(N):
    for i in range(N):
        for j in range(N):
            dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])
ans = INF
for p in perm:
    tmp = 0
    p = list(p)
    for i in range(R-1):
        tmp += dp[p[i]][p[i+1]]
    ans = min(ans, tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
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

##############################
n,w,r = map(int,input().split()) #n:頂点数　w:辺の数
t = list(map(int,input().split()))

d = [[float("inf")]*n for i in range(n)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(w):
    x,y,z = map(int,input().split())
    d[x-1][y-1] = z
    d[y-1][x-1] = z
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
res = warshall_floyd(d)

print(max([res[t[0]-1][i-1] for i in t]))

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
n,m,r=map(int,input().split())
vis=list(map(int,input().split()))
INF=10**6
path=[[INF]*n for i in range(n)]
for i in range(m):
  a,b,c=map(int,input().split())
  path[a-1][b-1]=c
  path[b-1][a-1]=c
for i in range(n):
  for j in range(n):
    for k in range(n):
      if i!=j and j!=k and k!=i:
        path[i][j]=min(path[i][j],path[i][k]+path[k][j])
        path[j][i]=path[i][j]
ans=10**9
for root in permutations(vis):
  cnt=0
  for j in range(1,r):
    cnt+=path[root[j-1]-1][root[j]-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())
vis=list(map(int,input().split()))
INF=10**6
path=[[INF]*n for i in range(n)]
for i in range(m):
  a,b,c=map(int,input().split())
  path[a-1][b-1]=c
  path[b-1][a-1]=c
for i in range(n):
  for j in range(n):
    for k in range(n):
      if i!=j and j!=k and k!=i:
        path[i][j]=min(path[i][j],path[i][k]+path[k][j])
        path[j][i]=path[i][j]
ans=10**18
for root in permutations(vis):
  cnt=0
  for j in range(1,r):
    cnt+=path[root[j-1]-1][root[j]-1]
  ans=min(ans,cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,m,r=map(int,input().split())
vis=list(map(int,input().split()))
INF=10**6
path=[[INF]*n for i in range(n)]
for i in range(m):
  a,b,c=map(int,input().split())
  path[a-1][b-1]=c
  path[b-1][a-1]=c
for i in range(n):
  for j in range(n):
    for k in range(n):
      if i!=j and j!=k and k!=i:
        path[i][j]=min(path[i][j],path[i][k]+path[k][j])
        path[j][i]=path[i][j]
seq=[i for i in range(r)]
num=list(itertools.permutations(seq))
ans=10**18
for root in num:
  cnt=0
  for j in range(1,len(root)):
    cnt+=path[root[j-1]-1][root[j]-1]
  ans=min(ans,cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
def warshallFloyd():
    for i in range(N):
        for j in range(N):
            if dp[j][i] == INF: continue
            for k in range(N):
                if dp[i][k] == INF: continue
                dp[j][k] = min(dp[j][k], dp[j][i] + dp[i][k])
    return

INF = 10 ** 18
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
dp = [[INF for _ in range(N)] for _ in range(N)]
ansF = False
for i in range(N):
    for j in range(N):
        if i == j:
            dp[i][j] = 0

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

warshallFloyd()
ans = INF
for i in permutations(r):
    tmp = 0
    for j in range(1, len(i)):
        tmp += dp[i[j - 1] - 1][i[j] - 1]
    ans = min(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
def warshallFloyd():
    for i in range(N):
        for j in range(N):
            for k in range(N):
                dp[j][k] = min(dp[j][k], dp[j][i] + dp[i][k])
    return

INF = 10 ** 18
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
dp = [[INF for _ in range(N)] for _ in range(N)]
ansF = False
for i in range(N):
    for j in range(N):
        if i == j:
            dp[i][j] = 0

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

warshallFloyd()
ans = INF
for i in permutations(r):
    tmp = 0
    for j in range(1, len(i)):
        tmp += dp[i[j - 1] - 1][i[j] - 1]
    ans = min(ans, tmp)

print(ans)