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:
#!/usr/bin/env python
# ワーシャルフロイド+全探索

import numpy as np
import itertools

def main():
    N, M, R = map(int, input().split())
    rs = map(int, input().split())
    inf = float('inf')
    cost = [[inf]*N for _ in range(N)]

    # グラフ作る
    for _ in range(M):
        a, b, c = map(int, input().split())
        cost[a-1][b-1] = c
        cost[b-1][a-1] = c
    
    # ワーシャルフロイドで全頂点間距離算出
    for k in range(N):
        for i in range(N):
            for j in range(N):
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])

    # 組み合わせ全探索
    ans = inf
    for route in itertools.permutations(rs):
        d = 0
        for i in range(R-1):
            d += cost[route[i]-1][route[i+1]-1]
        ans = min(ans, d)
    
    print(int(ans))


if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# ワーシャルフロイド+全探索

import numpy as np
import itertools

def main():
    N, M, R = map(int, input().split())
    rs = map(int, input().split())
    cost = np.empty((N, N))
    cost[:] = np.inf

    # グラフ作る
    for _ in range(M):
        a, b, c = map(int, input().split())
        cost[a-1, b-1] = c
        cost[b-1, a-1] = c
    
    # ワーシャルフロイドで全頂点間距離算出
    for k in range(N):
        for i in range(N):
            for j in range(N):
                cost[i, j] = min(cost[i, j], cost[i, k] + cost[k, j])

    # 組み合わせ全探索
    ans = float('inf')
    for route in itertools.permutations(rs):
        d = 0
        for i in range(len(route)-1):
            d += cost[route[i]-1, route[i+1]-1]
        ans = min(ans, d)
    
    print(int(ans))


if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# ワーシャルフロイド+全探索

import numpy as np
import itertools

def main():
    N, M, R = map(int, input().split())
    rs = map(int, input().split())
    graph = np.zeros((N, N))
    
    # グラフ作る
    for _ in range(M):
        a, b, c = map(int, input().split())
        graph[a-1, b-1] = c
        graph[b-1, a-1] = c
    
    # ワーシャルフロイドで全頂点間距離算出
    cost = np.zeros((N, N))
    for i in range(N):
        for j in range(N):
            if i==j:
                cost[i, j] = 0
                cost[j, i] = 0
            elif graph[i, j] == 0:
                cost[i, j] = float('inf')
            else:
                cost[i, j] = graph[i, j]
    for k in range(N):
        for i in range(N):
            for j in range(N):
                cost[i, j] = min(cost[i, j], cost[i, k] + cost[k, j])

    # 組み合わせ全探索
    ans = float('inf')
    for route in itertools.permutations(rs, R):
        d = 0
        for i in range(len(route)-1):
            d += cost[route[i]-1, route[i+1]-1]
        ans = min(ans, d)
    
    print(int(ans))


if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

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

G = [[float('inf')] * N for _ in xrange(N)]

for i in xrange(N):
    G[i][i] = 0

for i in range(M):
    A, B, C = map(int, sys.stdin.readline().split())
    G[A-1][B-1] =  G[B-1][A-1] = C

# Warshall–Floyd Algorithm
for k in xrange(N):
    for i in xrange(N):
        for j in xrange(N):
            G[i][j] = min(G[i][j], G[i][k] + G[k][j]); 

ans = float('inf')

for i in permutations(r):
    ans = min(ans, sum([G[i[j]][i[j+1]] for j in xrange(R-1)]))

print ans

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

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

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

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

for i in range(M):
    A, B, C = map(int, sys.stdin.readline().split())
    G[A-1][B-1] =  G[B-1][A-1] = C

# Warshall–Floyd Algorithm
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 = float('inf')

for i in permutations(r):
    ans = min(ans, sum([G[i[j]][i[j+1]] for j in range(R-1)]))

print ans

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

from itertools import permutations

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

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

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

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

# Warshall–Floyd Algorithm
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 = float('inf')

for i in permutations(r):
    ans = min(ans, sum([G[i[j]][i[j+1]] for j in range(R-1)]))

print ans

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

from itertools import permutations

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

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

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

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

# Warshall–Floyd Algorithm
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 = float('inf')

for i in permutations(r):
    t = 0
    for j in range(R-1):
        t += G[i[j]][i[j+1]]

    ans = min(ans, t)

print ans

Submission status: Time Limit Exceeded

Solution code:
import heapq
import itertools
N,M,R=map(int, raw_input().split())
r=map(int, raw_input().split())

cost=[ [ float("inf") for i in range(N+1)] for i in range(N+1) ]
nl=[ [] for i in range(N+1) ]

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


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


def Dij(start):

	#Initialize
	d=[float("inf") for i in range(N+1)]
	d[start]=0
	q=[]
	heapq.heappush(q,(0,start))
	
	while len(q)!=0:
		tmp=heapq.heappop(q)
		u=tmp[1]

		for v in nl[u]:
			alt=d[u]+cost[u][v]
			if d[v]>alt:
				d[v]=alt
				heapq.heappush(q,(alt,v))
	return d


l=list(itertools.permutations(r))

C=[[]]
for i in range(1,N+1):
	C.append(Dij(i))

ans=float("inf")


for i in l:
	dist=0
	for j in range(R):
		if j==0:
			prev=i[j]
			continue
		cur=i[j]
		dist+=C[prev][cur]
		prev=cur
	ans=min(ans,dist)

print ans

Submission status: Time Limit Exceeded

Solution code:
import heapq
import itertools
N,M,R=map(int, raw_input().split())
r=map(int, raw_input().split())

cost=[ [ float("inf") for i in range(N+1)] for i in range(N+1) ]
nl=[ [] for i in range(N+1) ]

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


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


def Dij(start):

	#Initialize
	d=[float("inf") for i in range(N+1)]
	d[start]=0
	q=[]
	heapq.heappush(q,(0,start))
	
	while len(q)!=0:
		tmp=heapq.heappop(q)
		u=tmp[1]

		for v in nl[u]:
			alt=d[u]+cost[u][v]
			if d[v]>alt:
				d[v]=alt
				heapq.heappush(q,(alt,v))
	return d


l=list(itertools.permutations(r))


ans=float("inf")

for i in l:
	dist=0
	for j in range(R):
		if j==0:
			prev=i[j]
			continue
		cur=i[j]
		d=Dij(prev)
		dist+=d[cur]
		prev=cur
	ans=min(ans,dist)

print ans

Submission status: Time Limit Exceeded

Solution code:
import itertools
N,M,R=map(int, raw_input().split())
r=map(int, raw_input().split())

dp=[ [ float("inf") for i in range(N+1)] for i in range(N+1) ]

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

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


for k in range(N+1):
	for x in range(N+1):
		for y in range(N+1):
			dp[x][y]=min( dp[x][y], dp[x][k]+dp[k][y] )


l=list(itertools.permutations(r))


ans=float("inf")

for i in l:
	dist=0
	for j in range(R):
		if j==0:
			prev=i[j]
			continue
		cur=i[j]
		dist+=dp[prev][cur]
		prev=cur
	ans=min(ans,dist)

print ans

Submission status: Time Limit Exceeded

Solution code:
import itertools

n, m, r = map(int, input().split())
order = list(map(int, input().split()))
dist = [[float('inf') for _ in range(n + 1)] for _ in range(n + 1)]

for i in range(1, n + 1):
    dist[i][i] = 0

for _ 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(1, n + 1):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

ans = float('inf')
for perm in itertools.permutations(order):
    cur = 0
    for i in range(1, r):
        cur += dist[perm[i - 1]][perm[i]]

    ans = min(ans, cur)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from itertools import permutations, product
def inpl(): return tuple(map(int, input().split()))
N, M, R = inpl()
inf = float("inf")
G = [[inf for _ in range(N+1)] for _ in range(N+1)]
D = inpl() # destination

for _ in range(M):
    a, b, c = inpl()
    G[a][b] = c
    G[b][a] = c

for n in range(N+1):
    G[n][n] = 0

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

res = inf
for C in permutations(D, len(D)):
    res = min(res, sum([G[C[i]][C[i+1]] for i in range(len(D)-1)]))

print(res)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from itertools import permutations
def inpl(): return tuple(map(int, input().split()))
N, M, R = inpl()
inf = float("inf")
G = [[inf for _ in range(N+1)] for _ in range(N+1)]
D = inpl() # destination

for _ in range(M):
    a, b, c = inpl()
    G[a][b] = c
    G[b][a] = c

for n in range(N+1):
    G[n][n] = 0

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

res = inf
for C in permutations(D, len(D)):
    res = min(res, sum([G[C[i]][C[i+1]] for i in range(len(D)-1)]))

print(res)

Submission status: Time Limit Exceeded

Solution code:
n,m,r_=[int(i) for i in input().split()]
r=[int(i)-1 for i in input().split()]
abc=[[int(j)-1 for j in input().split()] for i in range(m)]
INF=999999999999
for i in range(m):
        abc[i][2]+=1

edge=[[INF for j in range(n)] for i in range(n)]
for root in abc:
        edge[root[0]][root[1]]=root[2]
        edge[root[1]][root[0]]=root[2]
#for e in edge:
#       print(e)
#print("...")
for k in range(n):
        for i in range(n):
                for j in range(n):
                        if i!=j:
                                edge[i][j]=min(edge[i][j],edge[i][k]+edge[k][j])
#for e in edge:
#       print(e)

def search(now,went):
        if went.count(False)==0:
                return 0
        ans=INF
        for i in range(len(went)):
                if not went[i]:
                        went[i]=True
                        ans=min(ans,search(r[i],went)+edge[now][r[i]])
                        #print("edge")
                        #print(edge[now][r[i]])
                        went[i]=False
        return ans

ans=INF
for i in range(r_):
        went=[False for j in range(r_)]
        went[i]=True
        #print(went)
        ans=min(ans,search(r[i],went))
#print("~~~")
#print(r)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def Warshall_Floyd(edges,N):
  for k in range(N):
    for i in range(N):
      for j in range(N):
        edges[i][j]=min(edges[i][j],edges[i][k]+edges[k][j])
  return edges

import itertools
N, M, R = map(int,input().split())
r = list(map(int,input().split()))
A=[[float("inf") for i in range(N)] for j in range(N)]
for m in range(M):
  a, b, c = map(int,input().split())
  A[a-1][b-1] = c
  A[b-1][a-1] = c
A = Warshall_Floyd(A,N)

ans = float("inf")
for road in list(itertools.permutations(r)):
  length = 0
  for i in range(R-1):
    length += A[road[i]-1][road[i+1]-1]
  ans = min(ans, length)
print(ans)

Submission status: Time Limit Exceeded

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

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

INF = 100000
matrix = [[INF for _ in range(N)] for _ in range(N)]
for _ in range(M):
    source, target, dist = map(int, input().split(" "))
    source -= 1
    target -= 1
    matrix[source][target] = matrix[target][source] = dist

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

shortest_len = INF
used = [False for _ in range(R)]

def dfs(used_r_num, prev_idx, dist):
    if used_r_num == R:
        global shortest_len
        if shortest_len > dist:
            shortest_len = dist
    else:
        for i in range(R):
            global used
            if not used[i]:
                used[i] = True
                if prev_idx == -1:
                    dfs(used_r_num + 1, i, 0)
                else:
                    source = rlist[i] - 1
                    target = rlist[prev_idx] - 1
                    dfs(used_r_num + 1, i, dist + matrix[source][target])
                used[i] = False
                
matrix = wf(matrix)
dfs(0, -1, 0)

print(shortest_len)

Submission status: Time Limit Exceeded

Solution code:
import sys
#sys.setrecursionlimit(n)
import heapq
from collections import defaultdict, deque
import itertools

import itertools
from heapq import heappop, heappush
N, M, R = map(int, input().split())

r = [int(i) for i in input().split()]
mp = defaultdict(lambda:defaultdict(list))
for _ in range(M):
    a, b, c= map(int, input().split())
    mp[a][b] = c
    mp[b][a] = c

v = [[float('inf')] * (N + 1) for _ in [0] * (N + 1)]
def dijkstra(start):
    q = []
    global v
    heapq.heappush(q, (0, start))
    vv = v[start]
    vv[start] = 0
    while(q):
        vc, vs = heapq.heappop(q)
        for i in mp[vs]:
            vsc = mp[vs][i]
            cost = vv[i]
            newcost = vsc + vc
            if cost > newcost:
                vv[i] = newcost
                heapq.heappush(q, (newcost, i))

ans = float('inf')
for i in range(N + 1):
    dijkstra(i)

ans = float('inf')
for i in itertools.permutations(r):
    t_ans = 0
    for j in range(R - 1):
        t_ans += v[i[j]][i[j + 1]]
    if ans > t_ans:
        ans = t_ans
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-        
import numpy as np
import itertools

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

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

graph = np.zeros((v,v)).astype('uint32')
path = np.zeros((v,v)).astype('uint32')

for i in range(v):
    for j in range(v):
            graph[i][j] = 0 if (i==j) else 999999
            path[i][j] = j
            
for i in range(e):
    src, dst, cost = a[i]-1, b[i]-1, c[i]
    graph[src][dst] = cost
    graph[dst][src] = cost

for k in range(v):
    for i in range(v):
        for j in range(v):
            if(graph[i][k]+graph[k][j]<graph[i][j]):
                graph[i][j] = graph[i][k]+graph[k][j]
                path[i][j] = path[i][k]
                
perm = list(itertools.permutations(r))
ans = 999999
for city in perm:
    tmp = 0
    for j in range(len(city)-1):
        tmp += graph[city[j]-1][city[j+1]-1]
    ans = min(ans,tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
import itertools

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

cmin = [[float('inf') for j in range(n)] for i in range(n)]
for i in range(n):
    cmin[i][i] = 0

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

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

minr = float('inf')
for routes in itertools.permutations(rs):
    total = 0
    start = routes[0]
    for i in range(1, r):
        total += cmin[start - 1][routes[i] - 1]
        start = routes[i]
    minr = min(minr, total)

print(minr)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
import itertools

def read_data():
    try:
        LOCAL_FLAG
        import codecs
        import os

        lines = []
        file_path = os.path.join(os.path.dirname(__file__), 'data073.dat')
        with codecs.open(file_path, 'r', 'utf-8') as f:
            lines.append(f.readline().rstrip("\r\n"))
            N, M, R = list(map(int, lines[0].split()))
            for i in range(M+1):
                lines.append(f.readline().rstrip("\r\n"))

    except NameError:
        lines = []
        lines.append(input())
        N, M, R = list(map(int, lines[0].split()))
        for i in range(M+1):
            lines.append(input())

    return lines

def dis(D, town_list):
    total = 0
    for i in range(len(town_list)-1):
        total += D[town_list[i]][town_list[i+1]]
    return total


def Travel():

    raw_data = read_data()
    N, M, R = list(map(int, raw_data[0].split()))
    town_list = list(map(int, raw_data[1].split()))
    road_set = set([])

    MAX = 200000
    D = np.zeros((N+1, N+1), dtype='int32')
    D += MAX

    for i in range(2, M+2):
        a, b, c = list(map(int, raw_data[i].split()))
        D[a][b] = c
        D[b][a] = c

    for k in range(1, N+1):
        for i in range(1, N+1):
            if(i == k):
                continue
            for j in range(i+1, N+1):
                if(j == k):
                    continue
                dis_two_node = D[i][k] + D[k][j]
                if dis_two_node < D[i,j]:
                    D[i,j] = dis_two_node
                    D[j,i] = dis_two_node
                

    # print(D)


    min_dis = MAX*8
    for each in itertools.permutations(town_list):
        min_dis = min(dis(D, each), min_dis)

    print(min_dis)




Travel()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
import itertools

def read_data():
    try:
        LOCAL_FLAG
        import codecs
        import os

        lines = []
        file_path = os.path.join(os.path.dirname(__file__), 'data073.dat')
        with codecs.open(file_path, 'r', 'utf-8') as f:
            lines.append(f.readline().rstrip("\r\n"))
            N, M, R = list(map(int, lines[0].split()))
            for i in range(M+1):
                lines.append(f.readline().rstrip("\r\n"))

    except NameError:
        lines = []
        lines.append(input())
        N, M, R = list(map(int, lines[0].split()))
        for i in range(M+1):
            lines.append(input())

    return lines

def dis(D, town_list):
    total = 0
    for i in range(len(town_list)-1):
        total += D[town_list[i]][town_list[i+1]]
    return total


def Travel():

    raw_data = read_data()
    N, M, R = list(map(int, raw_data[0].split()))
    town_list = list(map(int, raw_data[1].split()))
    road_set = set([])

    MAX = 200000
    D = np.zeros((N+1, N+1), dtype='int32')
    D += MAX

    for i in range(2, M+2):
        a, b, c = list(map(int, raw_data[i].split()))
        D[a][b] = c
        D[b][a] = c

    for k in range(1, N+1):
        for i in range(1, N+1):
            if(i == k):
                continue
            for j in range(1, N+1):
                if(j == k) or (j == i):
                    continue                
                dis_two_node = D[i][k] + D[k][j]
                if dis_two_node < D[i,j]:
                    D[i,j] = dis_two_node
                

    # print(D)


    min_dis = MAX*8
    for each in itertools.permutations(town_list):
        min_dis = min(dis(D, each), min_dis)

    print(min_dis)




Travel()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
import itertools

def read_data():
    try:
        LOCAL_FLAG
        import codecs
        import os

        lines = []
        file_path = os.path.join(os.path.dirname(__file__), 'data073.dat')
        with codecs.open(file_path, 'r', 'utf-8') as f:
            lines.append(f.readline().rstrip("\r\n"))
            N, M, R = list(map(int, lines[0].split()))
            for i in range(M+1):
                lines.append(f.readline().rstrip("\r\n"))

    except NameError:
        lines = []
        lines.append(input())
        N, M, R = list(map(int, lines[0].split()))
        for i in range(M+1):
            lines.append(input())

    return lines

def dis(D, town_list):
    total = 0
    for i in range(len(town_list)-1):
        total += D[town_list[i]][town_list[i+1]]
    return total


def Travel():

    raw_data = read_data()
    N, M, R = list(map(int, raw_data[0].split()))
    town_list = list(map(int, raw_data[1].split()))
    road_set = set([])

    MAX = 200000
    D = np.zeros((N+1, N+1), dtype='int32')
    D += MAX

    for i in range(2, M+2):
        a, b, c = list(map(int, raw_data[i].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):
                dis_two_node = D[i][k] + D[k][j]
                if dis_two_node < D[i,j]:
                    D[i,j] = dis_two_node

    # print(D)


    min_dis = MAX
    for each in itertools.permutations(town_list):
        min_dis = min(dis(D, each), min_dis)

    print(min_dis)




Travel()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
import math

def read_data():
    try:
        LOCAL_FLAG
        import codecs
        import os

        lines = []
        file_path = os.path.join(os.path.dirname(__file__), 'data073.dat')
        with codecs.open(file_path, 'r', 'utf-8') as f:
            lines.append(f.readline().rstrip("\r\n"))
            N, M, R = list(map(int, lines[0].split()))
            for i in range(M+1):
                lines.append(f.readline().rstrip("\r\n"))

    except NameError:
        lines = []
        lines.append(input())
        N, M, R = list(map(int, lines[0].split()))
        for i in range(M+1):
            lines.append(input())

    return lines

def dis(D, town_list):
    total = 0
    for i in range(len(town_list)-1):
        total += D[town_list[i]][town_list[i+1]]
    return total


def Travel():

    raw_data = read_data()
    N, M, R = list(map(int, raw_data[0].split()))
    town_list = list(map(int, raw_data[1].split()))
    road_set = set([])

    MAX = 200000
    D = np.zeros((N+1, N+1), dtype='int32')
    D += MAX

    for i in range(2, M+2):
        a, b, c = list(map(int, raw_data[i].split()))
        D[a][b] = c
        D[b][a] = c
        road_set.add(a)
        road_set.add(b)

    # print(raw_data)
    # print(N, M, R)
    # print(town_list)
    # print(D)
    # print(road_set)

    import itertools

    for k in range(int(math.ceil(len(road_set)/2))):
        for i, j in itertools.combinations(road_set, 2):
            dis_two_node = np.min(D[i] + D[j])
            if dis_two_node < D[i,j]:
                D[i,j] = dis_two_node
                D[j,i] = dis_two_node

    min_dis = MAX
    for each in itertools.permutations(town_list):
        if(dis(D, each) < min_dis):
            min_dis = dis(D, each)

    print(min_dis)




Travel()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
import math

def read_data():
    try:
        LOCAL_FLAG
        import codecs
        import os

        lines = []
        file_path = os.path.join(os.path.dirname(__file__), 'data073.dat')
        with codecs.open(file_path, 'r', 'utf-8') as f:
            lines.append(f.readline().rstrip("\r\n"))
            N, M, R = list(map(int, lines[0].split()))
            for i in range(M+1):
                lines.append(f.readline().rstrip("\r\n"))

    except NameError:
        lines = []
        lines.append(input())
        N, M, R = list(map(int, lines[0].split()))
        for i in range(M+1):
            lines.append(input())

    return lines

def dis(D, town_list):
    total = 0
    for i in range(len(town_list)-1):
        total += D[town_list[i]][town_list[i+1]]
    return total


def Travel():

    raw_data = read_data()
    N, M, R = list(map(int, raw_data[0].split()))
    town_list = list(map(int, raw_data[1].split()))

    MAX = 200000
    D = np.zeros((N+1, N+1), dtype='int32')
    D += MAX

    for i in range(2, M+2):
        a, b, c = list(map(int, raw_data[i].split()))
        D[a][b] = c
        D[b][a] = c

    # print(raw_data)
    # print(N, M, R)
    # print(town_list)
    # print(D)

    for k in range(int(math.ceil(M/2))):
        for i in range(1, N):
            for j in range(i+1, N+1):
                dis_two_node = np.min(D[i] + D[j])
                if dis_two_node < D[i,j]:
                    D[i,j] = dis_two_node
                    D[j,i] = dis_two_node



    import itertools
    min_dis = MAX
    for each in itertools.permutations(town_list):
        if(dis(D, each) < min_dis):
            min_dis = dis(D, each)

    print(min_dis)




Travel()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys

def read_data():
    try:
        LOCAL_FLAG
        import codecs
        import os

        lines = []
        file_path = os.path.join(os.path.dirname(__file__), 'data073.dat')
        with codecs.open(file_path, 'r', 'utf-8') as f:
            lines.append(f.readline().rstrip("\r\n"))
            N, M, R = list(map(int, lines[0].split()))
            for i in range(M+1):
                lines.append(f.readline().rstrip("\r\n"))

    except NameError:
        lines = []
        lines.append(input())
        N, M, R = list(map(int, lines[0].split()))
        for i in range(M+1):
            lines.append(input())

    return lines

def dis(D, town_list):
    total = 0
    for i in range(len(town_list)-1):
        total += D[town_list[i]][town_list[i+1]]
    return total


def Travel():

    raw_data = read_data()
    N, M, R = list(map(int, raw_data[0].split()))
    town_list = list(map(int, raw_data[1].split()))

    MAX = 200000
    D = np.zeros((N+1, N+1), dtype='int32')
    D += MAX

    for i in range(2, M+2):
        a, b, c = list(map(int, raw_data[i].split()))
        D[a][b] = c
        D[b][a] = c

    # print(raw_data)
    # print(N, M, R)
    # print(town_list)
    # print(D)

    for k in range(int(N/2)):
        for i in range(1, N):
            for j in range(i+1, N+1):
                dis_two_node = np.min(D[i] + D[j])
                if dis_two_node < D[i,j]:
                    D[i,j] = dis_two_node
                    D[j,i] = dis_two_node



    import itertools
    min_dis = MAX
    for each in itertools.permutations(town_list):
        if(dis(D, each) < min_dis):
            min_dis = dis(D, each)

    print(min_dis)




Travel()

Submission status: Time Limit Exceeded

Solution code:
import itertools
N,M,R=map(int,input().split())
R = [ int(i)-1 for i in input().split()]
rs = [[1001001001]*N for _ in range(N)]

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

for i in range(N-1):
    for j, d1 in enumerate(rs[i][i+1:], start=i+1):
        d2 = min(rs[i]+rs[j])
        if d1 >= d2:
            rs[i][j] = rs[j][i] = d2

p = list(itertools.permutations(range(N)));
ans = 1001001001
for i in p:
    s = 0
    for j in range(N-1):
        s += rs[i[j]][i[j+1]]
    ans = min(ans,s)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-
import itertools
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
d = [[0 for x in range(N)] for y in range(N)]
ans = float("inf")
for y in range(N):
    for x in range(N):
        d[y][x] = 0 if x == y else float('inf')

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

for k in range(N):
    for y in range(N):
        if d[y][k] == float('inf'):
            continue
        for x in range(N):
            if d[k][x] == float('inf'):
                continue
            d[y][x] = min(d[y][x], d[y][k]+d[k][x])

for tmp in list(itertools.permutations(r)):
    factor = 0
    for tmp2 in range(0, len(tmp)-1):
        if d[tmp[tmp2]-1][tmp[tmp2+1]-1] != 0 and d[tmp[tmp2]-1][tmp[tmp2+1]-1] != float('inf'):
            factor += d[tmp[tmp2]-1][tmp[tmp2+1]-1]
        else:
            break
    ans = min(ans, factor)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

N, M, R = [int(n) for n in input().split()]
r = [int(n)-1 for n in input().split()]
d = [[100000000]*N for n in range(N)]

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

for m in range(M):
  A, B, C = [int(n) for n in input().split()]
  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][k]+d[k][j], d[i][j])

res = 1000000000
for perm in permutations(range(R)):
  s = 0
  for i in range(R-1):
    s += d[r[perm[i]]][r[perm[i+1]]]
  res = min(s, res)

print(res)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

N, M, R = [int(n) for n in input().split()]
r = [int(n)-1 for n in input().split()]
d = [[100000000]*N for n in range(N)]

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

for m in range(M):
  A, B, C = [int(n) for n in input().split()]
  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][k]+d[k][j], d[i][j])

res = 10000000000
for perm in permutations(range(R)):
  s = 0
  for i in range(R-1):
    s += d[r[perm[i]]][r[perm[i+1]]]
  res = min(s, res)

print(res)