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:
inf = float('inf')

n, m, r = map(int, input().split())
rs = [r-1 for r in list(map(int, input().split()))]


ds = [[inf] * n for _ in range(n)]
for i in range(n):
  ds[i][i] = 0

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

## warshall floyd
for k in range(n):
  for i in range(n):
    for j in range(n):
      ds[i][j] = min(ds[i][j], ds[i][k] + ds[k][j])


#def dfs(dist, before, remain, ds):
#  print(f'dfs({dist}, {before}, {remain})')
#  if remain == []:
#    return dist
#  dd = []
#  for r in remain:
#    if before is not None:
#      dist += ds[before][r]
#    dd.append(dfs(dist, r, list(set(remain) - set([r])), ds))
#  return min(dd)    
#
#print(dfs(0, None, rs, ds))


import itertools
dds = []
for i in itertools.permutations(rs, len(rs)):
  d = 0
  for j in range(len(rs)-1):
    dd = ds[i[j]][i[j+1]]
    d += dd
    #print(f'added {dd}')
  dds.append(d)
print(min(dds))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import itertools

def main():
    node_num, edge_num, visit_num = map(int, input().split())
    visit_place = list(map(int, input().split()))
    data = [list(map(int, input().split())) for i in range(edge_num)]

    hashi_set = defaultdict(set)
    kyori_data = [defaultdict(int) for i in range(node_num + 1)]
    for i in range(edge_num):
        a, b, c = data[i]
        hashi_set[a].add(b)
        hashi_set[b].add(a)
        kyori_data[a][b] = c
        kyori_data[b][a] = c

    saitan_data = [[-1 for i in range(node_num + 1)] for j in range(node_num + 1)]


    for i in range(1, node_num + 1):
        saitan_data[i][i] = 0
        done_data = set()
        done_data.add(i)
        for j in range(1, i):
            saitan_data[i][j] = saitan_data[j][i]
            done_data.add(j)

        while len(done_data) < node_num:
            node_add = -1
            kyori_add = 10 ** 10
            for now_ele in done_data:
                for next_ele in hashi_set[now_ele]:
                    if saitan_data[i][next_ele] != -1:
                        continue
                    kyori = saitan_data[i][now_ele] + kyori_data[now_ele][next_ele]
                    if kyori < kyori_add:
                        kyori_add = kyori
                        node_add = next_ele
            done_data.add(node_add)
            saitan_data[i][node_add] = kyori_add

    # for i in range(node_num + 1):
    #     print(saitan_data[i])

    ans = 10 ** 10
    for ikikata in list(itertools.permutations(visit_place, visit_num)):
        kari = 0
        for i in range(visit_num - 1):
            kari += saitan_data[ikikata[i]][ikikata[i + 1]]
        if kari < ans:
            ans = kari
    print(ans)





if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

n, m, r = [ int(v) for v in input().split() ]
town_list = [ int(v)-1 for v in input().split() ]

road_matrix = [ [ 10**9 for j in range(n) ] for i in range(n) ]


for i in range(m):
	s, e, d = [ int(v) - 1 for v in input().split() ]
	road_matrix[s][e] = d + 1
	road_matrix[e][s] = d + 1


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


mindist = 10**9
for i in itertools.permutations(town_list,r):
	dist = 0
	for j in range(r-1):
		dist += road_matrix[i[j]][i[j+1]]

	mindist = min(mindist,dist)
print(mindist)

Submission status: Time Limit Exceeded

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

n, m, r = [ int(v) for v in input().split() ]
town_list = [ int(v)-1 for v in input().split() ]

road_matrix = [ [ 10**9 for j in range(n) ] for i in range(n) ]


for i in range(m):
	s, e, d = [ int(v) - 1 for v in input().split() ]
	road_matrix[s][e] = d + 1
	road_matrix[e][s] = d + 1


min_dist_matrix = []
for h in range(n):
	min_dist = [ min_dist_matrix[i][h] for i in range(h)] + road_matrix[h][h:]
	searched_point = []
	sarching_point = []
	j = h
	while len(searched_point) < n:
		heapq.heappush(searched_point,j)
		for i in range(n):
			if road_matrix[j][i] != 10**9 and i != h:
				heapq.heappush(sarching_point,(road_matrix[j][i],i))
				min_dist[i] = min(min_dist[i],min_dist[j] + road_matrix[j][i])
		sarching_point.sort()

		for k in range(len(sarching_point)):
			s = heapq.heappop(sarching_point)
			if s[1] not in searched_point:
				j = s[1]
				break

	min_dist_matrix.append(min_dist)


mindist = 10**9
for i in itertools.permutations(town_list,r):
	dist = 0
	for j in range(r-1):
		dist += min_dist_matrix[i[j]][i[j+1]]

	mindist = min(mindist,dist)
print(mindist)

Submission status: Time Limit Exceeded

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

n, m, r = [ int(v) for v in input().split() ]
town_list = [ int(v)-1 for v in input().split() ]

road_matrix = [ [ 10**9 for j in range(n) ] for i in range(n) ]


for i in range(m):
	s, e, d = [ int(v) - 1 for v in input().split() ]
	road_matrix[s][e] = d + 1
	road_matrix[e][s] = d + 1


min_dist_matrix = []
for h in range(n):
	min_dist = [ min_dist_matrix[i][h] for i in range(h)] + road_matrix[h][h:]
	searched_point = []
	sarching_point = []
	j = h
	while len(searched_point) < n:
		searched_point.append(j)
		for i in range(n):
			if road_matrix[j][i] != 10**9 and i != h:
				heapq.heappush(sarching_point,(road_matrix[j][i],i))
				min_dist[i] = min(min_dist[i],min_dist[j] + road_matrix[j][i])
		sarching_point.sort()

		for k in range(len(sarching_point)):
			s = heapq.heappop(sarching_point)
			if s[1] not in searched_point:
				j = s[1]
				break

	min_dist_matrix.append(min_dist)


mindist = 10**9
for i in itertools.permutations(town_list,r):
	dist = 0
	for j in range(r-1):
		dist += min_dist_matrix[i[j]][i[j+1]]

	mindist = min(mindist,dist)
print(mindist)

Submission status: Time Limit Exceeded

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

n, m, r = [ int(v) for v in input().split() ]
town_list = [ int(v)-1 for v in input().split() ]

road_matrix = [ [ 10**9 for j in range(n) ] for i in range(n) ]


for i in range(m):
	s, e, d = [ int(v) - 1 for v in input().split() ]
	road_matrix[s][e] = d + 1
	road_matrix[e][s] = d + 1


min_dist_matrix = []
for h in range(n):
	min_dist = road_matrix[h]
	searched_point = []
	sarching_point = []
	j = h
	while len(searched_point) < n:
		searched_point.append(j)
		for i in range(n):
			if road_matrix[j][i] != 10**9 and i != h:
				heapq.heappush(sarching_point,(road_matrix[j][i],i))
				min_dist[i] = min(min_dist[i],min_dist[j] + road_matrix[j][i])
		sarching_point.sort()

		for k in range(len(sarching_point)):
			s = heapq.heappop(sarching_point)
			if s[1] not in searched_point:
				j = s[1]
				break

	min_dist_matrix.append(min_dist)


mindist = 10**9
for i in itertools.permutations(town_list,r):
	dist = 0
	for j in range(r-1):
		dist += min_dist_matrix[i[j]][i[j+1]]

	mindist = min(mindist,dist)
print(mindist)

Submission status: Time Limit Exceeded

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

n, m, r = [ int(v) for v in input().split() ]
town_list = [ int(v)-1 for v in input().split() ]

road_matrix = [ [ 10**9 for j in range(n) ] for i in range(n) ]


for i in range(m):
	s, e, d = [ int(v) - 1 for v in input().split() ]
	road_matrix[s][e] = d + 1
	road_matrix[e][s] = d + 1


min_dist_matrix = []
for h in range(n):
	min_dist = road_matrix[h]
	searched_point = []
	sarching_point = []
	j = h
	while len(searched_point) < n:
		searched_point.append(j)
		for i in range(n):
			if road_matrix[j][i] != 10**9 and i != h:
				sarching_point.append((road_matrix[j][i],i))
				min_dist[i] = min(min_dist[i],min_dist[j] + road_matrix[j][i])
		sarching_point.sort()

		for k in range(len(sarching_point)):
			if sarching_point[k][1] not in searched_point:
				j = sarching_point[k][1]
				sarching_point = sarching_point[k+1:]
				break
	min_dist_matrix.append(min_dist)


mindist = 10**9
for i in itertools.permutations(town_list,r):
	dist = 0
	for j in range(r-1):
		dist += min_dist_matrix[i[j]][i[j+1]]

	mindist = min(mindist,dist)
print(mindist)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n, m, r = [ int(v) for v in input().split() ]
town_list = [ int(v)-1 for v in input().split() ]

road_matrix = [ [ 10**9 for j in range(n) ] for i in range(n) ]


for i in range(m):
	s, e, d = [ int(v) - 1 for v in input().split() ]
	road_matrix[s][e] = d + 1
	road_matrix[e][s] = d + 1


min_dist_matrix = []
for h in range(n):
	min_dist = road_matrix[h]
	searched_point = []
	sarching_point = []
	j = h
	while len(searched_point) < n:
		searched_point.append(j)
		for i in range(n):
			if road_matrix[j][i] != 10**9 and i != h:
				sarching_point.append((road_matrix[j][i],i))
				min_dist[i] = min(min_dist[i],min_dist[j] + road_matrix[j][i])
		sarching_point.sort()

		for k in range(len(sarching_point)):
			if sarching_point[k][1] not in searched_point:
				j = sarching_point[k][1]
				sarching_point = sarching_point[k+1:]
				break
	min_dist_matrix.append(min_dist)


mindist = 10**9
for i in itertools.permutations(town_list,r):
	dist = 0
	for j in range(r-1):
		dist += min_dist_matrix[i[j]][i[j+1]]

	mindist = min(mindist,dist)
print(mindist)

Submission status: Time Limit Exceeded

Solution code:
n,m,r = map(int,input().split())
R = tuple(map(int,input().split()))
ABC = [list(map(int,input().split())) for _ in range(m)]
inf = 1000000000

edge = [[inf]*(n+1) for _ in range(n+1)]

for a,b,c in ABC:
    edge[a][b] = c
    edge[b][a] = c

def wf(e,n):
    for s in range(1,n+1):
        for g in range(1,n+1):
            for k in range(1,n+1):
                e[s][g] = min(e[s][g],e[s][k] + e[k][g])
                e[g][s] = e[s][g]
    return e
    


from itertools import permutations as pm

temp = list(pm(R))

ans = 10000000000
Edge = wf(edge,n)

for RR in temp:
    cost = 0
    for i in range(r-1):
        cost += Edge[RR[i]][RR[i+1]]
    if cost < ans:
        ans = cost

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from itertools import permutations

def warshall_floyd(conn):
    n = len(conn)
    dp = [[v for v in A] for A in conn]
    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])
    return dp


def solve(N: int, M: int, R: int, r: "List[int]", A: "List[int]", B: "List[int]", C: "List[int]"):
    conn = [[float('inf') for _ in range(N)] for _ in range(N)]
    for i in range(N):
        conn[i][i] = 0
    for j in range(M):
        a = A[j] - 1
        b = B[j] - 1
        conn[a][b] = min(conn[a][b], C[j])
        conn[b][a] = min(conn[b][a], C[j])
    dp = warshall_floyd(conn)
    #print(dp)
    ret = float('inf')
    perms = list(permutations(list(range(R))))
    for order in perms:
        tmp = 0
        for i in range(R - 1):
            s = r[order[i]] - 1
            t = r[order[i + 1]] - 1
            #print(r[s], r[t], dp[s][t])
            tmp += dp[s][t]
        ret = min(ret, tmp)
    print(ret)
    return


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 itertools
n,m,r=map(int,input().split())
R=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(m)]

distance=[[99999999 for i in range(n)] for j in range(n)]
for i in range(n):
  distance[i][i]=0
for i in range(m):
  distance[l[i][0]-1][l[i][1]-1]=l[i][2]
  distance[l[i][1]-1][l[i][0]-1]=l[i][2]

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

ans=99999999
for i in itertools.permutations(R):
  L=list(i)
  ct=0
  for j in range(r-1):
    ct+=distance[L[j]-1][L[j+1]-1]
  ans=min(ans,ct)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from itertools import permutations

def warshall_floyd(conn):
    n = len(conn)
    #dp = [[float('inf') for _ in range(n)] for _ in range(n)]
    dp = [[] for _ in range(n)]
    for i, C in enumerate(conn):
        for j, c in enumerate(C):
            dp[i].append(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])
    return dp


def solve(N: int, M: int, R: int, r: "List[int]", A: "List[int]", B: "List[int]", C: "List[int]"):
    conn = [[float('inf') for _ in range(N)] for _ in range(N)]
    for j in range(M):
        a = A[j] - 1
        b = B[j] - 1
        conn[a][b] = C[j]
        conn[b][a] = C[j]
    dp = warshall_floyd(conn)
    #print(dp)
    ret = float('inf')
    perms = list(permutations(list(range(R))))
    for perm in perms:
        tmp = 0
        for i in range(R - 1):
            s = perm[i] - 1
            t = perm[i + 1] - 1
            #print(r[s], r[t], dp[s][t])
            tmp += dp[s][t]
        ret = min(ret, tmp)
    print(ret)
    return


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 itertools
n,m,r=map(int,input().split())
t=list(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,input().split())
    a,b=min(a,b),max(a,b)
    d[a-1][b-1]=c
for i in range(n):
    for j in range(n):
        for k in range(j+1,n):
            if i==j or i==k:continue
            d[j][k]=min(d[j][k],d[j][i]+d[i][k])
a=float("inf")
for i in list(itertools.permutations(t)):
    x=0
    for j in range(len(t)-1):
        x+=d[min(i[j]-1,i[j+1]-1)][max(i[j]-1,i[j+1]-1)]
    a=min(a,x)
print(a)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,m,r=map(int,input().split())
t=list(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,input().split())
    d[a-1][b-1]=c
    d[b-1][a-1]=c
for i in range(n):
    for j in range(n):
        for k in range(n):
            if i==j or i==k:continue
            d[j][k]=min(d[j][k],d[j][i]+d[i][k])
a=float("inf")
for i in list(itertools.permutations(t)):
    x=0
    for j in range(len(t)-1):x+=d[i[j]-1][i[j+1]-1]
    a=min(a,x)
print(a)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from collections import deque
from functools import reduce
from pprint import pprint
import itertools
import bisect
import copy
import fractions
import math
import random
import sys
import time
import queue
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers): return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers): return reduce(LCM, numbers)
def LCM(m, n): return (m * n // fractions.gcd(m, n))
def warshall_floyd(n):
    # 隣接行列graphを使う
    for i in range(n):  # 経由する頂点
        for j in range(n):  # 開始頂点
            for k in range(n):  # 終端
                graph[j][k] = min(graph[j][k], graph[j][i] + graph[i][k])


N, M, R = MI()
r = LI()
road = [LI() for _ in range(M)]
graph = [[INF] * N for _ in range(N)]
# pprint(graph, width=30)
distance = [[INF] * N for _ in range(N)]
for a, b, c in road:
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c
for i in range(N):
    graph[i][i] = 0

q = queue.PriorityQueue()

# distance = [INF] * N
# while not q.empty():
#     cost, v = q.get()
#     if distance[v] < cost:
#         continue
#     distance[v] = cost
# 
#     for next_v in range(N):
#         if graph[v][next_v] == 0:  # 繋がっていない
#             continue
#         q.put((distance[v] + graph[v][next_v], next_v))

for begin in range(N):
    q.put((0, begin))  # 0番目の頂点始点, 0~0のコストは0
    while not q.empty():
        cost, v = q.get()
        if distance[begin][v] < cost:
            continue
        distance[begin][v] = cost

        for next_v in range(N):
            if graph[v][next_v] == 0:
                continue
            q.put((distance[begin][v] + graph[v][next_v], next_v))

# pprint(graph, width=30)
# pprint(distance, width=30)
mini = INF
for permutation in itertools.permutations(r):
    tmp = 0
    # print(permutation)
    for i in range(R-1):
        tmp += distance[permutation[i]-1][permutation[i+1]-1]
    mini = min(mini, tmp)

print(mini)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from collections import deque
from functools import reduce
from pprint import pprint
import itertools
import bisect
import copy
import fractions
import math
import random
import sys
import time
import queue
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers): return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers): return reduce(LCM, numbers)
def LCM(m, n): return (m * n // fractions.gcd(m, n))
def warshall_floyd(n):
    # 隣接行列graphを使う
    for i in range(n):  # 経由する頂点
        for j in range(n):  # 開始頂点
            for k in range(n):  # 終端
                graph[j][k] = min(graph[j][k], graph[j][i] + graph[i][k])


N, M, R = MI()
r = LI()
road = [LI() for _ in range(M)]
graph = [[INF] * N for _ in range(N)]
# pprint(graph, width=30)
distance = [[INF] * N for _ in range(N)]
for a, b, c in road:
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c
for i in range(N):
    graph[i][i] = 0

q = queue.PriorityQueue()

# distance = [INF] * N
# while not q.empty():
#     cost, v = q.get()
#     if distance[v] < cost:
#         continue
#     distance[v] = cost
# 
#     for next_v in range(N):
#         if graph[v][next_v] == 0:  # 繋がっていない
#             continue
#         q.put((distance[v] + graph[v][next_v], next_v))

for begin in range(N):
    q.put((begin, 0))  # 0番目の頂点始点, 0~0のコストは0
    while not q.empty():
        v, cost = q.get()
        if distance[begin][v] < cost:
            continue
        distance[begin][v] = cost

        for next_v in range(N):
            if graph[v][next_v] == 0:
                continue
            q.put((next_v, distance[begin][v] + graph[v][next_v]))

# pprint(graph, width=30)
# pprint(distance, width=30)
mini = INF
for permutation in itertools.permutations(r):
    tmp = 0
    for i in range(R-1):
        tmp += distance[permutation[i]-1][permutation[i+1]-1]
    mini = min(mini, tmp)

print(mini)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

INF = 1e+9
N, M, R = map(int, input().split())
rlist = list(map(int, input().split()))

G = [[INF]*N for _ in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    G[a-1][b-1] = G[b-1][a-1] = c

def warshall_floyd(G):
    V = len(G)
    for k in range(V):
        for i in range(V):
            for j in range(V):
                G[i][j] = min(G[i][j], G[i][k] + G[k][j])
    return G

G = warshall_floyd(G)
sum_list = []
for tmp in permutations(rlist):
    t_sum = 0
    for i in range(len(tmp)-1):
        t_sum += G[tmp[i]-1][tmp[i+1]-1]
    sum_list.append(t_sum)

print(min(sum_list))

Submission status: Time Limit Exceeded

Solution code:
import itertools

N, M, R = map(int, input().split())
r = list(map(lambda x: int(x) - 1, 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())
MAX = 10 ** 10
dist = [[MAX] * N for _ in range(N)]

for i in range(M):
    dist[A[i]-1][B[i]-1] = C[i]
    dist[B[i]-1][A[i]-1] = C[i]
    
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 = 10 ** 10
for per in itertools.permutations(r, R):
    cost = 0
    for i in range(R-1):
        cost += dist[per[i]][per[i+1]]
    ans = min(ans, cost)

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()))
INF=float("inf")
G=[[INF]*N for i in range(N)]
for i in range(M):
    A,B,C=map(int,input().split())
    A,B=A-1,B-1
    G[A][B]=C
    G[B][A]=C
def distance(a,b):
    stack=[(G[a][i],i) for i in range(N) if G[a][i]!=INF]
    reached=[0]*N
    reached[0]=1
    stack.sort(reverse=True)
    dis=[INF]*N
    dis[0]=0
    while(stack):
        c,i=stack.pop()
        if reached[i]==1:
            continue
        if dis[i]<=c:
            continue
        dis[i]=c
        if i==b:
            return c
        reached[i]=1
        stack.extend([(G[i][j]+dis[i],j) for j in range(N) if G[i][j]!=INF])
        stack.sort(reverse=True)
D=[[0]*N for i in range(N)]
for i in r:
    for j in r:
        if i>=j:
            continue
        D[i-1][j-1]=distance(i-1,j-1)
        D[j-1][i-1]=D[i-1][j-1]
ans=10**9
for r_ in permutations(r):
    res=0
    for i in range(R-1):
        res+=D[r_[i]-1][r_[i+1]-1]
    ans=min(ans,res)
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()))
INF=float("inf")
G=[[INF]*N for i in range(N)]
for i in range(M):
    A,B,C=map(int,input().split())
    A,B=A-1,B-1
    G[A][B]=C
    G[B][A]=C
def distance(a,b):
    stack=[(G[a][i],i) for i in range(N) if G[a][i]!=INF]
    reached=[0]*N
    reached[0]=1
    stack.sort(reverse=True)
    dis=[INF]*N
    dis[0]=0
    while(stack):
        c,i=stack.pop()
        if reached[i]==1:
            continue
        if dis[i]<=c:
            continue
        dis[i]=c
        if i==b:
            return c
        stack.extend([(G[i][j]+dis[i],j) for j in range(N) if G[i][j]!=INF])
        stack.sort(reverse=True)
D=[[0]*N for i in range(N)]
for i in r:
    for j in r:
        if i>=j:
            continue
        D[i-1][j-1]=distance(i-1,j-1)
        D[j-1][i-1]=D[i-1][j-1]
ans=10**9
for r_ in permutations(r):
    res=0
    for i in range(R-1):
        res+=D[r_[i]-1][r_[i+1]-1]
    ans=min(ans,res)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    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])
    return d

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

inf = 10**9
d = [[inf for i in range(N+1)] for i in range(N+1)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(M):
    a, b, c = map(int, input().split())
    d[a][b] = c
    d[b][a] = c
for i in range(1, N+1):
    d[i][i] = 0 #自身のところに行くコストは０
warshall_floyd(d)
ans = inf
for v in itertools.permutations(rs, R):
    dist = 0
    for i in range(R-1):
        dist += d[v[i]][v[i+1]]
    if dist <= ans:
        ans = dist
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
def w_f(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())
LR = map(int,input().split())
d = [[float("inf") for i in range(n)] for i in range(n)]
for i in range(m):
    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 

D = w_f(d)
lr = list(itertools.permutations(LR))
ans = float("inf")
for li in lr:
    jd = 0
    for i in range(r-1):
        jd += D[li[i]-1][li[i+1]-1]
    
    if jd < ans:
        ans = jd
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,r = map(int,input().split())
r = list(map(int,input().split()))
node = [list(map(int,input().split())) for _ in range(m)]
dic = {}
for i in range(1,n+1):
    dic[i] = {}
    for j in range(1,n+1):
        dic[i][j]=10**6
for a,b,c in node:
    dic[a][b] = c
    dic[b][a] = c
dp = [[10**8]*(n+1) for _ in range(n+1)]
for i in range(n+1):
    dp[0][i] = 0
for i in range(1,n+1):
    for j in range(1,n+1):
        dp[i][j] = dic[i][j]
        for k in range(1,n+1):
            dp[i][j] = min(dp[i][j], dic[i][k]+dic[k][j])
def dfs(dv,nv,cost):
    if sum(dv)==len(dv):
        return cost
    ret = []
    for i in range(len(dv)):
        if dv[i]==1:
            continue
        dv_ = dv.copy()
        dv_[i] = 1
        ret.append(dfs(dv_,r[i],cost+dp[nv][r[i]]))
    return min(ret)
print(dfs([0]*len(r),0,0))

Submission status: Time Limit Exceeded

Solution code:
import itertools

n,m,l=map(int,input().split())
arr=list(map(int,input().split()))
d=[[10**10 for i in range(n)] for j in range(n)]
for i in range(m):
  u,v,w=map(int,input().split())
  d[u-1][v-1]=w
  d[v-1][u-1]=w
for i in range(n):
  d[i][i]=0
for i in range(n):
  for j in range(n):
    for k in range(n):
      if d[j][k]>=d[j][i]+d[i][k]:
        d[j][k]=d[j][i]+d[i][k]
c=list(itertools.permutations(arr,min(8,l)))
ans=10**10
for i in c:
  tmp=0
  for j in range(min(8,l)-1):
    tmp+=d[i[j]-1][i[j+1]-1]
  ans=min(tmp,ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M, R = map(int, input().split())
R_LIST = list(map(int, input().split()))
ABC = []
for _ in range(M):
    a,b,c = map(int, input().split())
    ABC.append((a,b,c))
    
edges = ABC[:]

# 無効グラフなので双方向にする
graph = {}
for a,b,c in edges:
    if not a in graph:
        graph[a] = {}
    if not b in graph:
        graph[b] = {}
    graph[a][b] = c
    graph[b][a] = c


from heapq import heappush, heappop

def dijkstra(graph, start):
    A = [None] * (N+1)
    queue = [(0, start)]
    while queue:
        path_len, v = heappop(queue)
        if A[v] is None: # v is unvisited
            A[v] = path_len
            for w, edge_len in graph[v].items():
                if A[w] is None:
                    heappush(queue, (path_len + edge_len, w))

    # to give same result as original, assign zero distance to unreachable vertices             
    return [0 if x is None else x for x in A]


shortest = [[0] * (N+1)]
for i in range(1, N+1):
    shortest.append(dijkstra(graph, i))
    
#print(shortest)

import sys
INT_MAX = sys.maxsize # 9223372036854775807
ans = INT_MAX

import itertools
line = R_LIST
for l in itertools.permutations(line):
    #print(l)
    tmp_len = 0
    for a,b in zip(l[:-1], l[1:]):
        tmp_len += shortest[a][b]

    #print(tmp_len)
    ans = min(ans, tmp_len)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M, R = map(int, input().split())
R_LIST = list(map(int, input().split()))
ABC = []
for _ in range(M):
    a,b,c = map(int, input().split())
    ABC.append((a,b,c))
    
    

    
edges = ABC[:]


def warshall_floyd(d, n):
    # d: グラフ二次元リスト
    # n: 頂点数 (0始まり)
    #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

# グラフ無効グラフ化
graph = [[float("inf") for i in range(N+1)] for i in range(N+1)] 
for x,y,z in edges:
    graph[x][y] = z
    graph[y][x] = z
for i in range(N+1):
    graph[i][i] = 0 #自身のところに行くコストは０

#最短経路
shortest =  warshall_floyd(graph, N+1)
    
# 順列全探索
import sys
INT_MAX = sys.maxsize # 9223372036854775807
ans = INT_MAX

import queue

rest = set(R_LIST[:])

import copy  
def dfs(cost,pre,rest):
    if len(rest) == 0:
        return cost
    
    ret = INT_MAX
    for r in rest:
        if pre == None:
            next_cost = 0
        else:
            next_cost = cost + shortest[pre][r]
        next_rest = copy.copy(rest)
        next_rest.remove(r)
        
        tmp_ret = dfs(next_cost, r, next_rest)
        ret = min(ret, tmp_ret)
        
    return ret
        
    

print(dfs(0, None, rest))