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:
# -*- coding: utf-8 -*-
"""
Created on Sun Oct  7 22:06:12 2018
ABC073D
@author: maezawa
"""
import itertools as itr
import sys
input = sys.stdin.readline

n, m, r = list(map(int, input().split()))
rarray = list(map(int, input().split()))
adjmatrix = [[float("inf")]*n for _ in range(n)]
#for i in range(n):
#    adjmatrix[i][i] = 0

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

#print(abc)

# Warshall-Floyd Algorithm
for k in range(len(adjmatrix)):
    for i in range(len(adjmatrix)):
        for j in range(len(adjmatrix[i])):
            if adjmatrix[i][j] > adjmatrix[i][k] + adjmatrix[k][j]:
                adjmatrix[i][j] = adjmatrix[i][k] + adjmatrix[k][j]
                adjmatrix[j][i] = adjmatrix[i][k] + adjmatrix[k][j]				

        
#print(*adjmatrix, sep='\n')
    
# search for ri to rj
mincnt = float("inf")
for route in itr.permutations(rarray):
    cnt = 0
    for i in range(len(route)-1):
        cnt += adjmatrix[route[i]-1][route[i+1]-1]
    if cnt < mincnt:
        mincnt = cnt

print(mincnt)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Oct  7 22:06:12 2018
ABC073D
@author: maezawa
"""
import itertools as itr
import sys
input = sys.stdin.readline

n, m, r = list(map(int, input().split()))
rarray = list(map(int, input().split()))
adjmatrix = [[float("inf")]*n for _ in range(n)]
#for i in range(n):
#    adjmatrix[i][i] = 0

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

#print(abc)

# Warshall-Floyd Algorithm
for k in range(len(adjmatrix)):
    for i in range(len(adjmatrix)):
        for j in range(len(adjmatrix[i])):
            if adjmatrix[i][j] > adjmatrix[i][k] + adjmatrix[k][j]:
                adjmatrix[i][j] = adjmatrix[i][k] + adjmatrix[k][j]
                adjmatrix[j][i] = adjmatrix[i][k] + adjmatrix[k][j]				

        
#print(*adjmatrix, sep='\n')
    
# search for ri to rj
mincnt = float("inf")
for route in itr.permutations(rarray):
    cnt = 0
    for i in range(len(rarray)-1):
        cnt += adjmatrix[route[i]-1][route[i+1]-1]
    if cnt < mincnt:
        mincnt = cnt

print(mincnt)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Oct  7 22:06:12 2018
ABC073D
@author: maezawa
"""
import itertools as itr
import sys
input = sys.stdin.readline

n, m, r = list(map(int, input().split()))
rarray = list(map(int, input().split()))
adjmatrix = [[float("inf")]*n for _ in range(n)]
#for i in range(n):
#    adjmatrix[i][i] = 0

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

#print(abc)

# Warshall-Floyd Algorithm
#for k in range(len(adjmatrix)):
#    for i in range(len(adjmatrix)):
#        for j in range(len(adjmatrix)):
#            if adjmatrix[i][j] > adjmatrix[i][k] + adjmatrix[k][j]:
#                adjmatrix[i][j] = adjmatrix[i][k] + adjmatrix[k][j]
#                adjmatrix[j][i] = adjmatrix[i][k] + adjmatrix[k][j]
#
for k in range(len(adjmatrix)):
    for i in range(len(adjmatrix)):
        for j in range(len(adjmatrix[i])):
            if adjmatrix[i][j] > adjmatrix[i][k] + adjmatrix[k][j]:
                adjmatrix[i][j] = adjmatrix[i][k] + adjmatrix[k][j]
                adjmatrix[j][i] = adjmatrix[i][k] + adjmatrix[k][j]				

        
#print(*adjmatrix, sep='\n')
    
# search for ri to rj
mincnt = 10*10
for route in itr.permutations(rarray):
    cnt = 0
    for i in range(len(rarray)-1):
        cnt += adjmatrix[route[i]-1][route[i+1]-1]
    if cnt < mincnt:
        mincnt = cnt

print(mincnt)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Oct  7 22:06:12 2018
ABC073D
@author: maezawa
"""
import itertools as itr
import sys
input = sys.stdin.readline

n, m, r = list(map(int, input().split()))
rarray = list(map(int, input().split()))
adjmatrix = [[float("inf")]*n for _ in range(n)]
#for i in range(n):
#    adjmatrix[i][i] = 0

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

#print(abc)

# Warshall-Floyd Algorithm
for k in range(n):
    for i in range(n):
        for j in range(n):
            if adjmatrix[i][j] > adjmatrix[i][k] + adjmatrix[k][j]:
                adjmatrix[i][j] = adjmatrix[i][k] + adjmatrix[k][j]
                adjmatrix[j][i] = adjmatrix[i][k] + adjmatrix[k][j]
        
#print(*adjmatrix, sep='\n')
    
# search for ri to rj
mincnt = 10*10
for route in itr.permutations(rarray):
    cnt = 0
    for i in range(len(rarray)-1):
        cnt += adjmatrix[route[i]-1][route[i+1]-1]
    if cnt < mincnt:
        mincnt = cnt

print(mincnt)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Oct  7 22:06:12 2018
ABC073D
@author: maezawa
"""
import itertools as itr
import sys
input = sys.stdin.readline

n, m, r = list(map(int, input().split()))
rarray = list(map(int, input().split()))
adjmatrix = [[10**10]*n for _ in range(n)]
#for i in range(n):
#    adjmatrix[i][i] = 0
    
for i in range(m):
    a, b, c = list(map(int, input().split()))
    adjmatrix[a-1][b-1] = c
    adjmatrix[b-1][a-1] = c

#print(abc)

# Warshall-Floyd Algorithm
for k in range(n):
    for i in range(n):
        for j in range(n):
            if adjmatrix[i][j] > adjmatrix[i][k] + adjmatrix[k][j]:
                adjmatrix[i][j] = adjmatrix[i][k] + adjmatrix[k][j]
                adjmatrix[j][i] = adjmatrix[i][k] + adjmatrix[k][j]
        
#print(*adjmatrix, sep='\n')
    
# search for ri to rj
mincnt = 10*10
for route in itr.permutations(rarray):
    cnt = 0
    for i in range(len(rarray)-1):
        cnt += adjmatrix[route[i]-1][route[i+1]-1]
    if cnt < mincnt:
        mincnt = cnt

print(mincnt)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Oct  7 22:06:12 2018
ABC073D
@author: maezawa
"""
import itertools as itr
import sys
input = sys.stdin.readline

n, m, r = list(map(int, input().split()))
rarray = list(map(int, input().split()))
adjmatrix = [[10**10]*n for _ in range(n)]
for i in range(n):
    adjmatrix[i][i] = 0
    
for i in range(m):
    a, b, c = list(map(int, input().split()))
    if adjmatrix[a-1][b-1] > c:
        adjmatrix[a-1][b-1] = c
        adjmatrix[b-1][a-1] = c

#print(abc)

# Warshall-Floyd Algorithm
for k in range(n):
    for i in range(n):
        for j in range(n):
            sc = adjmatrix[i][k] + adjmatrix[k][j]
            if sc < adjmatrix[i][j]:
                adjmatrix[i][j] = sc
                adjmatrix[j][i] = sc
        
#print(*adjmatrix, sep='\n')
    
# search for ri to rj
mincnt = 10*10
for route in itr.permutations(rarray):
    cnt = 0
    for i in range(len(rarray)-1):
        cnt += adjmatrix[route[i]-1][route[i+1]-1]
    if cnt < mincnt:
        mincnt = cnt

print(mincnt)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-# -*- coding: utf-8 -*-
"""
Created on Sun Oct  7 22:06:12 2018
ABC073D
@author: maezawa
"""
import itertools as itr
import sys
input = sys.stdin.readline

n, m, r = list(map(int, input().split()))
rarray = list(map(int, input().split()))
adjmatrix = [[10**10]*(n+1) for _ in range(n+1)]
for i in range(1,n+1):
    adjmatrix[i][i] = 0
    
for i in range(m):
    a, b, c = list(map(int, input().split()))
    if adjmatrix[a][b] > c:
        adjmatrix[a][b] = c
        adjmatrix[b][a] = c

#print(abc)

# Warshall-Floyd Algorithm
for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(i+1,n+1):
            adjmatrix[i][j] = min([adjmatrix[i][j],
                      adjmatrix[i][k] + adjmatrix[k][j]])
            adjmatrix[j][i] = adjmatrix[i][j]
        
#print(*adjmatrix, sep='\n')
    
# search for ri to rj
mincnt = 10*10
for route in itr.permutations(rarray):
    cnt = 0
    for i in range(len(rarray)-1):
        cnt += adjmatrix[route[i]][route[i+1]]
    if cnt < mincnt:
        mincnt = cnt

print(mincnt)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Oct  7 22:06:12 2018
ABC073D
@author: maezawa
"""
import itertools as itr
import sys
input = sys.stdin.readline

n, m, r = list(map(int, input().split()))
rarray = list(map(int, input().split()))
adjmatrix = [[10**10]*(n+1) for _ in range(n+1)]
for i in range(1,n+1):
    adjmatrix[i][i] = 0
    
for i in range(m):
    a, b, c = list(map(int, input().split()))
    if adjmatrix[a][b] > c:
        adjmatrix[a][b] = c
        adjmatrix[b][a] = c

#print(abc)

# Warshall-Floyd Algorithm
for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            adjmatrix[i][j] = min([adjmatrix[i][j],
                      adjmatrix[i][k] + adjmatrix[k][j]])
            #adjmatrix[j][i] = adjmatrix[i][j]
        
#print(*adjmatrix, sep='\n')
    
# search for ri to rj
mincnt = 10*10
for route in itr.permutations(rarray):
    cnt = 0
    for i in range(len(rarray)-1):
        cnt += adjmatrix[route[i]][route[i+1]]
    if cnt < mincnt:
        mincnt = cnt

print(mincnt)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Oct  7 22:06:12 2018
ABC073D
@author: maezawa
"""
import itertools as itr
import sys
#input = sys.stdin.readline

n, m, r = list(map(int, input().split()))
rarray = list(map(int, input().split()))
adjmatrix = [[10**10]*(n+1) for _ in range(n+1)]
for i in range(1,n+1):
    adjmatrix[i][i] = 0
    
for i in range(m):
    a, b, c = list(map(int, input().split()))
    if adjmatrix[a][b] > c:
        adjmatrix[a][b] = c
        adjmatrix[b][a] = c

#print(abc)

# Warshall-Floyd Algorithm
for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            adjmatrix[i][j] = min([adjmatrix[i][j],
                      adjmatrix[i][k] + adjmatrix[k][j]])
            #adjmatrix[j][i] = adjmatrix[i][j]
        
#print(*adjmatrix, sep='\n')
    
# search for ri to rj
mincnt = 10*10
for route in itr.permutations(rarray):
    cnt = 0
    for i in range(len(rarray)-1):
        cnt += adjmatrix[route[i]][route[i+1]]
    if cnt < mincnt:
        mincnt = cnt

print(mincnt)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Oct  7 22:06:12 2018
ABC073D
@author: maezawa
"""
import itertools as itr
import sys
input = sys.stdin.readline

n, m, r = list(map(int, input().split()))
rarray = list(map(int, input().split()))
adjmatrix = [[10**10]*(n+1) for _ in range(n+1)]
for i in range(m):
    a, b, c = list(map(int, input().split()))
    if adjmatrix[a][b] > c:
        adjmatrix[a][b] = c
        adjmatrix[b][a] = c

#print(abc)

# Warshall-Floyd Algorithm
for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            if i == j:
                adjmatrix[i][j] = 0
            if adjmatrix[i][j] > adjmatrix[i][k] + adjmatrix[k][j]:
                adjmatrix[i][j] = adjmatrix[i][k] + adjmatrix[k][j]
                #adjmatrix[j][i] = adjmatrix[j][k] + adjmatrix[k][i]
        
#print(*adjmatrix, sep='\n')
    
# search for ri to rj
mincnt = 10*10
for route in itr.permutations(rarray):
    cnt = 0
    for i in range(len(rarray)-1):
        cnt += adjmatrix[route[i]][route[i+1]]
    if cnt < mincnt:
        mincnt = cnt

print(mincnt)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Oct  7 22:06:12 2018
ABC073D
@author: maezawa
"""
import itertools as itr

n, m, r = list(map(int, input().split()))
rarray = list(map(int, input().split()))
abc = []
adjmatrix = [[10**10]*(n+1) for _ in range(n+1)]
for i in range(m):
    abci = list(map(int, input().split()))
    abc.append(abci)
    adjmatrix[abci[0]][abci[1]] = abci[2]
    adjmatrix[abci[1]][abci[0]] = abci[2]

#print(abc)

# Warshall?Floyd Algorithm
for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            if i == j:
                adjmatrix[i][j] = 0
            if adjmatrix[i][j] > adjmatrix[i][k] + adjmatrix[k][j]:
                adjmatrix[i][j] = adjmatrix[i][k] + adjmatrix[k][j]
        
#print(*adjmatrix, sep='\n')
    
# search for ri to rj
mincnt = 10*10
for route in itr.permutations(rarray):
    cnt = 0
    for i in range(len(rarray)-1):
        cnt += adjmatrix[route[i]][route[i+1]]
    if cnt < mincnt:
        mincnt = cnt

print(mincnt)

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')
graph = [[INF for i in range(N)] for j in range(N)]
for i 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

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

ans = 10**9
for p in permutations(r, len(r)):
    dist = 0
    flag = 0
    for i in range(len(r) - 1):
        if graph[p[i]-1][p[i+1]-1] == INF:
            flag = 1
            continue
        dist += graph[p[i]-1][p[i+1]-1]
    if flag == 0:
        ans = min(ans, dist)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import permutations
from heapq import heappush, heappop

def dijkstra(graph:list, node:int, start:int) -> list:
    # 未探索のノードは距離INF
    INF = float("inf")
    dist = [INF]*node
    
    # 始点ノードの距離を0とし、dfsのためのpriority queを作成
    dist[start] = 0
    heap = [(0,start)]
    
    # 未探索のノードをpriority queueに入れる
    while heap:
        cost, cur_node = heappop(heap)
        
        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heappush(heap, (dist[nex_node], nex_node))
    
    return dist

n,m,r = li()
r = list(li_())
graph = [[] for _ in range(n)]
for _ in range(m):
    a,b,c = li()
    a -= 1
    b -= 1
    graph[a].append((c,b))
    graph[b].append((c,a))
    
dists = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    dists[i] = dijkstra(graph, n, i)

routes = list(permutations(r))

ans = 2**64-1
for route in routes:
    temp = 0
    for i in range(len(route)-1):
        temp += dists[route[i]][route[i+1]]
        
    ans = min(ans,temp)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

import itertools

INF = float('inf')


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


def dijkstra(graph, start):
    MAX_SIZE = len(graph)
    visited = [False for _ in range(MAX_SIZE)]
    cost = [INF for _ in range(MAX_SIZE)]
    prev = [None for _ in range(MAX_SIZE)]

    cost[start] = 0
    prev[start] = start
    path = [start + 1]
    while True:
        min_cost = INF
        next = -1
        visited[start] = True
        # 頂点の選択
        for i in range(MAX_SIZE):
            if visited[i]: continue # 探索済みの頂点は飛ばす
            if graph[start][i]: # 頂点startと接続されているか判定
                dist = cost[start] + graph[start][i]
                if dist < cost[i]:
                    cost[i] = dist
                    prev[i] = start

            if cost[i] < min_cost:
                min_cost = cost[i]
                next = i

        start = next
        path.append(next + 1)
        if next == -1: break

    # print(cost)
    # print(path)
    return cost


def main():
    N, M, R = inpl()
    r = inpl()

    G = [[None for _ in range(N)] for _ in range(N)]
    for i in range(M):
        a, b, c = inpl()
        G[a - 1][b - 1] = c
        G[b - 1][a - 1] = c

    ans = INF
    for root in itertools.permutations(r, R):
        dist = 0
        for i in range(R - 1):
            dist += dijkstra(G, root[i] - 1)[root[i + 1] - 1]
        ans = min(ans, dist)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# ABC 073 D
import itertools

N, M, R = map(int,input().split())
s = list(map(int,input().split()))
D = [[10**9+7 for k in range(N)] for l in range(N)]
for k in range(N):
    D[k][k] = 0
for k in range(M):
    A, B, C = map(int,input().split())
    A -= 1
    B -= 1
    D[A][B] = C
    D[B][A] = C

for p in range(N):
    for q in range(N):
        for r in range(N):
            D[q][r] = min(D[q][r], D[q][p]+D[p][r])

cities = list(itertools.permutations(s))
ans = 10**9+7
for p in cities:
    t = 0
    for k in range(R-1):
        t += D[p[k]-1][p[k+1]-1]
    ans = min(ans,t)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from itertools import permutations

inf = 10**7
n,m,r = map(int, input().split())
rr = [int(x) for x in input().split()]
a = []
b = []
c = []
d = [[inf for _ in range(n)] for _ in range(n)]
for _ in range(m):
    aa,bb,cc = map(int, input().split())
    aa -= 1
    bb -= 1
    a.append(aa)
    b.append(bb)
    c.append(cc)
    d[aa][aa] = 0
    d[bb][bb] = 0
    d[aa][bb] = cc
    d[bb][aa] = cc

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

ret = inf
for l in permutations(rr):
    tmp = 0
    for i in range(r-1):
        tmp += d[l[i]-1][l[i+1]-1]
    if tmp < ret:
        ret = tmp

print(ret)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from itertools import permutations

inf = 10**30
n,m,r = map(int, input().split())
rr = [int(x) for x in input().split()]
a = []
b = []
c = []
d = [[inf for _ in range(n)] for _ in range(n)]
for _ in range(m):
    aa,bb,cc = map(int, input().split())
    aa -= 1
    bb -= 1
    a.append(aa)
    b.append(bb)
    c.append(cc)
    d[aa][aa] = 0
    d[bb][bb] = 0
    d[aa][bb] = cc
    d[bb][aa] = cc

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

ret = inf
for l in permutations(rr):
    tmp = 0
    for i in range(r-1):
        tmp += d[l[i]-1][l[i+1]-1]
    if tmp < ret:
        ret = tmp

print(ret)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)

N, M, R = map(int, input().split())
dest = list(map(int, input().split())) #訪れないと行けない街r1, r2, ..., rR

d = [[float('inf')] * 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

#ワーシャルフロイト法
#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])

c = [[d[dest[i] - 1][dest[j] - 1] for j in range(R)] for i in range(R)]

dp_memo = [[float('inf')] * R for _ in range(1 << R)]

def TSP(T, v):
    #今まで訪れた頂点の集合：T　今いる頂点：vとしたときの残りを全部巡回する最短の長さ

    if dp_memo[T][v] != float('inf'):
        return dp_memo[T][v]

    elif T == (1 << R) - 1 :
        #全部訪れたとき
        dp_memo[T][v] = 0
        return 0
    else:
        res = float('inf')
        for u in range(R):
            if (T >> u) & 1 == 0:
                res = min(res, TSP(T | (1 << u), u) + c[v][u])
        dp_memo[T][v] = res
        return res

ans = float('inf')
for i in  range(R):
    ans = min(ans, TSP(0, i))
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 = [[1000000 for i in range(N)] for j in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    DP[a - 1][b - 1] = c
    DP[b - 1][a - 1] = c

for i in range(N):
    for j in range(N):
        for k in range(N):
            DP[i][j] = min([DP[i][j], DP[i][k] + DP[k][j]])
ans = 0
for i in range(1, R):
    ans += DP[r[i - 1] - 1][r[i] - 1]


root = list(itertools.permutations(r))
finalans = 100000000
for i in root:
    ans = 0
    for j in range(1, R):
        ans += DP[i[j - 1] - 1][i[j] - 1]
    if ans < finalans:
        finalans = ans
        
print(finalans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, factorial
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def main():
    N, M, R = map(int, input().split())
    R = list(map(lambda x: int(x) - 1, input().split()))

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

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

    for m in range(N):
        for s in range(N):
            for e in range(N):
                if matrix[s][m] != INF and matrix[m][e] != INF:
                    matrix[s][e] = min(matrix[s][e], matrix[s][m] + matrix[m][e])

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

d = [[float('inf') for _ in range(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
for i in range(N):
    d[i][i]=0
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 = float('inf')
for seq in permutations(r):
    s = 0
    for j in range(R-1):
        s += d[seq[j]-1][seq[j+1]-1]
    ans = min(ans,s)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
import heapq

INF = float('inf')
n, m, R = list(map(int, input().split()))
r = list(map(int, input().split()))

cost = {}
for i in range(m):
    a, b, c = list(map(int, input().split()))
    if not a in cost.keys():
        cost[a] = [(b, c)]
    else:
        cost[a].append((b, c))
    if not b in cost.keys():
        cost[b] = [(a, c)]
    else:
        cost[b].append((a, c))
        
dist = [[INF]*(n+1) for _ in range(n+1)]
for st in range(1, n+1):
    d = [INF]*(n+1)
    d[st] = 0
    path = [(0, st)]
    heapq.heapify(path)
    while len(path) > 0:
        c, node = heapq.heappop(path)
        if d[node] < c:
            continue
        d[node] = c
        for node_next, c_next in cost[node]:
            if d[node]+c_next < d[node_next]:
                heapq.heappush(path, (d[node]+c_next, node_next))
    dist[st] = d
# for d in dist: print(d)

ans = INF
for p in permutations(r):
    ans_ = 0
    for i in range(R-1):
        ans_ += dist[p[i]][p[i+1]]
    ans = min(ans, ans_)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
import heapq

INF = float('inf')
n, m, R = list(map(int, input().split()))
r = list(map(int, input().split()))

cost = {}
for i in range(m):
    a, b, c = list(map(int, input().split()))
    if not a in cost.keys():
        cost[a] = [(b, c)]
    else:
        cost[a].append((b, c))
    if not b in cost.keys():
        cost[b] = [(a, c)]
    else:
        cost[b].append((a, c))
        
dist = [[INF]*(n+1) for _ in range(n+1)]
for st in range(1, n+1):
    d = [INF]*(n+1)
    d[st] = 0
    path = [(0, st)]
    heapq.heapify(path)
    while len(path) > 0:
        c, node = heapq.heappop(path)
        if d[node] < c:
            continue
        d[node] = c
        for node_next, c_next in cost[node]:
            heapq.heappush(path, (d[node]+c_next, node_next))
    dist[st] = d
# for d in dist: print(d)

ans = INF
for p in permutations(r):
    ans_ = 0
    for i in range(R-1):
        ans_ += dist[p[i]][p[i+1]]
    ans = min(ans, ans_)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
import sys
INF = float('inf')
n, m, R = map(int, sys.stdin.readline().split())
r = [i-1 for i in map(int, sys.stdin.readline().split())]
dist = [[INF]*n for _ in range(n)]
for i in range(n):
    dist[i][i] = 0
for i in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    dist[a-1][b-1] = c
    dist[b-1][a-1] = c
    
for k in range(n):
    for i in range(n):
        for j in range(n):
            if dist[i][j] > dist[i][k]+dist[k][j]:
                dist[i][j] = dist[i][k]+dist[k][j]
# for d in dist: print(d)

ans = INF
for p in permutations(r):
    ans_ = 0
    for i in range(R-1):
        ans_ += dist[p[i]][p[i+1]]
    ans = min(ans, ans_)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
import sys
INF = float('inf')
n, m, R = map(int, sys.stdin.readline().split())
r = list(map(int, input().split()))
dist = [[INF]*(n+1) for _ in range(n+1)]
for i in range(n+1):
    dist[i][i] = 0
for i in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    dist[a][b] = c
    dist[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 dist[i][j] > dist[i][k]+dist[k][j]:
                dist[i][j] = dist[i][k]+dist[k][j]
# for d in dist: print(d)

ans = INF
for p in permutations(r):
    ans_ = 0
    for i in range(R-1):
        ans_ += dist[p[i]][p[i+1]]
    ans = min(ans, ans_)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
import sys
INF = float('inf')
n, m, R = map(int, sys.stdin.readline().split())
r = list(map(int, input().split()))
dist = [[INF]*(n+1) for _ in range(n+1)]
for i in range(n+1):
    dist[i][i] = 0
for i in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    dist[a][b] = c
    dist[b][a] = c
    
for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
# for d in dist: print(d)

ans = INF
for p in permutations(r):
    ans_ = 0
    for i in range(R-1):
        ans_ += dist[p[i]][p[i+1]]
    ans = min(ans, ans_)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
INF = float('inf')
n, m, R = map(int, input().split())
r = list(map(int, input().split()))
dist = [[INF]*(n+1) for _ in range(n+1)]
for i in range(n+1):
    dist[i][i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    dist[a][b] = c
    dist[b][a] = c
    
for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(i, n+1):
            dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
            dist[j][i] = dist[i][j]
# for d in dist: print(d)

ans = INF
for p in permutations(r):
    ans_ = 0
    for i in range(R-1):
        ans_ += dist[p[i]][p[i+1]]
    if ans_ > ans:
	    break
    ans = min(ans, ans_)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
INF = 10**8
n, m, R = list(map(int, input().split()))
r = list(map(int, input().split()))
dist = [[INF]*n for _ in range(n)]
for i in range(n):
    dist[i][i] = 0
for i in range(m):
    a, b, c = list(map(int, input().split()))
    dist[a-1][b-1] = c
    dist[b-1][a-1] = 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])
# for d in dist: print(d)

ans = INF
for p in permutations(r):
    ans_ = 0
    for i in range(R-1):
        ans_ += dist[p[i]-1][p[i+1]-1]
    ans = min(ans, ans_)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
INF = 10**8
n, m, R = list(map(int, input().split()))
r = list(map(int, input().split()))
dist = [[INF]*(n+1) for _ in range(n+1)]
for i in range(1, n+1):
    dist[i][i] = 0
for i in range(m):
    a, b, c = list(map(int, input().split()))
    dist[a][b] = c
    dist[b][a] = c
    
for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
# for d in dist: print(d)

ans = INF
for p in permutations(r):
    ans_ = 0
    for i in range(R-1):
        ans_ += dist[p[i]][p[i+1]]
    ans = min(ans, ans_)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
"""
atcoder workspace
"""
from itertools import permutations

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

Dmat = [[1e9] * N for i in range(N)]

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

for i in range(M):
    f, t, c = map(int, input().split())
    Dmat[f-1][t-1] = c
    Dmat[t-1][f-1] = c

for i in range(N): #mid
    for j in range(N): #from
        for k in range(N): #to
            Dmat[j][k] = min(Dmat[j][k], Dmat[j][i] + Dmat[i][k])

ans = 1e9
for p in permutations(Rlist):
    temp = 0
    for i in range(R-1):
        temp += Dmat[p[i]-1][p[i+1]-1]
    ans = min(ans, temp)

print(ans)