Problem:


Score : 400 points

Problem Statement

There are N towns in the State of Atcoder, connected by M bidirectional roads.

The i-th road connects Town A_i and B_i and has a length of C_i.

Joisino is visiting R towns in the state, r_1,r_2,..,r_R (not necessarily in this order).

She will fly to the first town she visits, and fly back from the last town she visits, but for the rest of the trip she will have to travel by road.

If she visits the towns in the order that minimizes the distance traveled by road, what will that distance be?

Constraints

2≤N≤200

1≤M≤N×(N-1)/2

2≤R≤min(8,N) (min(8,N) is the smaller of 8 and N.)

r_i≠r_j (i≠j)

1≤A_i,B_i≤N, A_i≠B_i

(A_i,B_i)≠(A_j,B_j),(A_i,B_i)≠(B_j,A_j) (i≠j)

1≤C_i≤100000

Every town can be reached from every town by road.

All input values are integers.

Input

Input is given from Standard Input in the following format:

N M R
r_1 ... r_R
A_1 B_1 C_1
:
A_M B_M C_M

Output

Print the distance traveled by road if Joisino visits the towns in the order that minimizes it.

Sample Input 1

3 3 3
1 2 3
1 2 1
2 3 1
3 1 4

Sample Output 1

2

For example, if she visits the towns in the order of 1, 2, 3, the distance traveled will be 2, which is the minimum possible.

Sample Input 2

3 3 2
1 3
2 3 2
1 3 6
1 2 2

Sample Output 2

4

The shortest distance between Towns 1 and 3 is 4. Thus, whether she visits Town 1 or 3 first, the distance traveled will be 4.

Sample Input 3

4 6 3
2 3 4
1 2 4
2 3 3
4 3 1
1 4 1
4 2 2
3 1 6

Sample Output 3

3



Sample input:
3 3 3
1 2 3
1 2 1
2 3 1
3 1 4


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

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

li = [[0 for i in range(N+1)]for j in range(N+1)]

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

def all_pairs_shortest_paths(W):
    inf = 10**18
    # 頂点の数
    n = len(W)
    # 結果を格納する行列を用意する
    res = [[0] * n for i in range(n)]
    # 用意した行列を初期化する
    for i in range(n):
        for j in range(i, n):
            if i == j:
                val = 0
            elif W[i][j]:
                val = W[i][j]
            else:
                val = inf
            res[i][j] = res[j][i] = val
    # 動的計画法ですべての超点間の最短距離を求める
    for k in range(n):
        for u in range(n):
            for v in range(n):
                res[u][v] = min(res[u][v], res[u][k] + res[k][v])
    return res

lin = all_pairs_shortest_paths(li)

pos = list(permutations(r))

mi = 10**18

for i in pos:
    l = 0
    for j in range(1,R):
        l += lin[i[j-1]][i[j]]
    mi = min(mi,l)

print(mi)

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M, R = MAP()
r = LIST()
ABC = [LIST() for _ in range(M)]

dist_matrix = [[INF]*N for _ in range(N)]
for A, B, C in ABC:
	dist_matrix[A-1][B-1] = C
	dist_matrix[B-1][A-1] = C

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

#for i in range(N):
#	print(dist_matrix[i])

def Warshall_Floyd(dist, N):
	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])

Warshall_Floyd(dist_matrix, N)

#for i in range(N):
#	print(dist_matrix[i])

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

def warshall_floyd(n, d):
    for k in range(n):
        for i in range(n): #始点
            for j in range(n): #終点
                d[i][j] = min(d[i][j], d[i][k]+d[k][j])
    return d

n,m,R=map(int,input().split())
r=list(map(int,list(input().split())))
g=[[float("inf")]*n for _ in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    g[a-1][b-1]=c
    g[b-1][a-1]=c
for i in range(n):
    g[i][i]=0
g=warshall_floyd(n,g)
ans=float("inf")
for p in list(permutations(r)):
    tmp=0
    for i in range(R-1):
        tmp+=g[p[i]-1][p[i+1]-1]
    ans=min(ans,tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N,M,R=map(int,input().split())
r=list(map(int,input().split()))
n=len(r)

graph=[[float("inf")]*N for _ in range(N)]
for i in range(M):
    A,B,C=map(int,input().split())
    A-=1
    B-=1
    graph[A][B]=C
    graph[B][A]=C

def dijkstra(start,cost):
    d=[float("inf")]*N
    used=[False]*N
    d[start]=0

    while True:
        v=-1
        for i in range(N):
            if (not used[i]) and (v==-1):
                v=i
            elif (not used[i]) and d[i]<d[v]:
                v=i
        if v==-1:
            break
        used[v]=True

        for j in range(N):
            d[j]=min(d[j],d[v]+cost[v][j])
    
    return d

d=[]
for i in range(N):
    d.append(dijkstra(i,graph))

anss=[]
for city in itertools.permutations(r):
    ans=0
    for i in range(n-1):
        ans+=d[city[i]-1][city[i+1]-1]
    anss.append(ans)
print(min(anss))

Submission status: Time Limit Exceeded

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

import sys
INF=float('inf')

road=[[INF]*n for _ in range(n)]

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

#経由地
for k in range(n):
    #出発地
    for s in range(n):
        #goal
        for g in range(n):
            road[s][g]=min(road[s][g],road[s][k]+road[k][g])

import itertools
rlist=list(itertools.permutations(r))

result=10**9
for item in rlist:
    tmp=0
    from_town=item[0]
    for to_town in item[1:]:
        tmp+=road[from_town-1][to_town-1]
        from_town=to_town
    result=min(result,tmp)

print(result)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N,M,R=map(int,input().split())
r=list(map(int,input().split()))
n=len(r)

graph=[[float("inf")]*N for _ in range(N)]
for i in range(M):
    A,B,C=map(int,input().split())
    A-=1
    B-=1
    graph[A][B]=C
    graph[B][A]=C

def dijkstra(start,cost):
    d=[float("inf")]*N
    used=[False]*N
    d[start]=0

    while True:
        v=-1
        for i in range(N):
            if (not used[i]) and (v==-1):
                v=i
            elif (not used[i]) and d[i]<d[v]:
                v=i
        if v==-1:
            break
        used[v]=True

        for j in range(N):
            d[j]=min(d[j],d[v]+cost[v][j])
    
    return d

d=[]
for i in range(N):
    d.append(dijkstra(i,graph))

ans=float("inf")
all_order=list(itertools.permutations(r))
for i in range(len(all_order)):
    tmp=0
    pre_location=all_order[i][0]-1
    for j in range(1,n):
        location=all_order[i][j]-1
        tmp+=d[pre_location][location]
        pre_location=location
    ans=min(ans,tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations


def main():
    towns, roads, visit = map(int, input().split())
    visit_order = [int(x) - 1 for x in input().split()]
    dist = [[float("inf") for _ in range(towns)] for _ in range(towns)]
    for _ in range(roads):
        a, b, d = map(int, input().split())
        a -= 1
        b -= 1
        dist[a][b] = d
        dist[b][a] = d
    for k in range(towns):
        for i in range(towns):
            for j in range(towns):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    answer = float("inf")
    for p in permutations(visit_order):
        now = 0
        for i in range(visit - 1):
            now += dist[p[i]][p[i + 1]]
        answer = min(answer, now)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from itertools import permutations


def warshall_floyd(n, d):
    for i in np.arange(n):
        for j in np.arange(n):
            for k in np.arange(n):
                t = d[j, i] + d[i, k]
                if t < d[j, k]:
                    d[j, k] = t


N, M, R = np.fromstring(input(), dtype = np.int64, sep = ' ')
r = np.fromstring(input(), dtype = np.int64, sep = ' ')

d = np.full((N + 1, N + 1), 1000000000, dtype=np.int64)
for _ in np.arange(M):
    A, B, C = np.fromstring(input(), dtype = np.int64, sep = ' ')
    d[A, B] = C
    d[B, A] = C
warshall_floyd(N + 1, d)

result = np.int64(1000000000)
for p in permutations(r):
    t = np.int64(0)
    for i in range(R - 1):
        t += d[p[i], p[i + 1]]
    if t < result:
        result = t
print(result)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from itertools import permutations


def warshall_floyd(n, d):
    for i in np.arange(n):
        for j in np.arange(n):
            for k in np.arange(n):
                t = d[j, i] + d[i, k]
                if t < d[j, k]:
                    d[j, k] = t


N, M, R = np.fromstring(input(), dtype = np.int64, sep = ' ')
r = np.fromstring(input(), dtype = np.int64, sep = ' ')

d = np.full((N + 1, N + 1), 1000000000, dtype=np.int64)
for _ in range(M):
    A, B, C = map(int, input().split())
    d[A, B] = C
    d[B, A] = C
warshall_floyd(N + 1, d)

result = 1000000000
for p in permutations(r):
    t = 0
    for i in range(R - 1):
        t += d[p[i], p[i + 1]]
    result = min(result, t)
print(result)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from itertools import permutations


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


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

d = np.full((N + 1, N + 1), 1000000000, dtype=np.int64)
for _ in range(M):
    A, B, C = map(int, input().split())
    d[A, B] = C
    d[B, A] = C
warshall_floyd(N + 1, d)

result = 1000000000
for p in permutations(r):
    t = 0
    for i in range(R - 1):
        t += d[p[i], p[i + 1]]
    result = min(result, t)
print(result)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations


def warshall_floyd(n, d):
    from builtins import min
    for i in range(n):
        di = d[i]
        for j in range(n):
            dj = d[j]
            for k in range(n):
                dj[k] = min(dj[k], dj[i] + di[k])


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

d = [[1000000000] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
    A, B, C = map(int, input().split())
    d[A][B] = C
    d[B][A] = C
warshall_floyd(N + 1, d)

result = 1000000000
for p in permutations(r):
    t = 0
    for i in range(R - 1):
        t += d[p[i]][p[i + 1]]
    result = min(result, t)
print(result)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations


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


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

d = [[1000000000] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
    A, B, C = map(int, input().split())
    d[A][B] = C
    d[B][A] = C
warshall_floyd(N + 1, d)

result = 1000000000
for p in permutations(r):
    t = 0
    for i in range(R - 1):
        t += d[p[i]][p[i + 1]]
    result = min(result, t)
print(result)

Submission status: Time Limit Exceeded

Solution code:
import itertools


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

INF = float("inf")
es = [[INF for _ in range(N)]  for _ in range(N)]
for i in range(N):
  es[i][i] = 0

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



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

ans = INF
for route in itertools.permutations(rs):
  tmp = 0
  for a,b in zip(route, route[1:]):
    tmp += es[a-1][b-1]
  ans = min(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n, m, r = map(int, input().split())
R = [int(x) for x in input().split()]
inf = pow(10, 9)+7

roads = [[inf]*n for _ in range(n)]
for i in range(m):
  a, b, c = map(int, input().split())
  roads[a-1][b-1] = c
  roads[b-1][a-1] = c

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

ans = inf
for value in itertools.permutations(R):
  sub = 0
  for k in range(r-1):
    sub += roads[value[k]-1][value[k+1]-1]
  if ans > sub:
    ans = sub

print(ans)

Submission status: Time Limit Exceeded

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

def warshall_floyd(G):
    #d[i][j]: iからjへの最短距離
    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])
    return G
G=warshall_floyd(G)
ans=10**8
for L in itertools.permutations(r):
    L=list(L)
    sub=0
    for i in range(1,R):
        s=L[i-1]
        t=L[i]
        sub+=G[s-1][t-1]
    ans=min(ans, sub)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**8
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,M,R = LI()
    r = _LI()
    root = [[] for _ in range(N)]
    for _ in range(M):
        a,b,c = LI()
        root[a-1].append((b-1,c))
        root[b-1].append((a-1,c))

    memo = [[0] * N for _ in range(N)]

    min_r = INF
    for x in itertools.permutations(r):
        it = 0
        s = x[0]
        for t in x[1:]:
            if memo[s][t]:
                it += memo[s][t]
            else:
                node = [INF] * N
                q = [(s,0)]
                while q:
                    u,l = q.pop()
                    node[u] = l
                    for v,m in root[u]:
                        if node[v] > l + m:
                            q.append((v,l+m))
                memo[s][t] = node[t]
                #memo[t][s] = node[t]
                it += node[t]
            s = t
        min_r = min(min_r,it)
    print(min_r)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**8
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,M,R = LI()
    r = _LI()
    root = [[] for _ in range(N)]
    for _ in range(M):
        a,b,c = LI()
        root[a-1].append((b-1,c))
        root[b-1].append((a-1,c))

    min_r = INF
    for x in itertools.permutations(r):
        it = 0
        s = x[0]
        for t in x[1:]:
            node = [INF] * N
            q = [(s,0)]
            while q:
                u,l = q.pop()
                node[u] = l
                for v,m in root[u]:
                    if node[v] > l + m:
                        q.append((v,l+m))
            it += node[t]
            s = t
        min_r = min(min_r,it)
    print(min_r)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# --- ワーシャルフロイド 任意のペアに対して最短距離を求める（非負）
def warshall_floyd(dp):
    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

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

d = [[float("inf")]*n for i in range(n)]

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

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

warshall_floyd(d)

import itertools

p = itertools.permutations(r, R)

INF = float('inf')
ans = INF
for path in p:
    tmp = 0
    for i in range(R-1):
        tmp += d[path[i]-1][path[i+1]-1]
    ans = min(ans,tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from itertools import permutations, tee

    INF = 1 << 30

    N, M, R = map(int, input().split())
    *r, = (int(x) - 1 for x in input().split())

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

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

    ans = INF
    for perm in permutations(r):
        perm_iter = iter(perm)
        frm_iter, to_iter = tee(perm_iter, 2)
        next(to_iter)
        t = 0
        for frm, to in zip(frm_iter, to_iter):
            t += d[frm][to]
        ans = min(ans, t)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
#s=input().rstrip()

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

##############################
n,w,r = map(int,input().split())#n:頂点数　w:辺の数
lis=LI()
d = [[float("inf")]*n for i in range(n)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(w):
    x,y,z = map(int,input().split())
    x-=1
    y-=1
    d[x][y] = z
    d[y][x] = z
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
#print(warshall_floyd(d))
#インデックスで与えられていることに注意
d=warshall_floyd(d)
#print(d)
z=permutations(lis,r)
mn=inf
for s in z:
    u=list(s)
    dis=0
    for i in range(r-1):
        dis+=d[u[i]-1][u[i+1]-1]
    #print(dis)
    if dis<mn:
        mn=dis
print(mn)

Submission status: Time Limit Exceeded

Solution code:
N,M,R = map(int,input().split())
r = list(map(int,input().split()))
INF = 10**18
d = [[INF for i in range(N)] for j in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c

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

# ワーシャルフロイド
for k in range(N):
    for i in range(N):
        for j in range(N):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

import itertools
ans = INF
for v in itertools.permutations(r,R):
    anss = 0
    for i in range(R-1):
        anss += d[v[i]-1][v[i+1]-1]
    ans = min(ans,anss)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
inf=10**5
n,m,R=map(int,input().split())
r=list(map(int,input().split()))
d=[[inf]*n for i in range(n)]
for i in range(n):
    d[i][i]=0
ans=inf
for i in range(m):
    a,b,c=map(int,input().split())
    d[a-1][b-1]=c
    d[b-1][a-1]=c
for k in range(n):
    for i in range(n):
        for j in range(n):
            d[i][j]=min(d[i][j],d[i][k]+d[k][j])
for i in itertools.permutations(r):
    preans=0
    for j in range(R-1):
        preans+=d[i[j]-1][i[j+1]-1]
    ans=min(ans,preans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

def main():
    n, m, q = map(int, input().split())
    r = list(map(int, input().split()))
    dist = [[10**18 for _ in range(n)] for _ in range(n)]
    for i in range(m):
        a, b, c = 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])

    ans = 10 ** 18
    for p in itertools.permutations(r):
        total = 0
        for i in range(q-1):
            total += dist[p[i]-1][p[i+1]-1]
        ans = min(ans, total)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10 ** 9)
    MOD = 10 ** 9 + 7

    from itertools import permutations

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

    INF = 10 ** 9

    G = [[INF] * (N + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        G[i][i] = 0

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

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

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

    print (ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

from itertools import permutations

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

INF = 10 ** 9

G = [[INF] * (N + 1) for _ in range(N + 1)]
for i in range(N + 1):
    G[i][i] = 0

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

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

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

print (ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

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

minDist = [[10**18] * N for _ in range(N)]
for _ in range(M):
    fr, to, cost = map(int, input().split())
    fr -= 1
    to -= 1
    minDist[fr][to] = cost
    minDist[to][fr] = cost
for i in range(N):
    minDist[i][i] = 0

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

ans = 10**18
for P in permutations(R, r=len(R)):
    cost = 0
    for fr, to in zip(P, P[1:]):
        cost += minDist[fr][to]
    ans = min(ans, cost)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n,m,r = map(int,input().split())
wa = [[float("INF")]*n for i in range(n)]
l = [i-1 for i in map(int,input().split())]
for i in range(m):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    wa[a][b] = c
    wa[b][a] = c
for i in range(n):
    wa[i][i] = 0

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

ans = float("INF")

for p in list(itertools.permutations(l)):
    count = 0
    for i in range(r-1):
        count += wa[p[i]][p[i+1]]
    ans = min(ans,count)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import permutations


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


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

    def warshall_floyd(d):
        # d[i][j]: iからjへの最短距離
        for k in range(N):
            for i in range(N):
                for j in range(N):
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])
        return d

    r = list(map(int, input().split()))
    d = [[float("inf")] * 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 = warshall_floyd(d)
    P = list(permutations(r))
    cost = float("inf")
    for p in P:
        c = 0
        for i in range(R - 1):
            c += D[p[i] - 1][p[i + 1] - 1]
        if c < cost:
            cost = c
    print(cost)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
##from scipy.sparse.csgraph import csgraph_from_dense,floyd_warshall
import numpy as np
from itertools import permutations
N,M,R = map(int,input().split())
r = list(map(int,input().split()))

"""
https://juppy.hatenablog.com/entry/2018/11/01/%E8%9F%BB%E6%9C%AC_python_%E5%85%A8%E7%82%B9%E5%AF%BE%E6%9C%80%E7%9F%AD%E7%B5%8C%E8%B7%AF%E6%B3%95%EF%BC%88%E3%83%AF%E3%83%BC%E3%82%B7%E3%83%A3%E3%83%AB%E3%83%95%E3%83%AD%E3%82%A4%E3%83%89%E6%B3%95
"""

def warshall_floyd(d):
    n = len(d)
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

graph = [[float("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

dist = warshall_floyd(graph)

ans = 1e10
for i in permutations(r):
    flag = True
    way = list(i)
    tmp = 0
    for i in range(len(way)-1):
        if dist[way[i]-1][way[i+1]-1] < 0:
            flag = False
            break
        tmp += dist[way[i]-1][way[i+1]-1]
    if flag:
        ans = min(tmp,ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense,floyd_warshall
import numpy as np
from itertools import permutations
N,M,R = map(int,input().split())
r = list(map(int,input().split()))

graph = [[float("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

dist = np.array(floyd_warshall(graph),dtype="int32")

ans = 1e10
for i in permutations(r):
    flag = True
    way = list(i)
    tmp = 0
    for i in range(len(way)-1):
        if dist[way[i]-1][way[i+1]-1] < 0:
            flag = False
            break
        tmp += dist[way[i]-1][way[i+1]-1]
    if flag:
        ans = min(tmp,ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

MAX_DIS = 10**10
N,M,R = map(int,input().split(" "))
r_list = list(map(int,input().split(" ")))
roads = [[MAX_DIS]*N for i in range(N)]
for i in range(N):
    roads[i][i] = 0
for i in range(M):
    A,B,C = map(int,input().split(" "))
    roads[A-1][B-1] = C
    roads[B-1][A-1] = C
for k in range(N):
    for i in range(N):
        for j in range(N):
            roads[i][j] = min(roads[i][j],roads[i][k]+roads[k][j])
min_dis = MAX_DIS
for directions in itertools.permutations(r_list):
    distance  = 0
    for dir in range(1,len(directions)):
        distance += roads[directions[dir-1]-1][directions[dir]-1]
    if distance < min_dis:
        min_dis =distance
print(min_dis)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
n, m, r = map(int, input().split())
towns = [int(x) - 1 for x in input().split()]
inf = 10 ** 10
d = [[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

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

warshall_floyd(d, n)
ans = 10 ** 10
for t in permutations(towns):
    tmp = 0
    for i in range(len(t) - 1):
        tmp += d[t[i]][t[i+1]]
    ans = min(ans, tmp)


print(ans)

Submission status: Time Limit Exceeded

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

n,m,r= map(int, input().split())
rr= list(map(int, input().split()))
a= [list(map(int, input().split())) for i in range(m)]
edges=[[] for i in range(n)]

for x,y,z in a:
    edges[x-1].append((y-1,z))
    edges[y-1].append((x-1,z))

#ダイクストラ法
from heapq import heappush, heappop

def dijkstra(edges, size, source,g):
    # edge=探索するグラフ
    # size=グラフの点の数
    # source=スタート点
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance[g]

# bit DP
# dp[S][v]: 訪れた点の集合がSで最後にVを訪れた時のVのMIN
INF=float('inf')
dp=[[INF]*r for i in range(1<<r)]
dp[0]=[0]*r

for i in range(1<<r):
    for k in range(r):
        # 訪問リストに入っているものを最後に訪問する時
        if (i >> k) & 1:
            if i^(1<<k)==0:
                dp[i][k]=0
            else:
                # 最後に訪れるものを除いた集合でどこを最後に訪問した時がminか調べる
                for l in range(r):
                    if (i ^ (1 << k))>>l:
                        dpm = dp[i ^ (1 << k)][l]
                        ad = dijkstra(edges, n, rr[l] - 1, rr[k] - 1)
                        dp[i][k] = min(dpm + ad, dp[i][k])

print(min(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
import itertools

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
INF = 10**15
cost = [[INF for _ in range(N)] for _ in range(N)]
for i in range(M):
    A, B, C = map(int, input().split())
    cost[A-1][B-1] = C
    cost[B-1][A-1] = C
    
for k in range(N):
    for i in range(N):
        for j in range(N):
            cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j])
      
a = list(itertools.permutations(r))
ans = INF
for i in range(len(a)):
    tmp = 0
    for j in range(R-1):
        tmp += cost[a[i][j]-1][a[i][j+1]-1]
    ans = min(ans, tmp)
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')

graph = [[INF for _ in range(N)] for _ in range(N)]

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

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

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

total_min = INF
for i in permutations(r, len(r)):
    total = 0
    for j in range(len(r)-1):
        total += graph[i[j]-1][i[j-1]-1]
    if total < total_min:
        total_min = total

print(total_min)