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: Accepted

Solution code:
n,m,R=[int(x) for x in input().split()]
r=[int(x) -1 for x in input().split()]
d=[[float("inf") for _ in [0]*n] for _ in [0]*n]
for i in range(n):
    d[i][i]=0
for i in [0]*m:
    a,b,c=[int(x) for x in input().split()]
    d[a-1][b-1]=d[b-1][a-1]=c
from itertools import product,permutations
for k,i,j in product(range(n),range(n),range(n)):
    if d[i][j] >d[i][k]+d[k][j]:
        d[i][j]=d[i][k]+d[k][j]
def Long(args):
    ans=0
    for i in range(len(args)-1):
        ans+=d[args[i+1]][args[i]]
    return ans
print(min(Long(i) for i in permutations(r)))

Submission status: Accepted

Solution code:
import itertools

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

inf = 10**10
d = [[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())
    a -= 1
    b -= 1
    d[a][b] = min(d[a][b], c)
    d[b][a] = d[a][b]

def wf(N):
    for i in range(N):#経由地点
        for j in range(N):#開始地点
            for k in range(N):#終端
                d[j][k] = min(d[j][k], d[j][i]+d[i][k])

wf(n)

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

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/python

import itertools
import sys

def main(argv):
    line = sys.stdin.readline()
    while line:
        N, M, R = map(lambda x: int(x), line.split(" ", 3))
        r  = map(lambda x: int(x) - 1, sys.stdin.readline().split(" "))
        weights = [[0 for i in xrange(N)] for j in xrange(N)]
        for i in xrange(M):
            a, b, c = map(lambda x: int(x), sys.stdin.readline().split(" ", 3))
            weights[a - 1][b - 1] = c
            weights[b - 1][a - 1] = c

        for k in xrange(N):
            for i in xrange(N):
                for j in xrange(N):
                    if j > i:
                        if weights[i][k] > 0 and weights[k][j] > 0:
                            length = weights[i][k] + weights[k][j]
                            if weights[i][j] == 0 or weights[i][j] > length:
                                weights[i][j] = length
                                weights[j][i] = length

        min_length = -1
        for p in itertools.permutations(r):
            length = 0
            previous = p[0]
            for i in p[1:]:
                length += weights[previous][i]
                previous = i
            if min_length == -1:
                min_length = length
            elif min_length > length:
                min_length = length
        print min_length

        line = sys.stdin.readline()

if __name__ == "__main__":
    main(sys.argv)

Submission status: Accepted

Solution code:
# D
from itertools import permutations
from collections import deque

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



# read graph
G = dict()
for i in range(N):
    G[i+1] = dict()
for _ in range(M):
    A, B, C = map(int, input().split())
    G[A][B] = C
    G[B][A] = C

# minimum length
dist_list = [[0]*R for _ in range(R)]

for i in range(R):
    # BFS
    que = deque([r_list[i]])
    d_list_i = [M*100000+1]*(N+1)
    d_list_i[r_list[i]] = 0
    while len(que) > 0:
        s = que.popleft()
        for t in G[s].keys():
            if d_list_i[s] + G[s][t] < d_list_i[t]:
                d_list_i[t] = d_list_i[s] + G[s][t]
                que.append(t)
            else:
                pass
        
    for j in range(R):
        dist_list[i][j] = d_list_i[r_list[j]]
    
# power forever    
perms = list(permutations(range(R)))

res = (M*100000+1)*R
for p in perms:
    res_ = 0
    for i in range(R-1):
        res_ += dist_list[p[i]][p[i+1]]
    res = min(res, res_)
    
# print(G)
# print(dist_list)
print(res)

Submission status: Accepted

Solution code:
N, M, R = map(int, raw_input().split(' '))
rs = map(int, raw_input().split(' '))

edge = {}
for m in xrange(M):
  a, b, c = map(int, raw_input().split(' '))
  if a not in edge: edge[a] = {}
  if b not in edge: edge[b] = {}
  edge[a][b] = edge[b][a] = c

dist = {}
for r in rs:
  if r not in dist: dist[r] = {}
  dist[r][r] = 0
  fixed = {}
  while True:
    min_idx = None
    min_dist = float('inf')
    for i, d in dist[r].iteritems():
      if i not in fixed and d < min_dist:
        min_idx = i
        min_dist = d
    if min_idx is None: break
    fixed[min_idx] = True
    current = min_idx

    for i, d in edge[current].iteritems():
      if i in fixed: continue
      total = min_dist + d
      dist[r][i] = min(total, dist[r].get(i, float('inf')))

def process(now, rs, R, arrived):
  if len(arrived) == R:
    return 0
  min_dist = float('inf')
  for r in rs:
    if r in arrived: continue
    min_dist = min(min_dist, process(r, rs, R, arrived+[r]) + dist[now][r])
  return min_dist

print min(process(r, rs, R, [r]) for r in rs)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import heapq
import math

def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = list(range(n))
    cycles = list(range(n, n-r, -1))
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

tmp = input()
N, M, R = [int(a) for a in tmp.split()]
tmp = input()
mokutekis = [int(a) for a in tmp.split()]
Rs = []
for i in range(M):
    tmp = input()
    Rs.append([int(a) for a in tmp.split()])

roots = {}
for a, b, dist in Rs:
    roots[(a, b)], roots[(b, a)] = dist, dist

minimums = {}
for i in range(1, N+1):
    minimums[(i, i)] = 0
for m in mokutekis:
    tmp_mins = {}
    merged = [False for i in range(N+1)]
    merged[m] = True
    merged_num = 1
    now = m
    while merged_num < N:
        minimum = [None, None]
        for i in range(1, N+1):
            if merged[i]:
                continue
            if (now, i) not in roots:
                new_dist = 100000*200+1
            else:
                new_dist = minimums[(m, now)] + roots[(now, i)]
            if (m, i) not in tmp_mins or tmp_mins[(m, i)] > new_dist:
                tmp_mins[(m, i)] = new_dist
                tmp_mins[(i, m)] = new_dist
            if minimum[0] is None or minimum[1] > tmp_mins[(m, i)]:
                minimum = i, tmp_mins[(m, i)]
        minimums[(m, minimum[0])], minimums[(minimum[0], m)] = minimum[1], minimum[1]
        now = minimum[0]
        merged[now] = True
        merged_num += 1

d_min = None
for perm in permutations(range(len(mokutekis))):
    perm = list(perm)
    d = 0
    d_max = None
    for p1, p2 in zip(perm, perm[1:]+[perm[0]]):
        m1, m2 = mokutekis[p1], mokutekis[p2]
        now_d = minimums[(m1, m2)]
        if d_max is None or d_max < now_d:
            d_max = now_d
        d += now_d
    d -= now_d
    if d_min is None or d_min > d:
        d_min = d
print(d_min)

Submission status: Accepted

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


def solve(links, rs):
    r = len(rs)
    dists = [[-1] * r for _ in range(r)]
    r_dict = {ri: i for i, ri in enumerate(rs)}
    for ri in rs:
        dists_r = dists[r_dict[ri]]
        visited = set()
        queue = [(0, ri)]
        r_cnt = 0
        while queue:
            cost, node = heappop(queue)
            if node in visited:
                continue
            if node in r_dict:
                dists_r[r_dict[node]] = cost
                r_cnt += 1
                if r_cnt == r:
                    break
            visited.add(node)
            for c, a in links[node]:
                if a not in visited:
                    heappush(queue, (cost + c, a))
    ans = 1e9
    for p in permutations(range(r)):
        tmp = sum(dists[r1][r2] for r1, r2 in zip(p, p[1:]))
        ans = min(ans, tmp)
    return ans


n, m, r = map(int, input().split())
rs = [i - 1 for i in map(int, input().split())]
links = [set() for _ in range(n)]
for a, b, c in (map(int, input().split()) for _ in range(m)):
    a -= 1
    b -= 1
    links[a].add((c, b))
    links[b].add((c, a))

print(solve(links, rs))

Submission status: Accepted

Solution code:
N,M,NR = map(int,input().split())

R = list(map(lambda x: int(x) - 1 ,input().split()))

import scipy.sparse as ss
import numpy as np

G = ss.dok_matrix((N,N), dtype=np.uint32)

def it():
  for _ in range(M):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    yield ((a,b),c)
    yield ((b,a),c)

G.update(it())

D = ss.csgraph.floyd_warshall(G.tocsr(), directed=False)

def it2():
  from itertools import permutations
  for p in permutations(R):
    pp = iter(p)
    next(pp)
    yield sum(D[a,b] for a,b in zip(p,pp))

print(int(min(it2())))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n,m,R = LI()
    t = LI()
    e = collections.defaultdict(list)
    for _ in range(m):
        a,b,c = LI()
        e[a].append((b,c))
        e[b].append((a,c))

    # メソッドのみ版
    def search(s):
        d = collections.defaultdict(lambda: inf)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return d
    td = {}
    for i in t:
        td[i] = search(i)

    r = inf
    for ta in itertools.permutations(t):
        tr = 0
        for i in range(1,R):
            tr += td[ta[i-1]][ta[i]]
        if tr < r:
            r = tr

    return r

print(main())

Submission status: Runtime Error

Solution code:
n,m,r=map(int,input().split())
road=list(map(int,input().split()))
cost=[[float("inf")]*n for i in range(n)]
for i in range(m):
    cost[i][i]=0
    a,b,c=map(int,input().split())
    a,b=a-1,b-1
    cost[a][b]=c
    cost[b][a]=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])
import itertools
ans=float("inf")
for i in itertools.permutations(road):
    tmp=0
    for j in range(len(i)-1):
        tmp+=cost[i[j]-1][i[j+1]-1]
    if tmp<ans:
        ans=tmp
print(ans)

Submission status: Runtime Error

Solution code:
n,m,r=map(int,input().split())
road=list(map(int,input().split()))
cost=[[float("inf")]*n for i in range(n)]
for i in range(n):
    cost[i][i]=0
    a,b,c=map(int,input().split())
    a,b=a-1,b-1
    cost[a][b]=c
    cost[b][a]=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])
import itertools
ans=float("inf")
for i in itertools.permutations(road):
    tmp=0
    for j in range(len(i)-1):
        tmp+=cost[i[j]-1][i[j+1]-1]
    if tmp<ans:
        ans=tmp
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
INF = 10**12+7
N,M,R = map(int,input().split())
r = list(map(str,input().split()))
d = [[INF]*(N+1) for _ in range(N+1)]
for _ in range(M):
    A,B,C = map(int,input().split())
    d[A][B] = C
    d[B][A] = C
for i in range(1,N+1):
    d[i][i] = 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])
ans = INF
que = deque(r)
cnt = 0
while len(que) != 0:
    p = que.popleft()
    if len(p) == R:
        cnt += 1
        val = 0
        for i in range(1,R):
            val += d[int(p[i-1])][int(p[i])]
        ans = min(ans,val)
    else:
        for i in r:
            if not i in p:
                que.append(p+i)

for x in range(2,R+1):
  cnt /= x
if cnt != 1:
  cnt / 0

print(ans)

Submission status: Runtime Error

Solution code:
from itertools import permutations
n_node, n_edge, R = map(int,input().split())
r_ls = list(map(int,input().split()))
for i in range(R):
    r_ls[i] -= 1
ad_mat = [[float('inf')]*n_edge for _ in range(n_node)]
for i in range(n_node):
    ad_mat[i][i] = 0
for i in range(n_edge):
    a,b,c = map(int,input().split())
    ad_mat[a-1][b-1] = c
    ad_mat[b-1][a-1] = c

# ワーシャルフロイド
for start in range(n_node):
    for end in range(n_node):
        for stop in range(n_node):
            ad_mat[start][end] = min(ad_mat[start][end],ad_mat[start][stop]+ad_mat[stop][end])

ans = float('inf')
for path in permutations(r_ls):
    cost = 0
    for i in range(R-1):
        cost += ad_mat[path[i]][path[i+1]]
    ans = min(ans,cost)
print(ans)

Submission status: Runtime Error

Solution code:
asergae

Submission status: Runtime Error

Solution code:
from itertools import permutations
N,M,R = map(int,input().split())
RList = list(map(int,input().split()))
dp = [[[float("INF")]*(N+1) for _ in range(N+1)]for _ in range(N+1)]
for i in range(N+1):
    dp[i][i] = 0
for _ in range(M):
    a,b,c = map(int,input().split())
    dp[a][b] = c
    dp[b][a] = c

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

ans = float("INF")
RList = list(permutations(RList))
for Rs in RList:
    tmp = 0
    for i in range(1,R):
        a = Rs[i-1]
        b = Rs[i]
        tmp += dp[a][b]
    ans = min(ans,tmp)
print(ans)

Submission status: Runtime Error

Solution code:
import heapq
from itertools import permutations
n, m, r = map(int, input().split())
R = list(map(lambda x: int(x)-1, input().split()))
edges = [[]for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    edges[a].append((c, b-1))
    edges[b].append((c, a-1))


def dijkstra(init_v):
    next_v = [(0, init_v)]
    INF = 10**18
    dist = [INF]*n
    dist[init_v] = 0
    while next_v:
        d, v = heapq.heappop(next_v)
        if dist[v] < d:
            continue
        for d, v2 in edges[v]:
            if dist[v2] <= dist[v]+d:
                continue
            dist[v2] = dist[v]+d
            heapq.heappush(next_v, (dist[v2], v2))
    return dist


dists = []
for x in R:
    dist = dijkstra(x)
    dists.append(dist)

INF = 10**18
ans = INF
for subset in permutations(range(r)):
    d = 0
    for v, v2 in zip(subset, subset[1:]):
        d += dists[v][R[v2]]
    if d < ans:
        ans = d

print(ans)

Submission status: Runtime Error

Solution code:
from itertools import permutations
INFTY = 10**8
N,M,R = map(int,input().split())
r = list(map(int,input().split()))
G = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b,c = map(int,input().split())
    G[a].append((b,c))
    G[b].append((a,c))
dist = [[INFTY for _ in range(N+1)] for _ in range(N+1)]
for i in range(1,N+1):
    dist[i][i] = 0
for i in range(1,N+1):
    for j,d in G[i]:
        dist[i][j] = d
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])
dmin = 10**8
for i in range(R):
    for j in range(R):
        if i!=j:
            A = list(range(R))
            A.remove(i)
            A.remove(j)
            if len(A)>0:
                for x in permutations(A,R-2):
                    d = dist[r[i]][r[x[0]]]
                    for k in range(1,R-2):
                        d += dist[r[x[i]]][r[x[i-1]]]
                    d += dist[r[x[R-3]]][r[j]]
            else:
                d = dist[r[i]][r[j]]
            dmin = min(dmin,d)
print(dmin)

Submission status: Runtime Error

Solution code:
from itertools import permutations
INFTY = 10**8
N,M,R = map(int,input().split())
r = list(map(int,input().split()))
G = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b,c = map(int,input().split())
    G[a].append((b,c))
    G[b].append((a,c))
dist = [[INFTY for _ in range(N+1)] for _ in range(N+1)]
for i in range(1,N+1):
    dist[i][i] = 0
for i in range(1,N+1):
    for j,d in G[i]:
        dist[i][j] = d
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])
dmin = 10**8
for i in range(R):
    for j in range(R):
        if i!=j:
            A = list(range(R))
            A.remove(i)
            A.remove(j)
            for x in permutations(A,R-2):
                d = dist[r[i]][r[x[0]]]
                for k in range(1,R-2):
                    d += dist[r[x[i]]][r[x[i-1]]]
                d += dist[r[x[R-3]]][r[j]]
            dmin = min(dmin,d)
print(dmin)

Submission status: Runtime Error

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

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

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

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

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

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import java.util.*;
public class Main {
	
	static boolean[] used;
	static int[] r;
	static int[][] d;
	static int INF = Integer.MAX_VALUE/2, R;
	static long ans = INF;
	
	static void dfs(int now, long cost, int cnt) {
		if(cnt == R) {
			ans = Math.min(ans, cost);
			return;
		}
		for(int i : r)
			if(!used[i]) {
				used[i] = true;
				dfs(i, cost + d[now][i], cnt + 1);
				used[i] = false;
			}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		R = sc.nextInt();
		r = new int[R];
		used = new boolean[N];
		d = new int[N][N];
		Arrays.setAll(r, i -> sc.nextInt()-1);
		for(int i = 0; i < N; i++)
			for(int j = 0; j < N; j++)
				if(i != j)
					d[i][j] = INF;
		for(int i = 0; i < M; i++) {
			int A = sc.nextInt()-1;
			int B = sc.nextInt()-1;
			int C = sc.nextInt();
			d[A][B] = C;
			d[B][A] = C;
		}
		for(int k = 0; k < N; k++)
			for(int i = 0; i < N; i++)
				for(int j = 0; j < N; j++)
					d[i][j] = Math.min(d[i][j], d[i][k] + d[j][k]);
		for(int i : r) {
			used[i] = true;
			dfs(i, 0, 1);
			used[i] = false;
		}
		System.out.println(ans);
	}

}

Submission status: Runtime Error

Solution code:
from sys import stdin
import collections
import math

n,m,r   = [int(x) for x in stdin.readline().rstrip().split()]
r_arr = [int(x) for x in stdin.readline().rstrip().split()]

ways = [[int(c)  for c in stdin.readline().rstrip().split()] for _ in range(m)]

cost = [[float("inf") for j in range(n)] for i in range(n)]
for i in range(n):
    cost[i][i] = 0

for way in ways:
    cost[way[0]-1][way[1]-1] = way[2]
    cost[way[1]-1][way[0]-1] = way[2]


# ワーシャルフロイド
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])

# rの訪れ方を全パターン試して、最小の距離のものを答えにする。
tours = []
for perm in itertools.permutations(r_arr):
    d = 0
    for i in range(r-1):
        d += cost[perm[i]][perm[i+1]]
    tours.append(d)
print(min(tours))

Submission status: Runtime Error

Solution code:
from itertools import permutations
import heapq

def dijkstra(N, G, s):
    INF = 10**40
    d = [INF] * N
    d[s] = 0
    q = [(0, s)]
    while q:
        c, v = heapq.heappop(q)
        if d[v] < c:
            continue
        for t, co in G[v]:
            if d[v] + co < d[t]:
                d[t] = d[v] + co
                heapq.heappush(q, (d[t], t))
    return d


def main():
    N, M, _ = map(int, input().split())
    R = list(map(int, input().split()))
    R = [r - 1 for r in R]
    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a - 1].append((b - 1, c))
        G[b - 1].append((a - 1, c))
    RM = []
    for r in R:
        d = dijkstra(N, G, r)
        RM.append([d[rr] for rr in R])
    m = 10 ** 40
    for i in permutations(range(R)):
        t = i[0]
        c = 0
        for r in i[1:]:
            c += RM[t][r]
            t = r
        m = min(m, c)
    return m


print(main())

Submission status: Runtime Error

Solution code:
from itertools import permutations
import heapq

def dijkstra(N, G, s):
    INF = 10**40
    d = [INF] * N
    d[s] = 0
    q = [(0, s)]
    while q:
        c, v = heapq.heappop(q)
        if d[v] < c:
            continue
        for t, co in G[v]:
            if d[v] + co < d[t]:
                d[t] = d[v] + co
                heapq.heappush(q, (d[t], t))
    return d


def main():
    N, M, _ = map(int, input().split())
    R = list(map(int, input().split()))
    R = [r - 1 for r in R]
    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a - 1].append((b - 1, c))
        G[b - 1].append((a - 1, c))
    RM = []
    for r in R:
        d = dijkstra(N, G, r)
        RM.append([d[rr] for rr in R])
    m = 10 ** 40
    for i in permutations(R):
        t = i[0]
        c = 0
        for r in i[1:]:
            c += RM[t][r]
            t = r
        m = min(m, c)
    return m


print(main())

Submission status: Runtime Error

Solution code:
from itertools import permutations
import heapq

def dijkstra(N, G, s):
    INF = 10**40
    d = [INF] * N
    d[s] = 0
    q = [(0, s)]
    while q:
        c, v = heapq.heappop(q)
        if d[v] < c:
            continue
        for t, co in G[v]:
            if d[v] + co < d[t]:
                d[t] = d[v] + co
                heapq.heappush(q, (d[t], t))
    return d


def main():
    N, M, _ = map(int, input().split())
    R = list(map(int, input().split()))
    R = [r - 1 for r in R]
    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a - 1].append((b - 1, c))
        G[b - 1].append((a - 1, c))
    RM = []
    for r in R:
        d = dijkstra(N, G, r)
        RM.append([d[rr] for rr in R])
    m = 10 ** 40
    for i in permutations(R):
        t = R[0]
        c = 0
        for r in R[1:]:
            c += RM[t][r]
            t = r
        m = min(m, c)
    return m


print(main())

Submission status: Runtime Error

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

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

    return dist

res = 10*9
for k in al:
    temp = 0
    for l in al:
        temp += dfs(k)[l]
    res = min(res,temp)
print(res)

Submission status: Runtime Error

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


def main():
    N, M, R = list(map(int, input().split(' ')))
    towns = list(map(lambda t: int(t) - 1, input().split(' ')))
    A = np.zeros((N, N), dtype=int)
    for _ in range(M):
        a, b, c = list(map(int, input().split(' ')))
        A[a-1][b-1] = c
        A[b-1][a-1] = c
    fw = floyd_warshall(A)
    d = fw[towns, :][:, towns]
    min_d = 10**12
    for trip in itertools.permutations(range(R)):
        min_d = min([min_d, sum([d[trip[i]][trip[i+1]] for i in range(len(trip) - 1)])])
    print(int(min_d))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

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

for _ in range(M):
	A, B, C = MAP()
	dist_matrix[A-1][B-1] = C
	dist_matrix[B-1][A-1] = C

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

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

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

Warshall_Floyd(dist_matrix, N)

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


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

Submission status: Runtime Error

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

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

for _ in range(M):
	A, B, C = MAP()
	dist_matrix[A-1][B-1] = C
	dist_matrix[B-1][A-1] = C

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

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

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

Warshall_Floyd(dist_matrix, N)

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


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

Submission status: Runtime Error

Solution code:
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)

//
var (
	N int
	M int
	R int
	r []int
	d [][]int
)

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func fillInts(a []int, x int) {
	for i := 0; i < len(a); i++ {
		a[i] = x
	}
}

func warshallFloyd(n int, d [][]int) {
	for k := 0; k < n; k++ {
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				d[i][j] = min(d[i][j], d[i][k]+d[k][j])
			}
		}
	}
}

func swap(a []int, i int, j int) {
	x, y := a[i], a[j]
	a[i], a[j] = y, x
}

func permtationsImpl(a []int, i int, f func(a []int)) {
	if i == len(a)-1 {
		f(a)
		return
	}
	permtationsImpl(a, i+1, f)
	for j := i + 1; j < len(a); j++ {
		swap(a, i, j)
		permtationsImpl(a, i+1, f)
		swap(a, i, j)
	}
}

func permtations(a []int, f func(a []int)) {
	permtationsImpl(a, 0, f)
}

func main() {
	defer flush()

	N = readInt()
	M = readInt()
	R = readInt()
	r = make([]int, R)
	for i := 0; i < R; i++ {
		r[i] = readInt()
	}

	d = make([][]int, N+1)
	for i := 0; i < N+1; i++ {
		d[i] = make([]int, N+1)
		fillInts(d[i], math.MaxInt32)
		d[i][i] = 0
	}

	for i := 0; i < M; i++ {
		A := readInt()
		B := readInt()
		C := readInt()
		d[A][B] = C
		d[B][A] = C
	}
	warshallFloyd(N+1, d)

	result := math.MaxInt64
	permtations(r, func(a []int) {
		t := 0
		for i := 0; i < R-1; i++ {
			t += d[a[i]][a[i+1]]
		}
		result = min(result, t)
	})
	println(result)
}

const (
	ioBufferSize = 1 * 1024 * 1024 // 1 MB
)

var stdinScanner = func() *bufio.Scanner {
	result := bufio.NewScanner(os.Stdin)
	result.Buffer(make([]byte, ioBufferSize), ioBufferSize)
	result.Split(bufio.ScanWords)
	return result
}()

func readString() string {
	stdinScanner.Scan()
	return stdinScanner.Text()
}

func readInt() int {
	result, err := strconv.Atoi(readString())
	if err != nil {
		panic(err)
	}
	return result
}

var stdoutWriter = bufio.NewWriter(os.Stdout)

func flush() {
	stdoutWriter.Flush()
}

func printf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(stdoutWriter, f, args...)
}

func println(args ...interface{}) (int, error) {
	return fmt.Fprintln(stdoutWriter, args...)
}