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:
from itertools import permutations

def conv(a):
    return int(a) - 1

N,M,R = map(int,input().split())
rseq = list(map(conv,input().split()))
graph = [[-1]*N for x in range(N)]

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

#FloydWarshall
for k in range(N):
    for i in range(N):
        for j in range(N):
            if graph[i][k] == -1 or graph[k][j] == -1:
                continue
            if graph[i][j] == -1 or graph[i][j] > graph[i][k] + graph[k][j]:
                graph[i][j] = graph[i][k] + graph[k][j]

minimum = 200000000
for p in permutations(rseq):
    total = 0
    for i in range(1,R):
        total += graph[p[i]][p[i-1]]
        if total > minimum:
            break
    if total < minimum:
        minimum = total
print(minimum)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

def conv(a):
    return int(a) - 1

N,M,R = map(int,input().split())
rseq = list(map(conv,input().split()))
graph = [[-1]*N for x in range(N)]

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

#FloydWarshall
for k in range(N):
    for i in range(N):
        for j in range(N):
            if graph[i][k] == -1 or graph[k][j] == -1:
                continue
            if graph[i][j] == -1 or graph[i][j] > graph[i][k] + graph[k][j]:
                graph[i][j] = graph[i][k] + graph[k][j]

minimum = 200000000
for p in permutations(rseq):
    total = 0
    for i in range(1,R):
        total += graph[p[i]][p[i-1]]
    if total < minimum:
        minimum = total
print(minimum)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

##def permutation(lst):
##    if len(lst) < 2:
##        return[lst]
##    l = []
##    for i in range(len(lst)):
##        m = lst[i]
##        remLst = lst[:i] + lst[i+1:]
##        for p in permutation(remLst):
##            l.append([m] + p)
##    return l

N,M,R = map(int,input().split())
rseq = list(map(int,input().split()))
graph = [[-1]*(N+1) for x in range(N+1)]

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

##dist = [[(2 * (10 ** 8)) for x in range(N+1)] for x in range(N+1)]
#FloydWarshall
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            if graph[i][k] == -1 or graph[k][j] == -1:
                continue
            if graph[i][j] == -1 or graph[i][j] > graph[i][k] + graph[k][j]:
                graph[i][j] = graph[i][k] + graph[k][j]

minimum = 200000000
for p in permutations(rseq):
    total = 0
    for j in range(1,R):
        total += graph[p[j]][p[j-1]]
    if total < minimum:
        minimum = total
print(minimum)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

##def permutation(lst):
##    if len(lst) < 2:
##        return[lst]
##    l = []
##    for i in range(len(lst)):
##        m = lst[i]
##        remLst = lst[:i] + lst[i+1:]
##        for p in permutation(remLst):
##            l.append([m] + p)
##    return l

N,M,R = map(int,input().split())
rseq = list(map(int,input().split()))
graph = [[-1 for x in range(N+1)] for x in range(N+1)]

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

##dist = [[(2 * (10 ** 8)) for x in range(N+1)] for x in range(N+1)]
#FloydWarshall
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            if graph[i][k] == -1 or graph[k][j] == -1:
                continue
            if graph[i][j] == -1 or graph[i][j] > graph[i][k] + graph[k][j]:
                graph[i][j] = graph[i][k] + graph[k][j]

minimum = 200000000
for p in permutations(rseq):
    total = 0
    for j in range(1,R):
        total += graph[p[j]][p[j-1]]
    if total < minimum:
        minimum = total
print(minimum)

Submission status: Time Limit Exceeded

Solution code:
def permutation(lst):
    if len(lst) < 2:
        return[lst]
    l = []
    for i in range(len(lst)):
        m = lst[i]
        remLst = lst[:i] + lst[i+1:]
        for p in permutation(remLst):
            l.append([m] + p)
    return l

N,M,R = map(int,input().split())
rseq = list(map(int,input().split()))
graph = [[-1 for x in range(N+1)] for x in range(N+1)]

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

##dist = [[(2 * (10 ** 8)) for x in range(N+1)] for x in range(N+1)]
#FloydWarshall
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            if graph[i][k] == -1 or graph[k][j] == -1:
                continue
            if graph[i][j] == -1 or graph[i][j] > graph[i][k] + graph[k][j]:
                graph[i][j] = graph[i][k] + graph[k][j]
                
rpsec = permutation(rseq)
minimum = 200000000
for p in rpsec:
    total = 0
    for j in range(1,R):
        total += graph[p[j]][p[j-1]]
    if total < minimum:
        minimum = total
print(minimum)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N,M,R=map(int,input().split())
r=list(map(int,input().split()))
for i in range(R): r[i] -= 1

g = [ [1001001001] * 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 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 = 1001001001
for p in itertools.permutations(r):
  cur = 0
  for i in range(1, R):
    cur += g[p[i-1]][p[i]]
  ans = min(ans, cur)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
def solution():
	n,m,r = [int(x) for x in input().split(' ')]
	R = [int(x) for x in input().split(' ')]
	matrix = []
	for i in range(n):
		matrix.append([float("inf")]*n)

	for i in range(m):
		arc = [int(x) for x in input().split(' ')]
		matrix[arc[0]-1][arc[1]-1] = arc[2]
		matrix[arc[1]-1][arc[0]-1] = arc[2]

	for k in range(n):
		for j in range(n):
			for i in range(n):
				matrix[i][j] = min(matrix[i][j],matrix[i][k]+matrix[k][j])
	_min = float("inf")
	for order in itertools.permutations(R):
		val = 0
		for i in range(1,r):
			val += matrix[order[i-1]-1][order[i]-1]
			if val > _min:
				break
		if val < _min:
			_min = val

	return _min

print(solution())

Submission status: Time Limit Exceeded

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

g = [ [1001001001] * 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 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])
memo = {}

def f(s, l, c):
  if s + 1 == 1 << R:
    return c
  if (s,l) in memo:
    return memo[s,l];
  res = 1001001001
  for i in range(R):
    if (s >> i & 1) == 0:
      x = f(s | (1 << i), i, c + g[r[l]][r[i]])
      res = min(res, x)
  memo[s, l] = res
  return res

ans = min([ f(1 << i, i, 0) for i in range(R) ]) 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def nextPermutation(order):
	if len(order) == 1:
		return [order]
	elif len(order) == 2:
		return [order,[order[1],order[0]]]
	else:
		ans = []
		for i in range(len(order)):
			for _order in nextPermutation(order[:i]+order[(i+1):]):
				ans.append([order[i]]+_order)

		return ans


def solution():
	n,m,r = [int(x) for x in input().split(' ')]
	R = [int(x) for x in input().split(' ')]
	matrix = []
	for i in range(n):
		matrix.append([float("inf")]*n)

	for i in range(m):
		arc = [int(x) for x in input().split(' ')]
		matrix[arc[0]-1][arc[1]-1] = arc[2]
		matrix[arc[1]-1][arc[0]-1] = arc[2]

	for k in range(n):
		for j in range(n):
			for i in range(n):
				matrix[i][j] = min(matrix[i][j],matrix[i][k]+matrix[k][j])
	_min = float("inf")
	for i in range(r):
		permutations = nextPermutation(R[:i]+R[(i+1):])
		for _order in permutations:
			newOrder = [R[i]]+_order
			val = 0
			for i in range(1,r):
				val += matrix[newOrder[i-1]-1][newOrder[i]-1]
				if val > _min:
					break
			if val < _min:
				_min = val

	return _min

print(solution())

Submission status: Time Limit Exceeded

Solution code:
def nextPermutation(order):
	if len(order) == 1:
		return [order]
	elif len(order) == 2:
		return [order,[order[1],order[0]]]
	else:
		ans = []
		for i in range(len(order)):
			for _order in nextPermutation(order[:i]+order[(i+1):]):
				ans.append([order[i]]+_order)

		return ans


def solution():
	n,m,r = [int(x) for x in input().split(' ')]
	R = [int(x) for x in input().split(' ')]
	matrix = []
	for i in range(n):
		matrix.append([float("inf")]*n)

	for i in range(m):
		arc = [int(x) for x in input().split(' ')]
		matrix[arc[0]-1][arc[1]-1] = arc[2]
		matrix[arc[1]-1][arc[0]-1] = arc[2]

	for k in range(n):
		for j in range(n):
			for i in range(n):
				matrix[i][j] = min(matrix[i][j],matrix[i][k]+matrix[k][j])
	_min = float("inf")
	permutations = nextPermutation(R)
	for order in permutations:
		val = 0
		for i in range(1,r):
			val += matrix[order[i-1]-1][order[i]-1]
			if val > _min:
				break
		if val < _min:
			_min = val

	return _min

print(solution())

Submission status: Time Limit Exceeded

Solution code:
def nextPermutation(order):
	if len(order) == 1:
		return [order]
	elif len(order) == 2:
		return [order,[order[1],order[0]]]
	else:
		ans = []
		for i in range(len(order)):
			for _order in nextPermutation(order[:i]+order[(i+1):]):
				ans.append([order[i]]+_order)

		return ans


def solution():
	n,m,r = [int(x) for x in input().split(' ')]
	R = [int(x) for x in input().split(' ')]
	matrix = []
	for i in range(n):
		matrix.append([float("inf")]*n)

	for i in range(m):
		arc = [int(x) for x in input().split(' ')]
		matrix[arc[0]-1][arc[1]-1] = arc[2]
		matrix[arc[1]-1][arc[0]-1] = arc[2]

	for k in range(n):
		for j in range(n):
			for i in range(n):
				matrix[i][j] = min(matrix[i][j],matrix[i][k]+matrix[k][j])
	_min = float("inf")
	permutations = nextPermutation(R)
	for order in permutations:
		val = 0
		for i in range(1,r):
			val += matrix[order[i-1]-1][order[i]-1]
		if val < _min:
			_min = val

	return _min

print(solution())

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    N, M, R = list(map(int, input().split()))
    r = list(map(int, input().split()))
    # ワーシャルフロイド
    d = [[float('inf') for i in range(N)] for i in range(N)]
    for i in range(0, N):
        d[i][i] = 0
    for i in range(M):
        A, B, C = list(map(int, input().split()))
        d[A - 1][B - 1] = C
        d[B - 1][A - 1] = C

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

    mincost = [float('inf') for i in range(N)]
    used = [False for i in range(N)]

    mincost[r[0] - 1] = 0
    ans = 0

    while True:
        v = -1
        for tmp_r in r:
            # print(tmp_r)
            if not used[tmp_r - 1] and (v == -1 or mincost[tmp_r - 1] < mincost[v]):
                v = tmp_r - 1

        if v == -1:
            break

        used[v] = True
        ans += mincost[v]

        for tmp_r in r:
            mincost[tmp_r - 1] = min(mincost[tmp_r - 1], d[v][tmp_r - 1])

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc073/tasks/abc073_d
warshallFloydで検索 → TLE
"""
from itertools import permutations


def warshallFloyd(V, dp):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])


def main():
    N, M, R = [int(x) for x in input().split()]
    destinations = [int(x) for x in input().split()]
    dp = [[float('inf')]*(N+1) for _ in range(N+1)]
    for i in range(N+1):
        dp[i][i] = 0
    for _ in range(M):
        f, t, d = [int(x) for x in input().split()]
        dp[f][t] = dp[t][f] = d

    warshallFloyd(N+1, dp)

    minimum_cost = float('inf')
    for route in permutations(destinations, len(destinations)):
        cost = 0
        while len(route) > 1:
            f, t = route[0], route[1]
            cost += dp[f][t]
            if cost > minimum_cost:
                break
            route = route[1:]
        if cost < minimum_cost:
            minimum_cost = cost
    print(minimum_cost)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc073/tasks/abc073_d
"""
from itertools import permutations


def warshallFloyd(V, dp):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])


def main():
    N, M, R = [int(x) for x in input().split()]
    destinations = [int(x) for x in input().split()]
    dp = [[float('inf')]*(N+1) for _ in range(N+1)]
    for i in range(N+1):
        dp[i][i] = 0
    for _ in range(M):
        f, t, d = [int(x) for x in input().split()]
        dp[f][t] = d
        dp[t][f] = d

    warshallFloyd(N+1, dp)
    # for d in dp:
    #     print(d)
    # print('='*32)

    minimum_cost = float('inf')
    for route in permutations(destinations, len(destinations)):
        cost = 0
        while len(route) > 1:
            f, t = route[0], route[1]
            cost += dp[f][t]
            route = route[1:]
        if cost < minimum_cost:
            minimum_cost = cost
    print(minimum_cost)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
 
N, M, R = map(int, input().split())
r = map(int, input().split())
 
INF = float("inf")
d = [[INF] * (N + 1) for _ in range(N + 1)]
for n in range(1, N + 1):
    d[n][n] = 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):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]

ans = INF
for p in permutations(r):
    cnt = 0
    for i in range(len(p) - 1):
        p1, p2 = p[i:i + 2]
        cnt += d[p1][p2]
    ans = min(cnt, ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

N,M,R = map(int, input().split())
r = map(int, input().split())
INF = float("inf")

dis = [[INF]*(N+1) for _ in range(N+1)]
for n in range(1, N+1):
	dis[n][n] = 0
for i in range(M):
    Ai, Bi, Ci = map(int, input().split())
    dis[Ai][Bi] = Ci
    dis[Bi][Ai] = Ci
for k in range(1, N+1):    # Warshall-Floyd
    for i in range(1, N+1):
        for j in range(1, N+1):
            if dis[i][j] > dis[i][k] + dis[k][j]:
                dis[i][j] = dis[i][k] + dis[k][j]

ans = INF
for p in permutations(r):
    cnt = 0
    for i in range(len(p)-1):
        cnt += dis[p[i]][p[i+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 = map(int,input().split())

dis = [[float("inf")]*(N+1) for _ in range(N+1)]
for n in range(1, N+1):
	dis[n][n] = 0
for i in range(M):
    Ai, Bi, Ci = map(int, input().split())
    dis[Ai][Bi] = Ci
    dis[Bi][Ai] = Ci
for k in range(1, N+1):    # Warshall-Floyd
    for i in range(1, N+1):
        for j in range(1, N+1):
            if dis[i][j] > dis[i][k] + dis[k][j]:
                dis[i][j] = dis[i][k] + dis[k][j]

ans = float("inf")
for p in permutations(r):
    cnt = 0
    for i in range(len(p)-1):
        cnt += dis[p[i]][p[i+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 = map(int,input().split())
ans = float("inf")

dis = [[float("inf")]*(N+1) for _ in range(N+1)]
for n in range(1, N+1):
	dis[n][n] = 0
for i in range(M):
    Ai, Bi, Ci = map(int, input().split())
    dis[Ai][Bi] = Ci
    dis[Bi][Ai] = Ci
for k in range(1, N+1):    # Warshall-Floyd
    for i in range(1, N+1):
        for j in range(1, N+1):
            if dis[i][j] > dis[i][k] + dis[k][j]:
                dis[i][j] = dis[i][k] + dis[k][j]

for p in permutations(r):
    cnt = 0
    for i in range(len(p)-1):
        cnt += dis[p[i]][p[i+1]]
    ans = min(ans, cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def permutation(lst):
    if len(lst) == 0:
        return []
    if len(lst) == 1:
        return[lst]
    l = []
    for i in range(len(lst)):
        m = lst[i]
        remLst = lst[:i] + lst[i+1:]
        for p in permutation(remLst):
            l.append([m] + p)
    return l

N,M,R = map(int,input().split())
rseq = list(map(int,input().split()))
graph = [[] for x in range(N+1)]

for i in range(M):
    A,B,C = map(int,input().split())
    graph[A].append((B,C))
    graph[B].append((A,C))

dist = [[(2 * (10 ** 8)) for x in range(N+1)] for x in range(N+1)]
#FloydWarshall
for i in range(N+1):
    dist[i][i] = 0
for i in range(1,N+1):
    for j in range(len(graph[i])):
        dist[i][graph[i][j][0]] = graph[i][j][1]
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
rpsec = permutation(rseq)
minimum = 200000000
for p in rpsec:
    total = 0
    for j in range(1,R):
        total += dist[p[j]][p[j-1]]
    if total < minimum:
        minimum = total
print(minimum)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

def input_list() :
    return list(map(int, input().split()))

n, m ,r = input_list()
road = input_list()
road = [x-1 for x in road]
d = [[float('inf')] * n for i in range(n)]
for i in range(n) :
    d[i][i] = 0
for i in range(m) :
    a, b, c = input_list()
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = c

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

ans = float('inf')
for p in permutations(road) :
    dist = 0
    for i in range(r-1) :
        dist += d[p[i]][p[i+1]]
    if ans > dist :
        ans = dist

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

def input_list() :
    return list(map(int, input().split()))

n, m ,r = input_list()
road = input_list()
road = [x-1 for x in road]
d = [[float('inf')] * n for i in range(n)]
for i in range(n) :
    d[i][i] = 0
for i in range(m) :
    a, b, c = input_list()
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = c

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

ans = float('inf')
for p in permutations(road) :
    dist = 0
    for i in range(r-1) :
        dist += d[p[i]][p[i+1]]
    if ans > dist :
        ans = dist

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import sys
 
N, M, R = map(int, sys.stdin.readline().split())
 
r = [i - 1 for i in map(int, sys.stdin.readline().split())]
 
d = [[float('inf')]*N for _ 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 a in range(N):
    d[a][a] = 0
 
res = float('inf')
 
for k in range(N):
    for i in range(N):
        for j in range(N):
            if d[i][k]+d[k][j] < d[i][j]:
                d[i][j] = d[i][k]+d[k][j]
 
for perm in itertools.permutations(r):
    a = 0
    for i in range(len(perm)-1):
        a += d[perm[i]][perm[i+1]]
    res = min(a, res)
 
print(res)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
import sys

N, M, R = map(int, sys.stdin.readline().split())
r = [i - 1 for i in map(int, sys.stdin.readline().split())]

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

for i in range(N):
    d[i][i] = 0
    
for i 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 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]

ans = 10**12

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
import sys

N, M, R = map(int, sys.stdin.readline().split())
r = [i - 1 for i in map(int, sys.stdin.readline().split())]

d = [[float('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):
    a, b, c = map(int,sys.stdin.readline().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]

ans = 10**12

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
import sys

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

d = [[float('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):
    a, b, c = map(int,sys.stdin.readline().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):
            dd =  d[i][k] + d[k][j]
            if d[i][j] > dd:
                d[i][j] = dd

ans = 10**12

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
import sys

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

d = [[float('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):
    a, b, c = map(int,sys.stdin.readline().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]

ans = 10**12

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
import sys

N, M, R = map(int, sys.stdin.readline().split())
r = [int(i) - 1 for i in sys.stdin.readline().split()]
d = [[float('inf')] * N for j in range(N)]
for i in range(M):
    A, B, C = map(int, sys.stdin.readline().split())
    d[A-1][B-1] = min(d[A-1][B-1], C)
    d[B-1][A-1] = min(d[B-1][A-1], C)
for k in range(N):
    for s in range(N):
        for e in range(N):
            d[s][e] = min(d[s][e], d[s][k] + d[k][e])
l = True
for o in permutations(r):
    tmp_l = 0
    for s, e in zip(o[:-1], o[1:]):
        tmp_l = tmp_l + d[s][e]
    if l is True:
        l = tmp_l
    else:
        l = min(l, tmp_l)
print(l)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
import numpy as np
def read(): return list(map(int, input().split()))


INF = 114514810


def wf(d):
    N = len(d[0])
    d = np.array(d)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
    return d


def calc_dist(p, d):
    dist = 0
    for i in range(len(p) - 1):
        if d[p[i]][p[i + 1]] >= INF:
            return INF
        dist += d[p[i]][p[i + 1]]
    return dist


def main():
    N, M, R = read()
    r = map(lambda x: x - 1, sorted(read()))
    d = [[INF for i in range(N)] for j in range(N)]

    for i in range(M):
        a, b, c, = read()
        a -= 1
        b -= 1
        d[a][b] = d[b][a] = c

    d = wf(d)

    min_dist = INF
    for p in list(permutations(r)):
        min_dist = min(min_dist, calc_dist(p, d))

    print(min_dist)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
import numpy as np
def read(): return list(map(int, input().split()))

INF = 114514810

def wf(d):
    N = len(d[0])
    d = np.array(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


def calc_dist(p, d):
    dist = 0
    for i in range(len(p) - 1):
        dist += d[p[i]][p[i + 1]]
    return dist


def main():
    N, M, R = read()
    r = map(lambda x: x - 1, sorted(read()))
    d = [[INF for i in range(N)] for j in range(N)]

    for i in range(M):
        a, b, c, = read()
        a -= 1
        b -= 1
        d[a][b] = d[b][a] = c

    d = wf(d)

    min_dist = INF
    for p in list(permutations(r)):
        min_dist = min(min_dist, calc_dist(p, d))

    print(min_dist)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
import sys

def readline():
    return sys.stdin.readline()

def read_int_list():
    return list(map(int, readline().split()))

def read_int():
    return int(readline())

def main():
    N, M, R = read_int_list()

    r = [a-1 for a in read_int_list()]

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

    for _ in range(M):
        a, b, c = read_int_list()
        d[a-1][b-1] = c
        d[b-1][a-1] = c

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

    res = float('inf')

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

    for perm in itertools.permutations(r):
        a = 0
        for i in range(len(perm)-1):
            a += d[perm[i]][perm[i+1]]
        res = min(a, res)

    print(res)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
import sys

def readline():
    return sys.stdin.readline()

def read_int_list():
    return list(map(int, readline().split()))

def read_int():
    return int(readline())

def main():
    N, M, R = read_int_list()

    r = [a-1 for a in read_int_list()]

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

    for _ in range(M):
        a, b, c = read_int_list()
        d[a-1][b-1] = c
        d[b-1][a-1] = c

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

    res = float('inf')

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

    for perm in itertools.permutations(r):
        a = 0
        for i in range(len(perm)-1):
            a += d[perm[i]][perm[i+1]]
        res = min(a, res)

    print(res)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
import sys

def readline():
    return sys.stdin.readline()

def read_int_list():
    return list(map(int, readline().split()))

def read_int():
    return int(readline())

def main():
    N, M, R = read_int_list()

    r = [a-1 for a in read_int_list()]

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

    for _ in range(M):
        a, b, c = read_int_list()
        d[a-1][b-1] = c
        d[b-1][a-1] = c

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

    res = float('inf')

    for a, b, c in itertools.product(range(N), repeat=3):
        d[b][c] = min(d[b][c], d[b][a]+d[a][c])

    for perm in itertools.permutations(r):
        a = 0
        for i in range(len(perm)-1):
            a += d[perm[i]][perm[i+1]]
        res = min(a, res)

    print(res)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8

from collections import defaultdict
import itertools

inf = 10 ** 9

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

cost = defaultdict(dict)
for i in range(1, N + 1):
    for j in range(1, N + 1):
        if i == j:
            cost[i][j] = 0
        else:
            cost[i][j] = inf
for i in range(M):
    A, B, C = map(int, input().split(" "))
    cost[A][B] = C
    cost[B][A] = C

#get shortest path for each node pair
for k in range(1, N + 1):
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            if cost[i][j] > cost[i][k] + cost[k][j]:
                cost[i][j] = cost[i][k] + cost[k][j]

min_dist = inf
for route in itertools.permutations(r_list):
    dist = 0
    for i in range(len(route)):
        if i == len(route) - 1:
            break
        dist += cost[route[i]][route[i + 1]]
    if dist < min_dist:
        min_dist = dist
print(min_dist)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
def read(): return list(map(int, input().split()))

INF = 1145141919

def wf(d):
    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


def calc_dist(p, d):
    dist = 0
    for i in range(len(p) - 1):
        dist += d[p[i]][p[i + 1]]
    return dist


def main():
    N, M, R = read()
    r = map(lambda x: x - 1, sorted(read()))
    d = [[INF for i in range(N)] for j in range(N)]

    for i in range(M):
        a, b, c, = read()
        a -= 1
        b -= 1
        d[a][b] = d[b][a] = c

    d = wf(d)

    min_dist = INF
    for p in list(permutations(r)):
        min_dist = min(min_dist, calc_dist(p, d))

    print(min_dist)


if __name__ == '__main__':
    main()