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 itertools

inf = 10 ** 9
n, m, r = map(int, input().split())
r_list = [int(i) - 1 for i in input().split()]
a_list = [[inf for _ in range(n)] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    a_list[a][b] = a_list[b][a] = c
for k in range(n):
    for i in range(n):
        for j in range(n):
            x = a_list[i][k] + a_list[k][j]
            if x < a_list[i][j]:
                a_list[i][j] = a_list[j][i] = x
k = list(itertools.permutations(r_list))
ans = inf
for kk in k[:len(k)//2 + 1]:
    temp = 0
    for k1, k2 in zip(kk[:-1], kk[1:]):
        temp += a_list[k1][k2]
    if ans > temp:
        ans = temp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

inf = 10 ** 9
n, m, r = map(int, input().split())
r_list = [int(i) - 1 for i in input().split()]
a_list = [[inf for _ in range(n)] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    a_list[a][b] = a_list[b][a] = c
for k in range(n):
    for i in range(n):
        for j in range(n):
            x = a_list[i][k] + a_list[k][j]
            if x < a_list[i][j]:
                a_list[i][j] = a_list[j][i] = x
k = list(itertools.permutations(r_list))
ans = inf
for kk in k:
    temp = 0
    for k1, k2 in zip(kk[:-1], kk[1:]):
        temp += a_list[k1][k2]
    if ans > temp:
        ans = temp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

n,m,rnum = map(int,input().split())
inf = 10**18
shortest = [[inf for i in range(n)] for j in range(n)]
r = list(map(int,input().split()))
for i in range(len(r)):
    r[i]-= 1

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

for i in range(len(shortest)):
    for j in range(len(shortest)):
        for k in range(len(shortest)):
            shortest[j][k] = min(shortest[j][k],shortest[j][i]+shortest[i][k])

ans = inf
# print(shortest)
for p in permutations(r):
    temp = 0
    for i in range(rnum-1):
        temp+=shortest[p[i]][p[i+1]]
    if ans > temp:
        ans = temp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import*

n,m,o=map(int,input().split())
*R,=map(int,input().split())
INF=float("inf")
d=[[INF]*n for _ in range(n)]
r=range
for i in r(n):
	d[i][i]=0
for _ in r(m):
	a,b,c=map(int,input().split())
	d[a-1][b-1]=d[b-1][a-1]=c
for k in r(n):
	for i in r(n):
		for j in r(n):
			d[i][j]=min(d[i][j],d[i][k]+d[k][j])
v=[[d[i-1][j-1]for j in R]for i in R]
m=INF
for t in permutations(r(o)):
	a=0;f=1
	for i,j in zip(t,t[1:]):
		if v[i][j]==INF:
			f=0
			break
		else:
			a+=v[i][j]
	if f:
		m=min(m,a)
print(m)

Submission status: Time Limit Exceeded

Solution code:
n,m,R=map(int,input().split())
r=[int(i) for i in input().split()]
inputs=[]
d=[[10**100 for i in range(n+1)] for i in range(n+1)]
for i in range(m):
    a,b,c=map(int,input().split())
    d[a][b]=c
    d[b][a]=c

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n+1):
        for i in range(n+1):
            for j in range(n+1):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
d=warshall_floyd(d)
ans=10**100
import itertools
for x in itertools.permutations(r):
    p=0
    for i in range(1,R):
        p+=d[x[i-1]][x[i]]
    ans=min(ans,p)
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")
d = [[inf] * (N+1) for _ in range(N+1)]
ans = inf
for _ in range(M): #隣接行列
    A,B,C = map(int, input().split())
    d[A][B] = C
    d[B][A] = C

def warshall_floyd(n):
    for i in range(1,n+1): #経由する点
        for j in range(1,n+1): #始点
            for k in range(1,n+1): #終点
                d[j][k] = min(d[j][k], d[j][i] + d[i][k])

warshall_floyd(N)

for p in permutations(r): #通る町の順列生成
    tmp = 0
    for r1,r2 in zip(p,p[1:]):
        tmp += d[r1][r2]
    ans = min(ans, tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from itertools import permutations
INF = float("inf")


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.V = list(range(N))
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        """辺を加える。edgeは(始点, 終点、重み)からなるリスト
        重みがなければ、重み1とする。
        """
        if len(edge) == 2:
            edge.append(1)
        elif len(edge) != 3:
            print("error in add_edge")
            pass

        s, t, w = edge
        self.E[s].append([t, w])
        self.E[t].append([s, w])  # 無向グラフを仮定。逆向きにも辺を張る

        pass


def Warshall_Floyd(g: Graph):
    """ワーシャルフロイド法により、全節点対の最短距離を求める。O(V^3)
    https://ja.wikipedia.org/wiki/%E3%83%AF%E3%83%BC%E3%82%B7%E3%83%A3%E3%83%AB%E2%80%93%E3%83%95%E3%83%AD%E3%82%A4%E3%83%89%E6%B3%95
    """
    N = g.N
    dist = [[INF]*N for _ in range(N)]
    for from_, toweights in enumerate(g.E):
        for to_, w in toweights:
            dist[from_][to_] = w

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


def solve(N: int, M: int, R: int, r: "List[int]", A: "List[int]", B: "List[int]", C: "List[int]"):

    g = Graph(N)
    for a, b, c in zip(A, B, C):
        g.add_edge([a-1, b-1, c])

    B = Warshall_Floyd(g)

    m = INF
    for order in permutations(r, R):
        counter = 0
        for i in range(R-1):
            counter += B[order[i]-1][order[i+1]-1]
        m = min(m, counter)
    print(m)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    R = int(next(tokens))  # type: int
    r = [int(next(tokens)) for _ in range(R)]  # type: "List[int]"
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    C = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    solve(N, M, R, r, A, B, C)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations


class WarshallFloyd():
    def __init__(self, N):
        self.N = N
        self.d = [[float("inf") for i in range(N)]
                  for i in range(N)]  # d[u][v] : 辺uvのコスト(存在しないときはinf)

    def add(self, u, v, c, directed=False):
        if directed is False:
            self.d[u][v] = c
            self.d[v][u] = c
        else:
            self.d[u][v] = c

    def WarshallFloyd_search(self):
        # これを d[i][j]: iからjへの最短距離 にする
        # 本来無向グラフでのみ全域木を考えるが、二重辺なら有向でも行けそう
        # d[i][i] < 0 なら、グラフは負のサイクルを持つ
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    self.d[i][j] = min(self.d[i][j],
                                       self.d[i][k] + self.d[k][j])
        hasNegativeCycle = False
        for i in range(self.N):
            if self.d[i][i] < 0:
                hasNegativeCycle = True
                break
        for i in range(self.N):
            self.d[i][i] = 0
        return hasNegativeCycle, self.d


N, M, R = map(int, input().split())
r = list(map(int, input().split()))
A = [0] * M
B = [0] * M
C = [0] * M
for i in range(M):
    A[i], B[i], C[i] = map(int, input().split())

graph = WarshallFloyd(N)
for a, b, c in zip(A, B, C):
    graph.add(a - 1, b - 1, c)

hasNegativeCycle, d = graph.WarshallFloyd_search()

ans = float("inf")
for temp in list(permutations(r)):
    cand = 0
    for i in range(R - 1):
        fr = temp[i] - 1
        to = temp[i + 1] - 1
        cand += d[fr][to]
    ans = min(ans, cand)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,m,r = map(int, input().split())
towns = list(map(int, input().split()))
INF = float("inf")
cost = [[INF] * n for _ in range(n)]
#同じ場所にはコスト0で移動（というか移動しないので０）
for i in range(n):
    cost[i][i] = 0

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


ans = INF

for node in itertools.permutations(range(r)): #町移動順の全組み合わせを作成
    tmp = 0
    for x, y in zip(node, node[1:]):
        s, g = towns[x], towns[y] 
        tmp += cost[s-1][g-1] # 町ｓからｇまでの最短距離を足していく
    ans = min(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,r=map(int,input().split())
root=list(map(int,input().split()))
abc=[list(map(int,input().split())) for _ in [0]*m]
inf=10**10
dist=[[inf for _ in [0]*n] for _ in [0]*n]
for i in range(n):dist[i][i]=0
for a,b,c in abc:
    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]))

from itertools import permutations

p=list(permutations(root))

D=10**10
for i in p:
    d=0
    for j in range(len(i)-1):
        d+=dist[i[j]-1][i[j+1]-1]
    D=min(D,d)
print(D)

Submission status: Time Limit Exceeded

Solution code:

import itertools

def do():
    N,M,R = list(map(int,input().split(" ")))
    rs = list(map(int,input().split(" ")))
    INF = 10 ** 20
    graph = [ [INF for _ in range(N + 1)]for _ in range(N + 1)]
    for _ in range(M):
        a,b,c = (map(int, input().split(" ")))
        graph[a][b] = c
        graph[b][a] = c
    for k in range(1,N+1):
        for j in range(1, N + 1):
            for i in range(1, N + 1):
                graph[j][i] = min(graph[j][i] , graph[j][k] + graph[k][i])

    perms = itertools.permutations(rs)
    ans = INF
    for temp in perms:
        cand = 0
        for i in range(0,R-1):
            fr = temp[i]
            to = temp[i + 1]
            cand+= graph[fr][to]
        ans = min(cand,ans)
    print(ans)

if __name__ == "__main__":
    do()

Submission status: Time Limit Exceeded

Solution code:

import itertools

def do():
    N,M,R = list(map(int,input().split(" ")))
    rs = list(map(int,input().split(" ")))
    INF = 10 ** 20
    graph = [ [INF for _ in range(N + 1)]for _ in range(N + 1)]
    for _ in range(M):
        a,b,c = list(map(int, input().split(" ")))
        graph[a][b] = c
        graph[b][a] = c
    for k in range(1,N+1):
        for j in range(1, N + 1):
            for i in range(1, N + 1):
                graph[j][i] = min(graph[j][i] , graph[j][k] + graph[k][i])

    perms = itertools.permutations(rs)
    ans = INF
    for temp in perms:
        cand = 0
        for i,j in zip(range(0,R-1),range(1,R)):
            fr = temp[i]
            to = temp[j]
            cand+= graph[fr][to]
        ans = min(cand,ans)
    print(ans)

if __name__ == "__main__":
    do()

Submission status: Time Limit Exceeded

Solution code:
N,M,R = map(int,input().split())
r = list(map(int,input().split()))
INF = 10**7
G = [[0 if i==j else INF for j in range(N)] for i in range(N)]
for i in range(M):
    A,B,C = map(lambda x:int(x)-1,input().split())
    G[A][B] = C+1
    G[B][A] = C+1
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 = 0
for i in range(1,len(r)):
    ans+=G[r[i-1]-1][r[i]-1]
import itertools
for a in itertools.permutations(r):
    k = 0
    for i in range(1,len(r)):
        k+=G[a[i-1]-1][a[i]-1]
    ans=min(ans,k)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
INF = 10**10
dp = [[INF for i in range(N+1)] for j in range(N+1)]

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

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

ans = 10**10
for route in itertools.permutations(r):
    total = 0
    for i in range(R-1):
        total += dp[route[i]][route[i+1]]
    ans = min(ans, total)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import itertools
import sys
input = sys.stdin.readline

MAX = 1e9

def main():
    N, M, R = map(int, input().split())
    r = list(map(int, input().split()))
    link = [[MAX if j != i else 0 for j in range(N+1)] for i in range(N+1)]

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

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

    ans = MAX
    for per in list(itertools.permutations(r)):
        tmp = 0
        for i in range(R-1):
            tmp += link[per[i]][per[i+1]]
        ans = min(ans, tmp)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
n,m,r=map(int,input().split())
visit=list(map(int,input().split()))
dist=[[10**9]*n for i in range(n)]
for i in range(m):
  a,b,c=map(int,input().split())
  dist[a-1][b-1],dist[b-1][a-1]=c,c
for i in range(n):
  dist[i-1][i-1]=0
for i in range(n):
  for j in range(n):
    for k in range(n):
      dist[j][k]=min(dist[j][k],dist[j][i]+dist[i][k])
ans=10**9
check=permutations(visit)
for i in check:
  c=0
  for j in range(1,r):
    c+=dist[i[j-1]-1][i[j]-1]
  if c<ans:ans=c
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
from collections import defaultdict
from heapq import heappush, heappop


def solve(n, m, r):
    ans = 10**18
    g = defaultdict(list)
    rx = list(i-1 for i in map(int, input().split()))

    for i in range(m):
        s, t, length = map(int, input().split())
        g[s-1].append((length, t-1))
        g[t-1].append((length, s-1))

    d = []
    for k in range(n):
        d.append(dijkstra(n, g, k))

    for p in permutations(rx):
        from_p1_to_pr = 0
        for p_j,  p_next in zip(p, p[1:]):
            from_p1_to_pr += d[p_j][p_next]
        if from_p1_to_pr < ans:
            ans = from_p1_to_pr

    return ans


def dijkstra(vertex, g, sp):
    d = [float('inf')] * vertex
    d[sp] = 0
    heap = [(d[sp], sp)]

    while heap:
        du, u = heappop(heap)
        for length, v in g[u]:

            if d[v] > du + length:
                d[v] = du + length
                heappush(heap, (d[v], v))
    return d


if __name__ == '__main__':
    n, m, r = map(int, input().split())
    print(solve(n, m, r))

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations


def solve(n, m, r):
    ans = 10**18
    d = [[10**18]*n for _ in range(n)]
    rx = list(i-1 for i in map(int, input().split()))

    for i in range(m):
        s, t, length = map(int, input().split())
        d[s-1][t-1] = length
        d[t-1][s-1] = length

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

    for p in permutations(rx, r):
        from_p1_to_pr = 0
        for p_j,  p_next in zip(p, p[1:]):
            from_p1_to_pr += d[p_j][p_next]
        ans = min(ans, from_p1_to_pr)

    return ans


if __name__ == '__main__':
    n, m, r = map(int, input().split())
    print(solve(n, m, r))

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations


def solve(n, m, r):
    ans = float('inf')
    d = [[float("inf")]*n for _ in range(n)]
    rx = list(i-1 for i in map(int, input().split()))

    for i in range(m):
        s, t, length = map(int, input().split())
        d[s-1][t-1] = length
        d[t-1][s-1] = length

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

    for p in permutations(rx, r):
        from_p1_to_pr = 0
        for p_j,  p_next in zip(p, p[1:]):
            from_p1_to_pr += d[p_j][p_next]
        ans = min(ans, from_p1_to_pr)

    return ans


if __name__ == '__main__':
    n, m, r = map(int, input().split())
    print(solve(n, m, r))

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
from heapq import heappush


def solve(n, m, r):
    ans = []
    d = [[float("inf")]*n for _ in range(n)]
    rx = list(map(int, input().split()))
    rx = list(map(lambda x: x-1, rx))

    for i in range(m):
        s, t, length = map(int, input().split())
        d[s-1][t-1] = length
        d[t-1][s-1] = length

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

    for p in permutations(rx, r):
        from_p1_to_pr = 0
        for p_j,  p_next in zip(p, p[1:]):
            from_p1_to_pr += d[p_j][p_next]
        heappush(ans, from_p1_to_pr)

    return ans[0]


if __name__ == '__main__':
    n, m, r = map(int, input().split())
    print(solve(n, m, r))

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations


def solve(n, m, r):
    ans = float('inf')
    d = [[float("inf") for i in range(n)] for i in range(n)]
    rx = list(map(int, input().split()))
    rx = list(map(lambda x: x-1, rx))

    for i in range(m):
        s, t, length = map(int, input().split())
        d[s-1][t-1] = length
        d[t-1][s-1] = length

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

    d = warshall_floyd(d)

    for p in permutations(rx, r):
        from_p1_to_pr = 0
        for j in range(r-1):
            from_p1_to_pr += d[p[j]][p[j+1]]
        ans = min(ans, from_p1_to_pr)

    return ans


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


if __name__ == '__main__':
    n, m, r = map(int, input().split())
    print(solve(n, m, r))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
r = list(map(lambda x: x - 1, r))
d = numpy.array([[10 ** 10] * N for _ in range(N)])

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

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

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

ans = 10 ** 10

for i in itertools.permutations(r):
    dist = 0
    for j in range(R - 1):
        dist += d[i[j]][i[j + 1]]
    ans = min(ans, dist)

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 = list(map(lambda x: x - 1, r))
d = [[10 ** 10] * N for _ in range(N)]

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

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

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

ans = 10 ** 10

for i in itertools.permutations(r):
    dist = 0
    for j in range(R - 1):
        dist += d[i[j]][i[j + 1]]
    ans = min(ans, dist)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N, M, R = map(int, input().split())
TOWNS = [int(i) for i in input().split()]


def warshall_floyd(dist):
    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])
    return dist


def cost(dist, points):
    sum_cost = 0
    for i in range(len(points) - 1):
        sum_cost += dist[points[i] - 1][points[i + 1] - 1]
    return sum_cost


dist = [[float("inf")] * N for i 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 i in range(N):
    dist[i][i] = 0

min_dist = warshall_floyd(dist)
result = float("inf")
for points in itertools.permutations(TOWNS):
    result = min(result, cost(min_dist, points))
print(result)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N, M, R = map(int, input().split())
TOWNS = [int(i) for i in input().split()]
ABC = [map(int, input().split()) for _ in range(M)]


def warshall_floyd(dist):
    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])
    return dist


def cost(dist, points):
    sum_cost = 0
    for i in range(len(points) - 1):
        sum_cost += dist[points[i] - 1][points[i + 1] - 1]
    return sum_cost


dist = [[float("inf") for i in range(N)] for i in range(N)]

for a, b, c in ABC:
    dist[a - 1][b - 1] = c
    dist[b - 1][a - 1] = c

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

min_dist = warshall_floyd(dist)
result = float("inf")
for points in itertools.permutations(TOWNS):
    result = min(result, cost(min_dist, points))
print(result)

Submission status: Time Limit Exceeded

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

N,M,R = map(int,input().split())
r = list(map(int,input().split()))
S = [[]for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    S[a-1].append([b-1,c])
    S[b-1].append([a-1,c])
d = [[float('inf')]*N for i in range(N)]
queue = []
hoge = [0]*(M)
for i in range(N):
    queue = [i]
    d[i][i] = 0
    while queue !=[]:
        l = 0
        for q in queue:
            for next,c in S[q]:
                if d[i][next] > d[i][q]+c:
                    d[i][next] = d[i][q]+c
                    if not(next in hoge[:l]):
                        hoge[l] = next
                        l += 1
        queue = hoge[:l]
def func(x,l):
    if l == []:
        return 0
    ans = float('inf')
    for i in range(len(l)):
        ans =min(ans,func(l[i],l[:i]+l[i+1:]) + d[x-1][l[i]-1])
    return ans
ans = float('inf')
for i in r:
    ans = min(ans,func(i,r))
print(ans)

Submission status: Time Limit Exceeded

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

N,M,R = map(int,input().split())
r = list(map(int,input().split()))
S = [[]for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    S[a-1].append([b-1,c])
    S[b-1].append([a-1,c])
d = [[float('inf')]*N for i in range(N)]
queue = []
hoge = [0]*(M)
for i in range(N):
    queue = [i]
    d[i][i] = 0
    while queue !=[]:
        l = 0
        for q in queue:
            for next,c in S[q]:
                if d[i][next] > d[i][q]+c:
                    hoge[l] = next
                    l += 1
                    d[i][next] = d[i][q]+c
        queue = hoge[:l]
def func(x,l):
    if l == []:
        return 0
    ans = float('inf')
    for i in range(len(l)):
        ans =min(ans,func(l[i],l[:i]+l[i+1:]) + d[x-1][l[i]-1])
    return ans
ans = float('inf')
for i in r:
    ans = min(ans,func(i,r))
print(ans)

Submission status: Time Limit Exceeded

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

N,M,R = map(int,input().split())
r = list(map(int,input().split()))
S = [[]for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    S[a-1].append([b-1,c])
    S[b-1].append([a-1,c])
d = [[float('inf')]*N for i in range(N)]
queue = []
for i in range(N):
    queue = [i]
    d[i][i] = 0
    while queue !=[]:
        hoge = [0]*(M)
        l = 0
        for q in queue:
            for next,c in S[q]:
                if d[i][next] > d[i][q]+c:
                    hoge[l] = next
                    l += 1
                    d[i][next] = d[i][q]+c
        queue = hoge[:l]
def func(x,l):
    if l == []:
        return 0
    ans = float('inf')
    for i in range(len(l)):
        ans =min(ans,func(l[i],l[:i]+l[i+1:]) + d[x-1][l[i]-1])
    return ans
ans = float('inf')
for i in r:
    ans = min(ans,func(i,r))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M,R = map(int,input().split())
r = list(map(int,input().split()))
S = [[]for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    S[a-1].append([b-1,c])
    S[b-1].append([a-1,c])
d = [[float('inf')]*N for i in range(N)]
queue = []
for i in range(N):
    queue = [i]
    d[i][i] = 0
    while queue !=[]:
        hoge = []
        for q in queue:
            for next,c in S[q]:
                if d[i][next] > d[i][q]+c:
                    hoge.append(next)
                    d[i][next] = d[i][q]+c
        queue = hoge
def func(x,l):
    if l == []:
        return 0
    ans = float('inf')
    for i in range(len(l)):
        ans =min(ans,func(l[i],l[:i]+l[i+1:]) + d[x-1][l[i]-1])
    return ans
ans = float('inf')
for i in r:
    ans = min(ans,func(i,r))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M,R = map(int,input().split())
r = list(map(int,input().split()))
S = [[]for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    S[a-1].append([b-1,c])
    S[b-1].append([a-1,c])
d = [[float('inf')]*N for i in range(N)]
queue = []
for i in range(N):
    queue = [i]
    d[i][i] = 0
    while queue !=[]:
        hoge = []
        for q in queue:
            for next,c in S[q]:
                if d[i][next] > d[i][q]+c:
                    hoge.append(next)
                    d[i][next] = d[i][q]+c
        queue = hoge
def func(x,l):
    if l == []:
        return 0
    ans = []
    for i in range(len(l)):
        ans.append(func(l[i],l[:i]+l[i+1:]) + d[x-1][l[i]-1])
    return min(ans)
ans = float('inf')
for i in r:
    ans = min(ans,func(i,r))
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()))

r = [x-1 for x in r]

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

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

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

ans = 1e9

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
abcs = [list(map(int, input().split())) for i in range(M)]
INF = 10**9
dist_list = [[INF if i != j else 0 for j in range(N)] for i in range(N)]

# distance[i][j]で(i, j)間の最短の移動距離を保持
for abc in abcs:
    a = abc[0]-1
    b = abc[1]-1
    c = abc[2]
    if c < dist_list[a][b]:
        dist_list[a][b] = c
        dist_list[b][a] = c
# ワーシャルフロイド
for i in range(1, N):
    for j in range(N):
        for k in range(N):
            dist_list[j][k] = min(dist_list[j][k], dist_list[j][i] + dist_list[i][k])
            dist_list[k][j] = dist_list[j][k]

# 総当たり
result = []


def permutation(data, res):
    global result
    if len(data) == 0:
        result.append(res)
        return

    for i in data:
        _res = res[::]
        _res.append(i)
        _data = data[::]
        _data.remove(i)
        permutation(_data, _res)


permutation(r, [])
min_distance = INF
for res in result:
    distance = 0
    for i in range(1, len(res)):
        x = res[i]-1
        y = res[i-1]-1
        distance += dist_list[x][y]
    if distance < min_distance:
        min_distance = distance
print(min_distance)

Submission status: Time Limit Exceeded

Solution code:
N, M, R = map(int, input().split())
T = list(map(int, input().split()))
D = [[float('INF')] * N for _ in range(N)]
V = [False] * R
for _ in range(M):
    A, B, C = map(int, input().split())
    A -= 1
    B -= 1
    if D[A][B] > C:
        D[A][B] = C
        D[B][A] = C
ans = float('INF')


def dfs(c, s, d):
    global ans
    if c == R + 1:
        if ans > d:
            ans = d
            return

    for i in range(R):
        if V[i] is True:
            continue
        V[i] = True
        if s == -1:
            dfs(c + 1, i, 0)
        else:
            dfs(c + 1, i, d + D[T[s] - 1][T[i] - 1])
        V[i] = False


def main():
    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])
    dfs(1, -1, 0)
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
N, M, R = map(int, input().split())
T = list(map(int, input().split()))
D = [[float('INF')] * N for _ in range(N)]
for _ in range(M):
    A, B, C = map(int, input().split())
    A -= 1
    B -= 1
    if D[A][B] > C:
        D[A][B] = C
        D[B][A] = C


def dfs(i, d, v):
    v[i] = True
    if all(v[t - 1] for t in T) is True:
        return d
    dd = float('INF')
    for j in range(N):
        if v[j] is True:
            continue
        if D[i][j] == 0:
            continue
        dd = min(dd, dfs(j, d + D[i][j], v[::]))
    return dd


def main():
    ans = float('INF')
    for i in range(N):
        v = [False] * N
        ans = min(ans, dfs(i, 0, v[::]))
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
n, m, R = list(map(int, input().split()))
dist = [[float("INF") if i!=j else 0 for i in range(n)] for j in range(n)]
r = list(map(int, input().split()))
for i in range(m):
  a, b, c = list(map(int, input().split()))
  a, b = a-1, b-1
  dist[a][b] = c
  dist[b][a] = 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])

from itertools import permutations
ans = float("INF")
for e in permutations(r):
  cur = 0
  for i in range(R-1):
    cur += dist[e[i]-1][e[i+1]-1]
  ans = min(ans, cur)
print(ans)