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:
import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict, OrderedDict
#すべてのkeyが用意されてる defaultdict(int)で初期化
#順序を保ったdict
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########

n,m,r=map(int,input().split())
R=[i-1 for i in list(map(int,input().split()))]#いくまち
G=[[] for i in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    a-=1;b-=1
    G[a].append([c,b])
    G[b].append([c,a])  #G[i]:=iから出る道の[重み、行先]の配列


def dijkstra(s):
    dist=[inf for i in range(n)] #sからの距離のリスト
    dist[s]=0
    mirai=[True for i in range(n)] #Trueなら未確定
    mirai[s]=False

    queue=[] #こいつがheapqになる
    for kyori,to in G[s]:
        heapq.heappush(queue , kyori*10**6+to)  #重みと行先を1つの変数で表してる！
    while queue:
        minedge= heapq.heappop(queue)
        #miraiがTrueのやつ(未確定なやつ)から最小距離のものをさがす
        if not mirai[minedge%(10**6)]: continue
        #距離が小さいものから"確定"していく
        v=minedge%(10**6) #最小距離の頂点
        dist[v] = minedge//(10**6) #その距離
        mirai[v]=False
        for kyori,to in G[v]:
            if mirai[to]:
                heapq.heappush(queue, (kyori+dist[v])*(10**6)+to)
                #queueに入る数は、必ず「sからの」距離と行先を持っている
    return dist
#print(R)
#print(dijkstra(0))
from itertools import permutations as per
ans=inf
for l in per(R):
    now=0
    for i in range(r-1):
        now+=dijkstra(l[i])[l[i+1]]
    ans=min(ans,now)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
n, m, r = map(int, input().split())
R = list(map(lambda x: int(x)-1, input().split()))
INF = 10**18
dist = [[INF]*n for _ in range(n)]
for _ 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][k]+dist[k][j], dist[i][j])

ans = INF
for subset in permutations(R):
    d = 0
    for v, v2 in zip(subset, subset[1:]):
        d += dist[v][v2]
    if d < ans:
        ans = d
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

def warshall_floyd(A, INF=10**20):
    d = [[INF for i in range(len(A))] for j in range(len(A))]
    for i in range(len(A)):
        d[i][i] = 0
        for j in A[i].keys():
          d[i][j] = A[i][j]

    for k in range(len(A)):
        for i in range(len(A)):
            for j in range(len(A)):
                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,input().split()))
r2 = []
for i in range(len(r)):
  r2.append(r[i]-1)
r = r2
G=[{} for _ in range(N)]
for i in range(M):
  a,b,c=map(int,input().split())
  a -= 1
  b -= 1
  G[a][b] = c
  G[b][a] = c

d = warshall_floyd(G)

if R==2:
  print(d[r[0]][r[1]])
  exit()
  
ans = 10**20
for p in permutations(r):
  dist=0
  for i in range(R-1):
    dist += d[p[i]][p[i+1]]
  ans = min(ans,dist)
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
n,m,r = map(int,input().split())
route = list(map(int,input().split()))

dp = [[0 for _ in range(n)] for _ in range(n)]
INF = 10**18
for i in range(n):
    for j in range(n):
        if i!=j:
            dp[i][j] = INF
for _ in range(m):
    a,b,c = map(int,input().split())
    dp[a-1][b-1] = c
    dp[b-1][a-1] = c
#print(dp)

#最短リスト
for chu in range(n):
    for fir in range(n):
        for la in range(n):
            dp[fir][la] = min(dp[fir][la] , dp[fir][chu] +  dp[chu][la])

ans = 10**10
for j in permutations(route, r):
    a = 0
    for q,w in zip(j[:-1], j[1:]):
        a += dp[q-1][w-1]
        
    ans = min(ans,a)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m, r = map(int, input().split())  # n:頂点数　w:辺の数
r_list = list(map(int, input().split()))
graph = [[float('inf')]*n for i in range(n)]
for _ in range(m):
    u, v, w = map(int, input().split())
    graph[u-1][v-1] = w
    graph[v-1][u-1] = w
for i in range(n):
    graph[i][i] = 0

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


from itertools import permutations

adj_m=warshall_floyd(graph)
ans=float('inf')
for path in permutations(r_list):
    tmp_dist=0
    for i in range(r-1):
        tmp_dist+=adj_m[path[i]-1][path[i+1]-1]
    ans=min(ans, tmp_dist)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

N, M ,R = map(int, input().split())
r = list(map(int, input().split()))
rr = list(itertools.permutations(r, R))
ab = [[10 ** 10] * N for i in range(N)]
for i in range(N):
  ab[i][i] = 0
  
for i in range(M):
  a, b, c = list(map(int, input().split()))
  ab[a - 1][b - 1] = c
  ab[b - 1][a - 1] = c
  
ans = warshall_floyd(ab)  
#print(rr)
#print(ans)
#2 ** 8
answer = 10 ** 12
for i in rr:
  now = 0
  #print(i)
  for j in range(R - 1):
    now += ans[i[j] - 1][i[j + 1] - 1]
    
  answer = min(answer, now)  
  
print(answer)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

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, M, R = map(int, input().split())
r = list(map(int, input().split()))

road = [[float("inf")]*N for _ in range(N)]

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

for j in range(N):
    road[j][j] = 0

road = warshall_floyd(road)

# print(road)
ans = float("inf")

for v in permutations(r, len(r)):
    # print("v", v)
    tmp = 0
    for i in range(len(r)-1):
        tmp += road[v[i]-1][v[i+1]-1]
    # print(tmp)
    ans = min(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
n, m, r = map(int, input().split())
goals = list(map(int, input().split()))
goals = [g-1 for g in goals]

g = [[pow(10, 16)] * n for i in range(n)]

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

for i in range(n):
    for s in range(n):
        for t in range(n):
            g[s][t] = min(g[s][t], g[s][i] + g[i][t])

ans = float('inf')
for p in permutations(goals):
    cost = 0
    for s,t in zip(p[:-1], p[1:]):
        cost += g[s][t]
    ans = min(ans, cost)
print(ans)

Submission status: Time Limit Exceeded

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

INFTY = 10**9
cost = [[INFTY]*(N+1) for _ in range(N+1)]

# 辺を入力
for _ in range(W):
    u, v, c = map(int, input().split())
    cost[u][v] = c
    cost[v][u] = c

# 自身に向かうコストは0
for i in range(N+1):
    cost[i][i] = 0


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


WarshallFloyd()

ans = 10**9
for T in permutations(S, R):
    temp = 0
    t = T[0]
    for i in range(1, R):
        temp += cost[t][T[i]]
        t = T[i]
    ans = min(ans, temp)
print(ans)

Submission status: Time Limit Exceeded

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

    n, m, r, *x = map(int, open(0).read().split())
    to = x[:r]

    dis = [[0 if i == j else float("Inf") for j in range(n + 1)] for i in range(n + 1)]

    for a, b, c in zip(*[iter(x[r:])] * 3):
        dis[a][b] = c
        dis[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[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])

    ans = float("Inf")
    for p in permutations(to):
        tmp = 0
        nw = p[0]
        for nx in p[1:]:
            tmp += dis[nw][nx]
            nw = nx

        ans = min(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
from itertools import permutations
def main():
    def warshall_floyd(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())
    rs = tuple(map(int, input().split()))
    d = [[10**9] * n for _ in range(n)]
    m = map(int, read().split())
    mmm = zip(m, m, m)
    for s, t, dis in mmm:
        s -= 1
        t -= 1
        d[t][s] = d[s][t] = dis
    for j1 in range(n):
        d[j1][j1] = 0
    res = warshall_floyd(d)
    rsp = tuple(permutations(rs))
    result = float('inf')
    for rspe in rsp:
        res_t = 0
        for i1 in range(r - 1):
            res_t += res[rspe[i1]-1][rspe[i1+1]-1]
        result = min(result, res_t)
    print(result)
 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    n, m, r, *x = map(int, open(0).read().split())
    to = x[:r]

    m = [[0 if i == j else float("Inf") for j in range(n + 1)] for i in range(n + 1)]

    for a, b, c in zip(*[iter(x[r:])] * 3):
        m[a][b] = c
        m[b][a] = c

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

    ans = float("Inf")
    dis = f(m)
    for p in permutations(to):
        tmp = 0
        nw = p[0]
        for nx in p[1:]:
            tmp += dis[nw][nx]
            nw = nx

        ans = min(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    n, m, r, *x = map(int, open(0).read().split())
    to = x[:r]

    dis = [[0 if i == j else float("Inf") for j in range(n + 1)] for i in range(n + 1)]

    for a, b, c in zip(*[iter(x[r:])] * 3):
        dis[a][b] = c
        dis[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[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])

    ans = float("Inf")
    for p in permutations(to, r):
        tmp = 0
        nw = p[0]
        for nx in p[1:]:
            tmp += dis[nw][nx]
            nw = nx

        ans = min(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    n, m, r, *x = map(int, open(0).read().split())
    to = x[:r]

    dis = [[float("Inf")] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        dis[i][i] = 0

    for a, b, c in zip(*[iter(x[r:])] * 3):
        dis[a][b] = c
        dis[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[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])

    ans = float("Inf")
    done = []
    for p in permutations(to, r):
        tmp = 0
        if list(p) in done:
            continue
        q = list(p)
        done.append(sorted(q))
        for i, j in zip(p, p[1:]):
            tmp += dis[i][j]
        ans = min(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    n, m, r, *x = map(int, open(0).read().split())
    to = x[:r]

    dis = [[float("Inf")] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        dis[i][i] = 0

    for a, b, c in zip(*[iter(x[r:])] * 3):
        dis[a][b] = c
        dis[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[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])

    ans = float("Inf")
    for p in permutations(to, r):
        tmp = 0
        for i, j in zip(p, p[1:]):
            tmp += dis[i][j]
        ans = min(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    n, m, r, *x = map(int, open(0).read().split())
    to = x[:r]

    dis = [[float("Inf")] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        dis[i][i] = 0

    for a, b, c in zip(*[iter(x[r:])] * 3):
        dis[a][b] = c
        dis[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[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])

    ans = float("Inf")
    for p in permutations(to):
        tmp = 0
        for i, j in zip(p, p[1:]):
            tmp += dis[i][j]
        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())
G=[[] for _ in range(N)]
r=list(map(int, input().split()))
for i in range(M):
    a,b,c=map(int, input().split())
    G[a-1].append((b-1,c))
    G[b-1].append((a-1,c))

from heapq import heappop, heappush

class Dijkstra:
    """
    shortest_distance(g): startノードからgoalノードまでの最短距離
    """
    def __init__(self, graph, start, goal):
        """
        graph: 隣接リストによるグラフG[from]=(to,距離)
        start: 始点のノード番号
        goal: 終点のノード番号
        """
        self.g = graph
        self.V = len(graph)

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = [float('inf')] * (self.V)
        self.dist[start] = 0

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (0, start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            # goalノードならそこで終了
            if u == goal:
                break
            if dist_u > self.dist[u]:
                continue
            for v, weight in self.g[u]:
                alt = self.dist[u] + weight
                if alt < self.dist[v] :
                    self.dist[v] = alt
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        return self.dist[goal]


#print(G)

ans=float("INf")
for t in permutations(r):
    sub=0
    #print(t)
    for i in range(R):
        if i==0:
            now=t[i]
        d=Dijkstra(G,now-1,t[i]-1)
        sub+=d.shortest_distance(t[i]-1)
        now=t[i]
        #print(now)
    ans=min(ans, sub)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
MAX = 10 ** 9
def warshall_floyd(n, dist):
    for k in range(n):
        for i in range(n-1):
            for j in range(i, n):
                dist[i][j] = dist[j][i] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
E = [[MAX] * N for _ in range(N)]
for i in range(N):
    E[i][i] = 0
for i in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    E[a][b] = c
    E[b][a] = c
E = warshall_floyd(N, E)
res = MAX
for p in permutations(r):
    tmp = 0
    for i in range(R-1):
        tmp += E[p[i]-1][p[i+1]-1]
    res = min(res, tmp)
print(res)

Submission status: Time Limit Exceeded

Solution code:
n,m,r_=map(int,input().split())
r=list(map(int,input().split()))
g=[[]for _ in range(n)]
for _ in range(m):
  a,b,c=map(int,input().split())
  a-=1
  b-=1
  g[a].append([b,c])
  g[b].append([a,c])
from heapq import heapify,heappush,heappop
def dks(t0,t1):
  kyori=[-1]*n
  todo=[[0,t0]]
  heapify(todo)
  while todo:
    d,t=heappop(todo)
    kyori[t]=d
    if t==t1:break
    l=g[t]
    for li,c in l:
      if kyori[li]==-1:
        heappush(todo,[c+d,li])
  return kyori[t1]
ans=pow(10,9)
allr=[]
import sys
sys.setrecursionlimit(10**7)
def dfs(s,k): #s:list, k:set
  if len(k)==1:
    s.append(k.pop())
    return [s]
  ret=[]
  for ki in k:
    ret.extend(dfs(s+[ki],k-{ki}))
  return ret
allr=dfs([],set(r))
for j in range(len(allr)):
  r1=allr[j]
  ansi=0
  for i in range(r_-1):
    ansi+=dks(r1[i]-1,r1[i+1]-1)
  ans=min(ans,ansi)
print(ans)

Submission status: Time Limit Exceeded

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


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')

from itertools import permutations

def main():
	n,m,R=MI()
	r=LI()

	G=[[10**9]*(n+1) for _ in range(n+1)]
	for i in range(n+1):
		G[i][i]=0



	for _ in range(m):
		a,b,c=MI()
		G[a][b]=min(G[a][b],c)
		G[b][a]=min(G[b][a],c)
	#print(G)

	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])
	#print(G)

	ans=10**9
	for i in permutations(r,R):
		#print(i)
		ret=0
		for j in range(R-1):
			ret+=G[i[j]][i[j+1]]
		#print(ret)
		ans=min(ans,ret)
	print(ans)





if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N, M, R = getNM()

d = [[float("inf")] * N for i in range(N)]
list_R = [int(i) - 1 for i in input().split()]
for i in range(M):
   x, y, z = getNM()
   d[x - 1][y - 1] = min(d[x - 1][y - 1], z)
   d[y - 1][x - 1] = min(d[x - 1][y - 1], z)

dp = [[-1] * N for i in range(1 << N)]
goal = 0
# Rの地点に全てフラグを立てればOK（順番は気にしない）
for i in list_R:
    goal |= (1 << i)


ans = float('inf')
def rec(ns, nv, n_sum):
    global ans

    pos = []
    heapq.heapify(pos)
    heapq.heappush(pos, [n_sum, ns, nv])

    dp = [[-1] * N for i in range(1 << N)]

    while len(pos) > 0:
        sum, s, v = heapq.heappop(pos)

        if s & goal == goal:
            ans = min(ans, sum)
            break

        for u in range(N):
            if s & (1 << u) == 0:
                heapq.heappush(pos, [sum + d[v][u], s|(1 << u), u])

for i in range(R):
    index = list_R[i]
    rec((1 << index), index, 0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N, M, R = getNM()

d = [[float("inf")] * N for i in range(N)]
list_R = [int(i) - 1 for i in input().split()]
for i in range(M):
   x, y, z = getNM()
   d[x - 1][y - 1] = min(d[x - 1][y - 1], z)
   d[y - 1][x - 1] = min(d[x - 1][y - 1], z)

dp = [[-1] * N for i in range(1 << N)]
goal = 0
# Rの地点に全てフラグを立てればOK（順番は気にしない）
for i in list_R:
    goal |= (1 << i)

ans = float('inf')
def rec(s, v, sum):
    global ans

    if s & goal == goal:
        ans = min(ans, sum)
        return

    for u in range(N):
        if s & (1 << u) == 0:
            rec(s|(1 << u), u, sum + d[v][u])

for i in range(R):
    rec((1 << i), i, 0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N, M, R = getNM()

d = [[float("inf")] * N for i in range(N)]
list_R = [int(i) - 1 for i in input().split()]
for i in range(M):
   x, y, z = getNM()
   d[x - 1][y - 1] = z
   d[y - 1][x - 1] = z

dp = [[-1] * N for i in range(1 << N)]
goal = 0
# Rの地点に全てフラグを立てればOK（順番は気にしない）
for i in list_R:
    goal |= (1 << i)

ans = float('inf')
def rec(s, v, sum):
    global ans

    if s & goal == goal:
        ans = min(ans, sum)
        return

    for u in range(N):
        if s & (1 << u) == 0:
            rec(s|(1 << u), u, sum + d[v][u])

for i in range(R):
    rec((1 << i), i, 0)

print(ans)

Submission status: Time Limit Exceeded

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

inf = 10**9
d = [[inf]*N for _ 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
def warshall_floyd():
  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])
  
def main():
  warshall_floyd()
  ans = inf
  for per in itertools.permutations(r):
    ans_temp = 0
    for i in range(R-1):
      ans_temp += d[per[i]][per[i+1]]
    ans = min(ans, ans_temp)
  print(ans)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

inf = 10**9
d = [[inf]*N for _ 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
def warshall_floyd():
  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])
  
def main():
  warshall_floyd()
  ans = inf
  for per in itertools.permutations(r):
    ans_temp = 0
    for i in range(R-1):
      ans_temp += d[per[i]][per[i+1]]
    ans = min(ans, ans_temp)
  print(ans)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

d = [[10**7 for j in range(n)] for i in range(n)]
for i in range(m):
  a, b, c = map(int, input().split())
  a -= 1
  b -= 1
  d[a][b] = c
  d[b][a] = 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][k]+d[k][j],d[i][j])

# print (d)
ans = 10**8
for i in itertools.permutations(r):
  x = i
  k = 0
  for j in range(R-1):
    a,b = x[j+1],x[j]
    a -= 1
    b -= 1
    k += d[b][a]
  ans = min(ans,k)
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()))
d = [[1000000000 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 k in range(N):
  for i in range(N):
    for j in range(N):
      if i != j and j != k and k != i:
        d[i][j] = min(d[i][j], d[i][k] + d[k][j])
ans = 1000000000
for s in permutations(r):
  t = 0
  for i in range(1, R):
    t += d[s[i-1]-1][s[i]-1]
  ans = min(t, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

inf = float('inf')
dists = [[inf] * n for _ in range(n)]
for i in range(n):
    dists[i][i] = 0

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

## Warshall–Floyd
for k in range(n):
    for i in range(n):
        for j in range(n):
            dists[i][j] = min(dists[i][j], dists[i][k] + dists[k][j])

tours = []
for perm in itertools.permutations(rs):
    d = 0
    for i in range(r-1):
        d += dists[perm[i]][perm[i+1]]
    tours.append(d)
print(min(tours))

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

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

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

for i in range(M):
  A, B, C = map(int, input().split())
  d[A-1][B-1] = C
  d[B-1][A-1] = C
  
for 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])
      
perms = permutations(r, R)
ans = 10000000000
for perm in perms:
  now = 0
  for i in range(R-1):
    now += d[perm[i]][perm[i+1]]
  ans = min(ans, now)
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
n, m, r = map(int, input().split())
INF = 1 << 60

d = [[INF] * n for i in range(n)]
rs = list(map(int, input().split()))

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

def warshall_floyd(d):
    """
    input
        d : 初期全点対距離
    output
        d : 最適化後全点対距離
    """
    n = len(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

d_optimized = warshall_floyd(d)
# print(d_optimized)

ans = INF
for inds in permutations([r-1 for r in rs]):
    cnt = 0
    for i in range(r-1):
        prev = inds[i]
        nxt = inds[i+1]
        cnt += d_optimized[prev][nxt]
    ans = min(ans,cnt)
print(ans)

Submission status: Time Limit Exceeded

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

from collections import defaultdict
V = defaultdict(list)
 
for _ in range(m):
    a, b,c = map(int, input().split())
    V[a].append([b,c])
    V[b].append([a,c])
    
def dfs(source):
    dist = [-1]*(n+1)
    dist[source] = 0
    q = [source]
    while q:
        a = q.pop()
        ii = -1
        for b in V[a]:
            ii = ii+1
            if dist[b[0]]!=-1:
                dist[b[0]] = min(dist[b[0]],dist[a] + V[a][ii][1])
                continue
            dist[b[0]] = dist[a] + V[a][ii][1]
            q.append(b[0])

    return dist

import itertools
zz = list(itertools.permutations(al))

res = 10*9
for k in zz:
    temp = 0
    for l in range(r-1):
        temp += dfs(k[l])[(k[l+1])]
    res = min(res,temp)
print(res)