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: Runtime Error

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

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

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

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

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

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

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

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

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

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

Submission status: Runtime Error

Solution code:
INF = 10**10
n,m,R = map(int,input().split())
r=list(map(int,input().split()))
d = [[INF]*n for i in range(n)] 
# 入力
for i in range(m):
    a,b,c = map(int,input().split())
    a,b = a-1, b-1
    d[a][b] = c
    d[b][a] = c # 無向グラフ
for i in range(n):
    d[i][i] = 0

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

from itertools import permutations, combinations

ans=10**10
for v in permutations(r):
    tmp=0
    for i in range(R-1):
        tmp+=d[v[i]][v[i+1]]
    ans=min(ans,tmp)
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

from itertools import permutations

n,m,R = [int(i) for i in input().split()]

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

mat = np.ones([n,n]) *float('inf')

for i in range(m):
    a, b, c = [int(i) for i in input().split()]
    a -= 1
    b -= 1
    mat[a,b] = c
    mat[b,a] = c
    
    
def floyd_warshall(weights,V):
    distance_matrix = weights
    next_distance_matrix = distance_matrix
    for k in range(V):
        for i in range(V):
            for j in range(V):
                next_distance_matrix[i,j] = min(distance_matrix[i,j], distance_matrix[i,k] + distance_matrix[k,j])
        distance_matrix = next_distance_matrix
    return distance_matrix

dis = floyd_warshall(mat,n)


ans = float('inf')
for ite in permutations(r):
    cand = 0
    for i in range(R-1):
        cand += dis[ite[i],ite[i+1]]
    if cand < ans:
        ans = cand
        
print(int(ans))

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import floyd_warshall
import numpy as np
from itertools import permutations

n,m,r = map(int,input().split())
rr = np.array(list(map(int,input().split()))) - 1

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

shortest = floyd_warshall(L, directed = False)

ans = float('inf')

for route in permutations(rr,len(rr)):
    ans = min(ans, shortest[route[:-1],route[1:]].sum())
print(int(ans))

Submission status: Runtime Error

Solution code:
from collections import deque
import copy
n, m, r = map(int,input().split())
R = list(map(int, input().split()))
tree = [[] for _ in range(n+1)]
for i in range(m):
    a, b, c = map(int, input().split())
    tree[a].append([b, c])
    tree[b].append([a, c])

result = []
for i in R:
    visit = [-1 for _ in range(n+1)]
    visit[i] = 0
    q = deque([[i, visit]])
    while q:
        x, v = q.pop()
        for y, c in tree[x]:
            next_v = copy.deepcopy(v)
            if v[y]<0:
                next_v[y] = v[x]+c
                if all(next_v[j]>=0 for j in R):
                    result.append(next_v[y])
                else:
                    q.append([y, copy.deepcopy(next_v)])

print(min(result))

Submission status: Runtime Error

Solution code:
from collections import deque
n, m, r = map(int,input().split())
R = list(map(int, input().split()))
tree = [[] for _ in range(n+1)]
for i in range(m):
    a, b, c = map(int, input().split())
    tree[a].append([b, c])
    tree[b].append([a, c])

result = [10**9]
for i in R:
    visit = [-1 for _ in range(n+1)]
    visit[i] = 0
    q = deque([[i, visit.copy()]])
    while q:
        x, v = q.pop()
        for y, c in tree[x]:
            next_v = v.copy()
            if v[y]<0:
                next_v[y] = v[x]+c
                if all(next_v[j]>=0 for j in R):
                    result.append(next_v[y])
                else:
                    q.append([y, next_v.copy()])

print(min(result))

Submission status: Runtime Error

Solution code:
from collections import deque
n, m, r = map(int,input().split())
R = list(map(int, input().split()))
tree = [[] for _ in range(n+1)]
for i in range(m):
    a, b, c = map(int, input().split())
    tree[a].append([b, c])
    tree[b].append([a, c])

result = []
for i in R:
    visit = [-1 for _ in range(n+1)]
    visit[i] = 0
    q = deque([[i, visit.copy()]])
    while q:
        x, v = q.pop()
        for y, c in tree[x]:
            next_v = v.copy()
            if v[y]<0:
                next_v[y] = v[x]+c
                if all(next_v[j]>=0 for j in R):
                    result.append(next_v[y])
                else:
                    q.append([y, next_v.copy()])

print(min(result))

Submission status: Runtime Error

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

from itertools import permutations
from numba import jit
import numpy as np

HUGE = 10 ** 18

def main():
    n, m, r = map(int, input().split())
    togo = list(map(int, input().split()))
    adj_mat = [[HUGE for j in range(n)] for i in range(n)]
    for i in range(n):
        adj_mat[i][i] = HUGE
    for i in range(m):
        a, b, c = map(int, input().split())
        a0 = a - 1
        b0 = b - 1
        adj_mat[a0][b0] = c
        adj_mat[b0][a0] = c
    adj_mat = np.array(adj_mat)

    wf(adj_mat, n)

    res = HUGE
    for way in permutations(togo):
        assert len(way) > 1
        x = 0
        for i in range(len(way) - 1):
            x += adj_mat[way[i] - 1][way[i + 1] - 1]
        res = min(res, x)

    print(res)

@jit(nopython=True)
def wf(adj_mat, n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                adj_mat[i][j] = min(adj_mat[i][j], adj_mat[i][k] + adj_mat[k][j])

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import heapq
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
for i in range(R):
    r[i] -= 1
edge = [[] for i in range(N)]
for i in range(M):
    x, y, z = map(int, input().split())
    edge[x-1].append((z, y-1))
    edge[y-1].append((z, x-1))

MIN = 10**10
for i in range(R):
    ans = 0
    d = [float("inf")] * N
    used = [True] * N
    place = set(r.copy())
    place.remove(r[i])
    d[r[i]] = 0
    used[r[i]] = False
    edgelist = []

    for e in edge[r[i]]:
        heapq.heappush(edgelist, e)

    while place != set():
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        if v in place:
            place.remove(v)
            ans += d[v]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist, (e[0]+d[v], e[1]))
    MIN = min(ans, MIN)
    
print(MIN)

Submission status: Runtime Error

Solution code:
import itertools
from scipy.sparse.csgraph import floyd_warshall

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

INF = 10**10

d = [[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
    if d[a][b] > c:
        d[a][b] = c
        d[b][a] = c


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


# d = floyd_warshall(d)
warshall(d)


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

    if ans > dist:
        ans = dist

print(int(ans))

Submission status: Runtime Error

Solution code:
import itertools
from scipy.sparse.csgraph import floyd_warshall

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

INF = 10**10

d = [[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
    if d[a][b] > c:
        d[a][b] = c
        d[b][a] = c

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

d = froyd_warshall(d)


ans = INF
for p in itertools.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: Runtime Error

Solution code:
import itertools
from scipy.sparse import scr_matrix
from scipy.sparse.csgraph import froyd_warshall


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

INF = 10**10

d = [[INF] * (N+1) for _ in range(N+1)]

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

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

    if d[a][b] > c:
        d[a][b] = c
        d[b][a] = c

graph = csr_matrix(d)

dist_matrix, predesessors = froyd_warshall(
    csgraph=graph, directed=False, return_predesessor=True)

d = dist_matrix


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


ans = INF
for p in itertools.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: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc073/tasks/abc073_d

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))



# default import
from itertools import product, permutations, combinations

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

# ダイクストラか？
# 全点間の最小距離を取得
# rについてpermutationして。その通りに訪れたときの距離をシミュレーション
# 最小値を選ぶ

N, M, r = read_ints()
R = [x - 1 for x in read_ints()]
adj_mat = [[0] * M for _ in range(M)]
for _ in range(M):
    a, b, c = read_ints()
    a -= 1
    b -= 1
    adj_mat[a][b] = c
    adj_mat[b][a] = c

D = dijkstra(csr_matrix(adj_mat, dtype='int'), directed=False)
# print(D)
# 全探索パート
ans = 2 ** 31


def get_kyori(p):
    ret = 0
    for ps, pt in zip(p[:-1], p[1:]):
        ret += D[ps, pt]
    return ret


for p in permutations(R):
    ans = min(ans, get_kyori(p))
print(int(ans))

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc073/tasks/abc073_d

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))



# default import
from itertools import product, permutations, combinations

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

# ダイクストラか？
# 全点間の最小距離を取得
# rについてpermutationして。その通りに訪れたときの距離をシミュレーション
# 最小値を選ぶ

N, M, r = read_ints()
R = [x - 1 for x in read_ints()]
adj_mat = [[0] * M for _ in range(M)]
for _ in range(M):
    a, b, c = read_ints()
    a -= 1
    b -= 1
    adj_mat[a][b] = c
    adj_mat[b][a] = c

D = dijkstra(csr_matrix(adj_mat, dtype='int'), directed=False)
# print(D)
# 全探索パート
ans = 2**63
for p in permutations(R):
    tmp = 0
    for i in range(r - 1):
        tmp += D[p[i], p[i + 1]]
    ans = min(ans, tmp)
print(int(ans))

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc073/tasks/abc073_d

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))



# default import
from itertools import product, permutations, combinations

from scipy.sparse import csr_matrix, lil_matrix
from scipy.sparse.csgraph import dijkstra

# ダイクストラか？
# 全点間の最小距離を取得
# rについてpermutationして。その通りに訪れたときの距離をシミュレーション
# 最小値を選ぶ

N, M, r = read_ints()
R = read_ints()
adj_mat = [[0] * M for _ in range(M)]
for _ in range(M):
    a, b, c = read_ints()
    a -= 1
    b -= 1
    adj_mat[a][b] = c
    adj_mat[b][a] = c

D = dijkstra(csr_matrix(adj_mat), directed=False)
# print(D)
# 全探索パート
ans = 2**63
for p in permutations(R):
    tmp = 0
    for i in range(r - 1):
        tmp += D[p[i] - 1, p[i + 1] - 1]
    ans = min(ans, tmp)
print(int(ans))

Submission status: Runtime Error

Solution code:
from itertools import permutations as perm

n, m, r = map(int, input().split())
r = list(map(lambda x: int(x) - 1, input().split()))
d = [[10 ** 5] * m for _ in range(m)]
for i in range(m):
    abc = tuple(map(int, input().split()))
    a = abc[0] - 1
    b = abc[1] - 1
    c = abc[2]
    d[a][b] = c
    d[b][a] = c
for k in range(m):
    for i in range(m):
        for j in range(m):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])
            d[j][i] = min(d[j][i], d[i][k] + d[k][j])

ans = 8 * (10 ** 5)
for arr in perm(r, len(r)):
    rep = 0
    for i in range(len(arr) - 1):
        rep += d[arr[i]][arr[i + 1]]
    ans = min(ans, rep)
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import permutations
N, M, R, *L = map(int, open('0').read().split())
city = L[:R]
inf = L[R:]
dist = [[10**10]*N for i in range(N)]
for x,y,c in zip(*[iter(inf)]*3):
  dist[x-1][y-1] = c
  dist[y-1][x-1] = c
for i in range(N):
  dist[i][i] = 0

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 = 10**10
for m in permutations(city):
  n = 0
  for i in range(R-1):
    n += dist[m[i]-1][m[i+1]-1]
  ans = min(ans,n)
  print(n,m)
print(ans)

Submission status: Runtime Error

Solution code:
n, m, R = map(int, input().split())
r = list(map(int, input().split()))
inf = 10**10
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append([b, c])
    graph[b].append([a, c])


def dfs(visited, r_num, length):
    if r_num == R:
        return length
    now = visited[-1]
    ret = []
    for i, v in graph[now]:
        if i in r:
            ret.append(dfs(visited + [i], r_num + 1, length + v))
            continue
        ret.append(dfs(visited + [i], r_num, length + v))
    return min(ret)


ans = inf
for start in r:
    ans = min(ans, dfs([start], 1, 0))
print(ans)

Submission status: Runtime Error

Solution code:
#include <iostream> 
#include <algorithm>
#include <vector>
//#include <string>
#include <queue>
//#include <functional>
using namespace std;

int main() {
    const long INF = 100000*200;
    int N, M, R;
    cin >> N >> M >> R;
    vector<int> r;
    for (int i=0; i<R; i++) {
        int x;
        cin >> x;
        r.push_back(x-1);
    }
    long dp[200][200];
    for (int i=0; i<200; i++) {
        for (int j=0; j<200; j++) {
           dp[i][j] = INF;
        }
    }
    for (int i=0; i<M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        dp[a][b] = c;
        dp[b][a] = c;
    }
    for (int k=0; k<N; k++)
        for (int i=0; i<N; i++)
            for (int j=0; j<N; j++)
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]);
    long long ans = -1;
    do {
        long long tmp = 0;
        for (int i=0; i<R-1; i++)
            tmp += dp[r[i]][r[i+1]];
        if (ans == -1) ans = tmp;
        else ans = min(ans, tmp);
    } while(next_permutation(r.begin(), r.end()));
    cout << ans;
    return 0;
}

Submission status: Runtime Error

Solution code:
N,M,R=map(int, input().split())
r=map(lambda x:int(x)-1, input().split())
dp=[[10**9]*N for _ in range(N)]
for _ in range(M):
    A,B,C=map(int, input().split())
    A-=1
    B-=1
    dp[A][B]=C
    dp[B][A]=C
for z in range(N):
    for x in range(N):
        for y in range(N):
            dp[x][y]=min(dp[x][y], dp[x][z]+dp[z][y])

import itertools
ans=10**9
for p in itertools.permutations(range(R)):
    t=0
    rp=[r[i] for i in p]
    for i in range(R-1):
        t+=dp[rp[i]][rp[i+1]]
    ans=min(ans,t)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import shortest_path
from itertools import permutations

input = sys.stdin.readline
ans = -1

n, m, r = map(int, input().split())
r  = list(map(int, input().split()))
A, B, C = [], [], []
for i in range(m):
    a, b, c = map(int, input().split())
    A.append(a-1)
    B.append(b-1)
    C.append(c)

wf = shortest_path(csr_matrix((C, (A, B)), shape = (n, n)), directed=False)

for pi in permutations(r):
    cand = 0
    for r1, r2 in zip(pi, pi[1:]):
        d = wf[r1-1][r2-1]
        if d == float('inf'):
            break
        cand += int(d)
    if ans < 0 or ans > cand:
        ans = cand

print(ans)

Submission status: Runtime Error

Solution code:
import sys
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import shortest_path
from itertools import permutations

input = sys.stdin.readline
ans = -1

n, m, r = map(int, input().split())
r  = list(map(int, input().split()))
A, B, C = [], [], []
for i in range(m):
    a, b, c = map(int, input().split())
    A.append(a-1)
    B.append(b-1)
    C.append(c)

wf = shortest_path(csr_matrix((C, (A, B)), shape = (n, n)), directed=False)

for pi in permutations(r):
    cand = 0
    for r1, r2 in zip(pi, pi[1:]):
        cand += int(wf[r1-1][r2-1])
    if ans < 0 or ans > cand:
        ans = cand

print(ans)

Submission status: Runtime Error

Solution code:
import sys
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import shortest_path
from itertools import permutations

input = sys.stdin.readline
ans = -1

n, m, r = map(int, input().split())
r  = list(map(int, input().split()))
A, B, C = [], [], []
for i in range(m):
    a, b, c = map(int, input().split())
    A.extend(a-1)
    B.extend(b-1)
    C.extend(c)

wf = shortest_path(csr_matrix((C, (A, B)), shape = (n, n)), directed=False)

for pi in permutations(r):
    cand = 0
    for r1, r2 in zip(pi, pi[1:]):
        cand += int(wf[r1-1][r2-1])
    if ans < 0 or ans > cand:
        ans = cand

print(ans)

Submission status: Runtime Error

Solution code:
import sys
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import shortest_path
from itertools import permutations

input = sys.stdin.readline
ans = -1

n, m, r = map(int, input().split())
r  = list(map(int, input().split()))
A, B, C = [], [], []
for i in range(m):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    A.extend([a, b])
    B.extend([b, a])
    C.extend([c, c])

wf = shortest_path(csr_matrix((C, (A, B)), shape = (n, n)))

for pi in permutations(r):
    cand = 0
    for r1, r2 in zip(pi, pi[1:]):
        cand += int(wf[r1-1][r2-1])
    if ans < 0 or ans > cand:
        ans = cand

print(ans)

Submission status: Runtime Error

Solution code:
def warshall_floyd(n, dist):
    min_dist = dist.copy()
    for k in range(n):
        for i in range(n):
            for t in range(n):
                min_dist[i][t] = min(min_dist[i][t], min_dist[i][k] + min_dist[k][t])
        
    return min_dist
    
n, m, r = map(int, input().split())
r = list(map(int, input().split()))
edge = [[0] * n for _ in range(n)]

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

dist = warshall_floyd(n, edge)

ans = float('inf')
for pr in permutations(r):
    temp = 0
    for i in range(len(r)-1):
        temp += dist[pr[i]-1][pr[i+1]-1]
        if temp >= ans: break
    
    ans = min(ans, temp)
    
print(ans)

Submission status: Runtime Error

Solution code:
from collections import *
from itertools import *
import copy

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

data=[[] for i in range(N+1)]
nagasa={}
for a,b,c in ABC:
    data[a].append(b)
    data[b].append(a)
    A,B=min(a,b),max(a,b)
    nagasa.update({str(A)+" "+str(B):c})
mokutekiti=[[0 for i in range(R)] for m in range(R)]
for r1i in range(R-1):
    for r2i in range(r1i+1,R):
        r1=Rlst[r1i]
        r2=Rlst[r2i]
        stack=deque([[r1,set([r1]),r1]])
        visited=set([r1])
        ikulst=set()
        while stack:
            a,miti,mae=stack.popleft()
            for b in data[a]:
                if b!=mae:
                    if not b in visited:
                        visited.add(b)
                        tempmiti=copy.copy(miti)
                        tempmiti.add(b)
                        if b==r2:
                            ikulst=ikulst|tempmiti
                        else:
                            stack.append([b,tempmiti,a])
                    elif b in ikulst:
                        ikulst=ikulst|miti


        """
        stack=[[r1,0]]
        minpoint=[100000*200+1 for i in range(N+1)]
        while stack:
            a,m=stack.pop()
            for b in data[a]:
                if b in ikulst:
                    A,B=min(a,b),max(a,b)
                    tempm=m+nagasa[str(A)+" "+str(B)]
                    if tempm<minpoint[b]:
                        minpoint[b]=tempm
                        if b==r2:
                            pass
                        else:
                            stack.append([b,tempm])"""
        mokutekiti[r1i][r2i]=minpoint[r2]
        mokutekiti[r2i][r1i]=minpoint[r2]

value=[]
for lst in permutations([i for i in range(R)],R):
    nagasa=0
    for i in range(R-1):
        nagasa+=mokutekiti[lst[i]][lst[i+1]]
    value.append(nagasa)
print(min(value))

Submission status: Runtime Error

Solution code:
from collections import *
from itertools import *
import copy

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

data=[[] for i in range(N+1)]
nagasa={}
for a,b,c in ABC:
    data[a].append(b)
    data[b].append(a)
    A,B=min(a,b),max(a,b)
    nagasa.update({str(A)+" "+str(B):c})
mokutekiti=[[0 for i in range(R)] for m in range(R)]
for r1i in range(R-1):
    for r2i in range(r1i+1,R):
        r1=Rlst[r1i]
        r2=Rlst[r2i]
        mitilst=[]
        stack=[[r1,0]]
        minpoint=[100000 for i in range(N+1)]
        while stack:
            a,m=stack.pop()
            for b in data[a]:
                A,B=min(a,b),max(a,b)
                tempm=m+nagasa[str(A)+" "+str(B)]
                if tempm<minpoint[b]:
                    minpoint[b]=tempm
                    if b==r2:
                        mitilst.append(tempm)
                    else:
                        stack.append([b,tempm])
        mitilst=min(mitilst)
        mokutekiti[r1i][r2i]=mitilst
        mokutekiti[r2i][r1i]=mitilst

value=[]
for lst in permutations([i for i in range(R)],R):
    nagasa=0
    for i in range(R-1):
        nagasa+=mokutekiti[lst[i]][lst[i+1]]
    value.append(nagasa)
print(min(value))

Submission status: Runtime Error

Solution code:
from collections import *
from itertools import *
import copy

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

data=[[] for i in range(N+1)]
nagasa={}
for a,b,c in ABC:
    data[a].append(b)
    data[b].append(a)
    A,B=min(a,b),max(a,b)
    nagasa.update({str(A)+" "+str(B):c})
mokutekiti=[[0 for i in range(R)] for m in range(R)]
for r1i in range(R-1):
    for r2i in range(r1i+1,R):
        r1=Rlst[r1i]
        r2=Rlst[r2i]
        mitilst=[]
        stack=[[r1,[r1],0]]
        minpoint=[100000 for i in range(N+1)]
        while stack:
            a,miti,m=stack.pop()
            for b in data[a]:
                A,B=min(a,b),max(a,b)
                tempm=m+nagasa[str(A)+" "+str(B)]

                if tempm<minpoint[b]:
                    minpoint[b]=tempm
                    tempmiti=copy.copy(miti)
                    tempmiti.append(b)
                    if b==r2:
                        mitilst.append(tempm)
                    else:
                        stack.append([b,tempmiti,tempm])
        mitilst=min(mitilst)
        mokutekiti[r1i][r2i]=mitilst
        mokutekiti[r2i][r1i]=mitilst

value=[]
for lst in permutations([i for i in range(R)],R):
    nagasa=0
    for i in range(R-1):
        nagasa+=mokutekiti[lst[i]][lst[i+1]]
    value.append(nagasa)
print(min(value))

Submission status: Runtime Error

Solution code:
import math
import numpy as np
from scipy.sparse.csgraph import dijkstra

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

connections = np.zeros((N,N))
for i in range(M):
    A,B,C = list(map(int,input().split()))
    A,B = A-1,B-1
    
    connections[A][B] = C
    connections[B][A] = C

connections = dijkstra(connections)

def explore(unvisited,total,start):
    if unvisited:
        ret = math.inf
        for town in unvisited:
            ret = min(ret,explore(unvisited-set([town]),
                total+connections[start][town],town))
        return ret
    else:
        return total

ans = math.inf
targets = set(r)
for s in r:
    ans = min(ans,explore(targets-set([s]),0,s))
print(int(ans))

Submission status: Runtime Error

Solution code:
n, m, R = list(map(int, input().split()))
r = list(map(int, input().split()))
abc = [list(map(int, input().split())) for _ in range(m)]

from collections import defaultdict
import math

d = defaultdict(lambda: math.inf)

for a, b, c in abc:
  d[(a, b)] = c
  d[(b, a)] = c

for x in range(1, n + 1):
  d[(x, x)] = 0

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)])
      d[(j, i)] = d[(i, j)]

import itertools
costs = []
for per in itertools.permutations(r, r=R):
  cost = 0
  for i in range(R - 1):
    cost += d[(per[i], per[i + 1])]
  costs.append(cost)

print(min(costs))

Submission status: Runtime Error

Solution code:
n, m, R = list(map(int, input().split()))
r = list(map(int, input().split()))
abc = [list(map(int, input().split())) for _ in range(m)]

from collections import defaultdict
import math

d = defaultdict(lambda: math.inf)

for a, b, c in abc:
  d[(a, b)] = c
  d[(b, a)] = c

for x in range(1, n + 1):
  d[(x, x)] = 0

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

import itertools
costs = []
for per in itertools.permutations(r, r=R):
  cost = 0
  for i in range(R - 1):
    cost += d[(per[i], per[i + 1])]
  costs.append(cost)

print(min(costs))

Submission status: Runtime Error

Solution code:
n, m, R = list(map(int, input().split()))
r = list(map(int, input().split()))
abc = [list(map(int, input().split())) for _ in range(m)]

from collections import defaultdict
from math import inf

d = defaultdict(lambda: inf)

for a, b, c in abc:
  d[(a, b)] = c
  d[(b, a)] = c

for x in range(1, n + 1):
  d[(x, x)] = 0

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

import itertools
costs = []
for per in itertools.permutations(r, r=R):
  cost = 0
  for i in range(R - 1):
    cost += d[(per[i], per[i + 1])]
  costs.append(cost)

print(min(costs))

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
#define INF 100000000000

signed main(){
  ll n,m,r;cin >> n >> m >> r;
  vector<ll> rx(r);for(int i=0;i<r;i++)cin >> rx[i];
  vector<vector<ll>> wf(n,vector<ll>(n,INF));
  for(int i=0;i<n;i++) wf[i][i]=0;
  for(int i=0;i<m;i++){
    ll a,b,c;cin >> a >> b >> c;
    wf[a-1][b-1]=c;
    wf[b-1][a-1]=c;
  }
  for(int k=0;k<n;k++){
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
        wf[i][j]=min(wf[i][j],wf[i][k]+wf[k][j]);
      }
    }
  }
  ll cnt=INF;
  vector<ll> v(r);for(int i=0;i<r;i++) v[i]=i;
  do{
    ll cnt_sub=0;
    for(int i=0;i<r-1;i++){
      cnt_sub+=wf[rx[v[i]]-1][rx[v[i+1]]-1];
    }
    cnt=min(cnt,cnt_sub);
  }while(next_permutation(v.begin(),v.end()));
  cout << cnt << endl;
}