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


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

    r = [int(a)-1 for a in input().split()]

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

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

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

    res = float('inf')

    for a, b, c in itertools.product(range(N), repeat=3):
        d[b][c] = min(d[b][c], d[b][a]+d[a][c])

    for perm in itertools.permutations(r):
        a = 0
        for i in range(len(perm)-1):
            a += d[perm[i]][perm[i+1]]
        res = min(a, res)

    print(res)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools


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

    r = [int(a)-1 for a in input().split()]

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

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

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

    res = float('inf')

    for a, b, c in itertools.product(range(N), repeat=3):
        d[b][c] = min(d[b][c], d[b][a]+d[a][c])

    for perm in itertools.permutations(r):
        a = 0
        for i in range(len(perm)-1):
            a += d[perm[i]][perm[i+1]]
        res = min(a, res)

    print(res)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools


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

    r = [int(a)-1 for a in input().split()]

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

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

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

    res = float('inf')

    for a in range(N):
        for b in range(N):
            for c in range(N):
                d[b][c] = min(d[b][c], d[b][a]+d[a][c])

    for perm in itertools.permutations(r):
        a = 0
        for i in range(len(perm)-1):
            a += d[perm[i]][perm[i+1]]
        if a < res:
            # print(perm, a)
            res = a

    print(res)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
N, M, R = map(int, input().split())
r = [int(i) - 1 for i in input().split()]
d = [[float('inf')] * N for j in range(N)]
for i in range(M):
    A, B, C = map(int, input().split())
    d[A-1][B-1] = min(d[A-1][B-1], C)
    d[B-1][A-1] = min(d[A-1][B-1], C)
for k in range(N):
    for s in range(N):
        for e in range(N):
            d[s][e] = min(d[s][e], d[s][k] + d[k][e])
l = True
for o in permutations(r):
    tmp_l = 0
    for s, e in zip(o[:-1], o[1:]):
        tmp_l = tmp_l + d[s][e]
    if l is True:
        l = tmp_l
    else:
        l = min(l, tmp_l)
print(l)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# Youtubeの解説動画を観て
# 他の方のコードを見て
import itertools

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

# １．A -> B間の距離を計算
# ワーシャルフロイド法
# （全点間最短）
inf = float("inf")
lis = [[inf] * N for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    lis[a-1][b-1] = c
    lis[b-1][a-1] = c

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

# ２．たどる順番
## next-permutation
x = inf
for p in itertools.permutations(r_list):
    t = 0
    for k in range(1, R):
        t += lis[p[k-1]-1][p[k]-1]
    x = min(x, t)

print(x)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# Youtubeの解説動画を観て
# 他の方のコードを見て
N, M, R = map(int, input().split())
r_list = [int(i) for i in input().split()]

# １．A -> B間の距離を計算
# ワーシャルフロイド法
# （全点間最短）
lis = [[100000 for i in range(N)] for j in range(N)]
for i in range(M):
    inp = input().split()
    lis[int(inp[0])-1][int(inp[1])-1] = int(inp[2])
    lis[int(inp[1])-1][int(inp[0])-1] = int(inp[2])

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

# ２．たどる順番
## next-permutation
import itertools

x = 100000
for p in itertools.permutations(r_list):
    a = 0
    for k in range(1, R):
        a += lis[p[k-1]-1][p[k]-1]
    x = min(x, a)

print(x)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# Youtubeの解説動画を観て
import numpy as np

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

# １．A -> B間の距離を計算
# ワーシャルフロイド法
# （全点間最短）
lis_raw = [[100000 for i in range(N)] for j in range(N)]
lis = np.array(lis_raw)
for i in range(M):
    inp = input().split()
    lis[int(inp[0])-1][int(inp[1])-1] = int(inp[2])
    lis[int(inp[1])-1][int(inp[0])-1] = int(inp[2])

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

# ２．たどる順番
## next-permutation
import itertools

x = 100000
for p in itertools.permutations(r_list):
    a = 0
    for k in range(1, R):
        a += lis[p[k-1]-1][p[k]-1]
    x = min(x, a)

print(x)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# Youtubeの解説動画を観て
import numpy as np

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

# １．A -> B間の距離を計算
# ワーシャルフロイド法
# （全点間最短）
lis_raw = [[100000 for i in range(N)] for j in range(N)]
for i in range(M):
    inp = input().split()
    lis_raw[int(inp[0])-1][int(inp[1])-1] = int(inp[2])
    lis_raw[int(inp[1])-1][int(inp[0])-1] = int(inp[2])

lis = np.array(lis_raw)

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

# ２．たどる順番
## next-permutation
import itertools

permu = []
for p in itertools.permutations(r_list):
    permu.append(p)

a =0
x = 100000
for i in range(len(permu)):
    for k in range(1, R):
        a += lis[permu[i][k-1]-1][permu[i][k]-1]
    x = min(x, a)
    a = 0

print(x)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# Youtubeの解説動画を観て

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

# １．A -> B間の距離を計算
# ワーシャルフロイド法
# （全点間最短）
lis_raw = [[100000 for i in range(N)] for j in range(N)]
for i in range(M):
    inp = input().split()
    lis_raw[int(inp[0])-1][int(inp[1])-1] = int(inp[2])
    lis_raw[int(inp[1])-1][int(inp[0])-1] = int(inp[2])

lis = lis_raw[:]

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

# ２．たどる順番
## next-permutation
import itertools

np = []
for p in itertools.permutations(r_list):
    np.append(p)

a =0
x = 100000
for i in range(len(np)):
    for k in range(1, R):
        a += lis[np[i][k-1]-1][np[i][k]-1]
    if a < x:
        x = a
        route = np[i]
    a = 0

print(x)

Submission status: Time Limit Exceeded

Solution code:
import itertools, math

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

adj = [[float('inf')] * (N + 1) for _ in range(N + 1)]

for m in range(M):
    A, B, C = map(int, input().split())
    adj[A][B] = min(adj[A][B], C)
    adj[B][A] = min(adj[B][A], C)

res = float('inf')

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

for perm in itertools.permutations(r):
    best = 0
    for x, y in zip(perm, perm[1:]):
        best += adj[x][y]
    res = min(res, best)

print(res)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N,M,R = map(int, input().split())
r = map(int, input().split())
l = [[1e9 for i in range(N+1)] for i in range(N+1)]

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

for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            t = l[i][k] + l[k][j]
            if l[i][j] > t: l[i][j] = t

ans = 1e9
for a in itertools.permutations(r):
    s = 0
    for i,j in zip(a[:-1],a[1:]):
        s += l[i][j]
    if ans > s: ans = s

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N,M,R = map(int, input().split())
r = map(int, input().split())
l = [[1e9 for i in range(N+1)] for i in range(N+1)]

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

for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            t = l[i][k] + l[k][j]
            if l[i][j] > t: l[i][j] = t

ans = 1e9
for a in itertools.permutations(r):
    s = sum(l[i][j] for i,j in zip(a[:-1],a[1:]))
    if ans > s: ans = s

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

def floyd_warshall():
            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])

            
N, M, R = list(map(int, input().split()))
r = (int(i)-1 for i in input().split())
res = float('inf')
dist = [[float("inf")] * N for i in range(N)]
for i in range(N):
        dist[i][i] = 0
for i in range(M):
    a, b, c = list(map(int, input().split()))
    a -= 1
    b -= 1
    dist[a][b] = dist[b][a] = c

floyd_warshall()
for p in permutations(r):
        s = 0
        for i in range(R - 1):
            s += dist[p[i]][p[i + 1]]
        if s < res:
            res = s
print(res)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

def floyd_warshall():
            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])

            
N, M, R = list(map(int, input().split()))
r = (int(i)-1 for i in input().split())
res = float('inf')
dist = [[float("inf")] * N for i in range(N)]

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

floyd_warshall()
for p in permutations(r):
        s = 0
        for i in range(R - 1):
            s += dist[p[i]][p[i + 1]]
        if s < res:
            res = s
print(res)

Submission status: Time Limit Exceeded

Solution code:
def D_joisino_travel(N, M, R, r, A):
    """
    N:国の中の町の数
    M:町を結ぶ道の総数
    R:訪れる町の数
    r:訪れる町の番号
    A:町の結び方とその間の距離
    """
    from itertools import permutations
    INF = float('inf')
    # 道の番号-1が要素の番号
    r = [x - 1 for x in r]
    dist = [[INF]*N for j in range(N)]
    for i in range(N):
        dist[i][i] = 0
    for m, n, c in A:
        m-=1
        n-=1
        dist[m][n] = c
        dist[n][m] = c

    # ワーシャルフロイド法(町A→Bの最短距離を求められる)
    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])

    permutation_route = permutations(r)
    min_dist = INF
    for i in permutation_route:
        cost = 0
        for j in range(R - 1):  # i(行く町の順列)の先頭から2つ要素を拾う
            cost += dist[i[j]][i[j + 1]]  # コストはワーシャルフロイド法で求めてある
        min_dist = min(min_dist, cost)
    return min_dist
  
N,M,R = [int(i) for i in input().split()]
r = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for i in range(M)]
print(D_joisino_travel(N, M, R, r, A))

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

def main():
    def floyd_warshall():
                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])
    
                
    N, M, R = (int(i) for i in input().split())
    r = (int(i)-1 for i in input().split())
    res = float('inf')
    dist = [[float("inf")] * N for i in range(N)]
    
    for i in range(M):
        a, b, c = (int(i) for i in input().split())
        a -= 1
        b -= 1
        dist[a][b] = dist[b][a] = c
    
    floyd_warshall()
    for p in permutations(r):
            s = 0
            for i in range(R - 1):
                s += dist[p[i]][p[i + 1]]
            if s < res:
                res = s
    print(res)
main()

Submission status: Time Limit Exceeded

Solution code:
def D_joisino_travel(N, M, R, r, A):
    """
    N:国の中の町の数
    M:町を結ぶ道の総数
    R:訪れる町の数
    r:訪れる町の番号
    A:町の結び方とその間の距離
    """
    from itertools import permutations
    INF = float('inf')
    # 0行、0列は使わない(番号と配列の要素番号を一致させるため)
    dist = [[INF]*(N+1) for j in range(N + 1)]
    for i in range(1, N + 1):
        dist[i][i] = 0
    for m, n, c in A:
        dist[m][n] = c
        dist[n][m] = c

    # ワーシャルフロイド法(町A→Bの最短距離を求められる)
    for k in range(1, N + 1):
        for i in range(1, N + 1):
            for j in range(1, N + 1):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    permutation_route = permutations(r)
    min_dist = INF
    for i in permutation_route:
        cost = 0
        for j in range(R - 1):  # i(行く町の順列)の先頭から2つ要素を拾う
            cost += dist[i[j]][i[j + 1]]  # コストはワーシャルフロイド法で求めてある
        min_dist = min(min_dist, cost)
    return min_dist
  
N,M,R = [int(i) for i in input().split()]
r = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for i in range(M)]
print(D_joisino_travel(N, M, R, r, A))

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

def floyd_warshall():
            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])
                        
            
def permutation():
    global res
    for p in permutations(r):
        s = 0
        for i in range(R - 1):
            s += dist[p[i]][p[i + 1]]
        if s < res:
            res = s
            
N, M, R = (int(i) for i in input().split())
r = (int(i)-1 for i in input().split())
used = [bool]*9
res = float('inf')
dist = [[float("inf")] * N for i in range(N)]
for i in range(M):
    a, b, c = (int(i) for i in input().split())
    a -= 1
    b -= 1
    dist[a][b] = c
    dist[b][a] = c

floyd_warshall()
permutation()
print(res)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

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

def floyd_warshall():
            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])
                        
# def dfs(c, las, d):
#     global res
#     if c == R+1:
#         if res > d:
#             res = d
#         return
    
#     for i in range(1,R):
#         if used[i] != False:
#             used[i] = True
#             if las == -1:
#                 dfs(c+1,i,0)
#             else:
#                 dfs(c+1, i, d+dist[r[las]][r[i]])
#             used[i] = False
            
def permutation():
    global res
    for p in permutations(r):
        s = 0
        for i in range(R - 1):
            s += dist[p[i]][p[i + 1]]
        if s < res:
            res = s
            
N, M, R = (int(i) for i in input().split())
r = read_int_list()
r = [x - 1 for x in r]
used = [bool]*9
res = float('inf')
dist = [[float("inf") for i in range(201)] for i in range((201))]
for i in range(M):
    a, b, c = (int(i) for i in input().split())
    a -= 1
    b -= 1
    dist[a][b] = c
    dist[b][a] = c

floyd_warshall()
# dfs(1,-1,0)
permutation()
print(res)

Submission status: Time Limit Exceeded

Solution code:
def D_joisino_travel(N, M, R, r, A):
    """
    N:国の中の町の数
    M:町を結ぶ道の総数
    R:訪れる町の数
    r:訪れる町の番号
    A:町の結び方とその間の距離
    """
    from itertools import permutations
    # 0行、0列は使わない(番号と配列の要素番号を一致させるため)
    dist = [[float('inf') for i in range(N + 1)] for j in range(N + 1)]
    for i in range(1, N + 1):
        dist[i][i] = 0
    for m, n, c in A:
        dist[m][n] = c
        dist[n][m] = c

    # ワーシャルフロイド法(町A→Bの最短距離を求められる)
    for k in range(1, N + 1):
        for i in range(1, N + 1):
            for j in range(1, N + 1):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    permutation_route = permutations(r)
    min_dist = float('inf')
    for i in permutation_route:
        cost = 0
        for j in range(len(i) - 1): # i(行く町の順列)の先頭から2つ要素を拾う
            cost += dist[i[j]][i[j + 1]] # コストはワーシャルフロイド法で求めてある
        min_dist = min(min_dist, cost)
    return min_dist
  
N,M,R = [int(i) for i in input().split()]
r = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for i in range(M)]
print(D_joisino_travel(N, M, R, r, A))

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

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

d = [[float('inf') for i in range(N)] for j 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):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]

ans = 10**12

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, m, r = read_line(int, int, int)

rs = [int(r) for r in input().split()]

cities = Counter()

routes = {}
costs = {}
for _ in range(m):
    a, b, c = read_line(int, int, int)

    cities[a] = 1
    cities[b] = 1

    if a in routes:
        routes[a][b] = c
    else:
        routes[a] = { b : c }

    if b in routes:
        routes[b][a] = c
    else:
        routes[b] = { a : c }

for a in cities.keys():
    for b in cities.keys():
        if a not in costs:
            costs[a] = {}
        if b not in costs[a]:
            if a in routes and b in routes[a]:
                costs[a][b] = routes[a][b]
            else:
                costs[a][b] = 100000 + 1

keys = list(cities.keys())

for k in keys:
    for a in keys:
        for b in keys:
            c = costs[a][k] + costs[k][b]
            if costs[a][b] > c:
                costs[a][b] = c

def cost(selected):
    c = 0
    for i in range(len(selected) - 1):
        a = selected[i]
        b = selected[i + 1]
        c += costs[a][b]
    return c

smallest = cost(rs)

def passing_all_cities(selected):
    for r in rs:
        if r not in selected:
            return False
    return True

def f(selected, rest):
    global smallest
    if passing_all_cities(selected):
        c = cost(selected)
        if smallest > c:
            smallest = c
    else:
        for i in range(len(rest)):
            r = rest[i]
            rest_copy = rest[:]
            del rest_copy[i]
            if cost(selected + [r]) < smallest:
                f(selected + [r], rest_copy)

f([], keys)
print(smallest)

Submission status: Time Limit Exceeded

Solution code:
#coding=UTF-8

def search(jun):
    global ans
    global R
    global rrCost
    tmpans=0
    if len(jun)==R:
        mae=jun[0]
        for idx in range(1,R,1):
            ba=jun[idx]
            tmpans += rrCost[mae][ba]
            mae=ba

        if ans==None or tmpans<ans:
            ans=tmpans
    else:
        for me in range(0,R,1):
            if not (me in jun):
                search(jun+[me])

mozir=input()
hyo=mozir.split(' ')
N=int(hyo[0])
M=int(hyo[1])
R=int(hyo[2])

mozir=input()
hyo=mozir.split(' ')
r=[(int(mono)-1) for mono in hyo]

michi=[]
for idx in range(0,M,1):
    mozir=input()
    hyo=mozir.split(' ')
    A=int(hyo[0])-1
    B=int(hyo[1])-1
    C=int(hyo[2])

    michi.append((A,B,C))
    michi.append((B,A,C))

rrCost=[]
for idx in range(0,R,1):
    rrCost.append([None]*R)

for idx in range(0,R,1):
    rrCost[idx][idx]=0

for idr in range(0,R,1):
    deCost=[None]*N
    deCost[r[idr]]=0
    
    miru=[]
    for mono in michi:
        if mono[0] == r[idr]:
            deCost[mono[1]]=mono[2]
            miru.append(mono[1])

            for myon in range(0,R,1):
                if mono[1] == r[myon]:
                    rrCost[idr][myon]=mono[2]
                    rrCost[myon][idr]=mono[2]

    while miru:
        nextmiru=[]
        try:
            rrmax=max(rrCost[idr])
        except:
            rrmax=None
            
        for me in miru:
            preCost=deCost[me]
            for mono in michi:
                if mono[0] == me:
                    tmpCost=preCost+mono[2]
                    if deCost[mono[1]]==None or deCost[mono[1]]>tmpCost:
                        if rrmax==None or tmpCost < rrmax:
                            deCost[mono[1]]=tmpCost
                            nextmiru.append(mono[1])
                            
                            for myon in range(0,R,1):
                                if mono[1] == r[myon]:
                                    rrCost[idr][myon]=tmpCost
                                    rrCost[myon][idr]=tmpCost

        miru=list(set(nextmiru))



ans=None
search([])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
INF=99999999

#入力(面倒なので0-basedに変換する)
N,M,R=[int(i) for i in input().split()]
d=[[0 if i==j else INF for j in range(N)] for i in range(N)]
r=[int(i)-1 for i in input().split()]
used=[False for i in range(R)]
res=INF
for i in range(M):
	A,B,C=[int(i) for i in input().split()]
	A-=1;B-=1
	if d[A][B]>C:
		d[A][B]=C
		d[B][A]=C

#変数が定義し終えたのでここで関数を定義しておく
def dfs(c,las,dist):
	if c == R+1:
		global res
		if(res>dist):
			res=dist
		return
	for i in range(R):
		if not used[i]:
			used[i]=True
			if(las==-1):
				dfs(c+1,i,0)
			else:
				dfs(c+1,i,dist+d[r[las]][r[i]])
			used[i]=False
		
#計算
for k in range(N):
	for i in range(N):
		for j in range(N):
			if d[i][j]>d[i][k]+d[k][j]:
				d[i][j]=d[i][k]+d[k][j]
dfs(1,-1,0)
print(res)

Submission status: Time Limit Exceeded

Solution code:
INF=9999999999999

#入力(面倒なので0-basedに変換する)
N,M,R=[int(i) for i in input().split()]
d=[[0 if i==j else INF for j in range(N)] for i in range(N)]
r=[int(i)-1 for i in input().split()]
used=[False for i in range(R)]
res=INF
for i in range(M):
	A,B,C=[int(i) for i in input().split()]
	A-=1;B-=1
	if d[A][B]>C:
		d[A][B]=d[B][A]=C

#変数が定義し終えたのでここで関数を定義しておく
def dfs(c,las,dist):
	global res
	if c == R+1:
		if(res>dist):
			res=dist
		return
	for i in range(R):
		if not used[i]:
			used[i]=True
			if(las==-1):dfs(c+1,i,0)
			else: dfs(c+1,i,dist+d[r[las]][r[i]])
			used[i]=False
		
#計算
for k in range(N):
	for i in range(N):
		for j in range(N):
			if d[i][j]>d[i][k]+d[k][j]:
				d[i][j]=d[i][k]+d[k][j]
dfs(1,-1,0)
print(res)

Submission status: Time Limit Exceeded

Solution code:
#coding=UTF-8

def search(jun):
    global ans
    global R
    global rrCost
    tmpans=0
    if len(jun)==R:
        mae=jun[0]
        for idx in range(1,R,1):
            ba=jun[idx]
            tmpans += rrCost[mae][ba]
            mae=ba

        if ans==None or tmpans<ans:
            ans=tmpans
    else:
        for me in range(0,R,1):
            if not (me in jun):
                search(jun+[me])

mozir=input()
hyo=mozir.split(' ')
N=int(hyo[0])
M=int(hyo[1])
R=int(hyo[2])

mozir=input()
hyo=mozir.split(' ')
r=[(int(mono)-1) for mono in hyo]

michi=[]
for idx in range(0,M,1):
    mozir=input()
    hyo=mozir.split(' ')
    A=int(hyo[0])-1
    B=int(hyo[1])-1
    C=int(hyo[2])

    michi.append((A,B,C))
    michi.append((B,A,C))

rrCost=[]
for idx in range(0,R,1):
    rrCost.append([None]*R)

for idx in range(0,R,1):
    rrCost[idx][idx]=0

for idr in range(0,R,1):
    deCost=[None]*N
    deCost[r[idr]]=0
    
    miru=[]
    for mono in michi:
        if mono[0] == r[idr]:
            deCost[mono[1]]=mono[2]
            miru.append(mono[1])

    while miru:
        nextmiru=[]

        for me in miru:
            preCost=deCost[me]
            for mono in michi:
                if mono[0] == me:
                    tmpCost=preCost+mono[2]
                    if deCost[mono[1]]==None or deCost[mono[1]]>tmpCost:
                        deCost[mono[1]]=tmpCost
                        nextmiru.append(mono[1])

        miru=list(set(nextmiru))

    for idx in range(0,R,1):
        rrCost[idr][idx]=deCost[r[idx]]
        rrCost[idx][idr]=deCost[r[idx]]


ans=None
search([])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M,R = map(int,input().split())
r = list(map(int,input().split()))
from itertools import permutations
t = [[float('inf') for i in range(N)] for j in range(N)]

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

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

def c(l):
    ret = 0
    for i in range(R-1):
        ret += t[l[i]-1][l[i+1]-1]
    return ret

print(min([c(i) for i in permutations(r)]))

Submission status: Time Limit Exceeded

Solution code:
import itertools
def dist(a, b, l):
# 	return (l[a][b]+l[b][a])
	
	if l[a][b] == 0: return (l[b][a])
	if l[b][a] == 0: return (l[a][b])
	
	if l[a][b] > l[b][a]:
		return (l[b][a])
	else:
		return (l[a][b])


# 初期化
ans = float('inf')

#入力
N, M, R = map(int, input().split())		# 5 7 2

r = [int(i) for i in input().split()]	# 1 2 3 4 5 ...
r = list(set(r))


c = [[ans for i in range(N+1)] for j in range(N+1)]
for i in range(N+1):
	c[i][i] = 0

for i in range(1, M+1):
	A, B, C = map(int, input().split())		# 5 7 2
	c[A][B]=C
	c[B][A]=C




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


# print(c)
# print(dist(A, B, c))

# for i in range(len(r)-1):
# # 	print(r[i])
# 	ans += dist(r[i], r[i+1], c)

# print(ans)

for l in list(itertools.permutations(r)):
	sum = 0
	for i in range(len(l)-1):
#		sum += dist(l[i], l[i+1], c)
		sum += c[l[i]][l[i+1]]
	
	ans = min(ans, sum)
#	print(l, sum, ans)


print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
def dist(a, b, l):
# 	return (l[a][b]+l[b][a])
	
	if l[a][b] == 0: return (l[b][a])
	if l[b][a] == 0: return (l[a][b])
	
	if l[a][b] > l[b][a]:
		return (l[b][a])
	else:
		return (l[a][b])


# 初期化
ans = float('inf')

#入力
N, M, R = map(int, input().split())		# 5 7 2

r = [int(i) for i in input().split()]	# 1 2 3 4 5 ...
r = list(set(r))


c = [[ans for i in range(N+1)] for j in range(N+1)]
for i in range(N+1):
	c[i][i] = 0

for i in range(1, M+1):
	A, B, C = map(int, input().split())		# 5 7 2
	c[A][B]=C
	c[B][A]=C




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


# print(c)
# print(dist(A, B, c))

ans = 100000 * 200 * 200

# for i in range(len(r)-1):
# # 	print(r[i])
# 	ans += dist(r[i], r[i+1], c)

# print(ans)

for l in list(itertools.permutations(r)):
	sum = 0
	for i in range(len(l)-1):
		sum += dist(l[i], l[i+1], c)
	
	ans = min(ans, sum)
#	print(l, sum, ans)


print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, m, r = read_line(int, int, int)

rs = [int(r) for r in input().split()]

cities = Counter()

routes = {}
costs = {}
for _ in range(m):
    a, b, c = read_line(int, int, int)

    cities[a] = 1
    cities[b] = 1

    if a in routes:
        routes[a][b] = c
    else:
        routes[a] = { b : c }

    if b in routes:
        routes[b][a] = c
    else:
        routes[b] = { a : c }

for a in cities.keys():
    for b in cities.keys():
        if a not in costs:
            costs[a] = {}
        if b not in costs[a]:
            if a in routes and b in routes[a]:
                costs[a][b] = routes[a][b]
            else:
                costs[a][b] = 100000 + 1

for k in cities.keys():
    for a in cities.keys():
        for b in cities.keys():
            if costs[a][b] > costs[a][k] + costs[k][b]:
                costs[a][b] = costs[a][k] + costs[k][b]

def cost(selected):
    c = 0
    for i in range(len(selected) - 1):
        a = selected[i]
        b = selected[i + 1]
        c += costs[a][b]
    return c

smallest = 100000 + 1

def f(selected, rest):
    global smallest
    if len(rest) == 0:
        c = cost(selected)
        if smallest > c:
            smallest = c
    else:
        for i in range(len(rest)):
            r = rest[i]
            rest_copy = rest[:]
            del rest_copy[i]
            # if cost(selected + [r]) < smallest:
            #     f(selected + [r], rest_copy)
            f(selected + [r], rest_copy)

f([], list(rs))
print(smallest)