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

n, m, r = map(int, input().split())
order = list(map(int, input().split()))
dist = [[-1 for _ in range(n + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
    dist[i][i] = 0

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

for k in range(1, n + 1):
    for i in range(1, n + 1):
        if dist[i][k] == -1:
            continue

        for j in range(1, n + 1):
            if dist[k][j] == -1:
                continue

            if dist[i][j] == -1:
                dist[i][j] = dist[i][k] + dist[k][j]
            else:
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

ans = float('inf')
for perm in itertools.permutations(order):
    cur = 0
    for i in range(1, r):
        cur += dist[perm[i - 1]][perm[i]]

    ans = min(ans, cur)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N,M,R = map(int,input().split())
towns = list(map(int,input().split()))
INF = 200000
cs =[[INF for j in range(N)] for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    a,b = a-1, b-1
    cs[a][b] = c
    cs[b][a] = c
for i in range(N):
    cs[i][i] = 0

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

ans = INF * N
for ptn in itertools.permutations(towns):
    tmp = 0
    for i in range(len(ptn)-1):
        tmp += cs[ptn[i]-1][ptn[i+1]-1]
    ans = min(ans, tmp)
print(ans)

Submission status: Time Limit Exceeded

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

cities = list(map(int, input().split()))
g = [[10**12 for i in range(n+1)] for j in range(n+1)]
for i in range(n+1):
    g[i][i] = 0
for i in range(m):
    a,b,c = map(int, input().split())
    g[a][b] = c
    g[b][a] = c
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            g[i][k] = min(g[i][k], g[i][j] + g[j][k])
ans = 10**12
for p in permutations(cities):
    path = 0
    for i in range(1, len(p)):
        path += g[p[i-1]][p[i]]
    ans = min(ans, path)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n, m, r = map(int, input().split())
order = list(map(int, input().split()))
dist = [[-1 for _ in range(n + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
    dist[i][i] = 0

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

    dist[b][a] = dist[a][b]

for k in range(1, n + 1):
    for i in range(1, n + 1):
        if dist[i][k] == -1:
            continue
        for j in range(1, n + 1):
            if dist[k][j] == -1:
                continue

            if dist[i][j] == -1:
                dist[i][j] = dist[i][k] + dist[k][j]
            else:
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

ans = float('inf')
for perm in itertools.permutations(order):
    cur = 0
    for i in range(1, r):
        if dist[perm[i - 1]][perm[i]] == -1:
            assert(1 == 0)

        cur += dist[perm[i - 1]][perm[i]]

    ans = min(ans, cur)

print(ans)

Submission status: Time Limit Exceeded

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

cities = list(map(int, input().split()))
g = [[10**12 for i in range(n+1)] for j in range(n+1)]
for i in range(n+1):
    g[i][i] = 0
for i in range(m):
    a,b,c = map(int, input().split())
    g[a][b] = c
    g[b][a] = c
for i in range(n+1):
    for j in range(n+1):
        for k in range(n+1):
            g[i][k] = min(g[i][k], g[i][j] + g[j][k])
ans = 10**12
for p in permutations(cities):
    path = 0
    for i in range(1, len(p)):
        path += g[p[i-1]][p[i]]
    ans = min(ans, path)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,m,r = map(int, input().split())
req = list(map(lambda x:int(x)-1, input().split()))
dist = [[float('inf') for j in range(n)] for i in range(n)]
for i in range(m):
    a,b,c = map(int, input().split())
    a -= 1
    b -= 1
    dist[a][b] = c
    dist[b][a] = c

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

min_dist = float('inf')
for p in itertools.permutations(req):
    total_dist = 0
    for i in range(r-1):
        total_dist += dist[p[i]][p[i+1]]
    min_dist = min(min_dist, total_dist)
print(min_dist)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

def main():
    n, m, r = map(int, input().strip().split())
    rs = list(map(int, input().strip().split()))
    dist = [[10 ** 10 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for _ in range(m):
        a, b, c = map(int, input().strip().split())
        dist[a-1][b-1] = c
        dist[b-1][a-1] = c
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    ans = 10 ** 10
    for trs in permutations(rs):
        tans = 0
        for i in range(len(trs) - 1):
            tans += dist[trs[i]-1][trs[i+1]-1]
        ans = min(ans, tans)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n,m,r=na()
rs = na()
for i in range(r):
    rs[i] -= 1

g = [[99999999999]*n for _ in range(n)]
for i in range(n):
    g[i][i] = 0
for i in range(m):
    a, b, c = na()
    a -= 1
    b -= 1
    g[a][b] = g[b][a] = c

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

from itertools import *

ans = 9999999999999999999
for ord in permutations(rs):
    w = 0
    for i in range(1, r):
        w += g[ord[i-1]][ord[i]]
    ans = min(ans, w)
print(ans)

Submission status: Memory Limit Exceeded

Solution code:
N,M,r = map(int,input().split())
R = list(map(int,input().split()))
#dp[i][j][k] -> 町iまで経由地点として使える。j,kの最短移動距離
dp = [[[float("INF")]*(N+1) for _ in range(N+1)]for _ in range(N+1)]
for _ in range(M):
    a,b,c = map(int,input().split())
    dp[0][a][b] = c
    dp[0][b][a] = c

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

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

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

Submission status: Memory Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200000)

N,M,R = map(int,input().split())
RList = list(map(int,input().split()))
edges = [[]for _ in range(N+1)]
for _ in range(M):
    a,b,c = map(int,input().split())
    edges[a].append((b,c))
    edges[b].append((a,c))

dp = [[[float("INF")]*(N+1) for _ in range(N+1)]for o in range(N+1)]
for j in range(1,N+1):
    dp[0][j][j] = 0
    for nx,c in edges[j]:
        dp[0][j][nx] = c

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

def dfs(n,path,cost):
    tmp = path[::1]
    tmp.append(n)
    if len(tmp) == R:
        return cost
    else:
        ret = float("INF")
        for nx in RList:
            if nx not in tmp:
                ret = min(ret,dfs(nx,tmp,cost+dp[-1][n][nx]))
        return ret

ans = float("INF")
for r in RList:
    ans = min(ans,dfs(r,[],0))

print(ans)

Submission status: Accepted

Solution code:
class WarshallFloyd:
    #O(V^3)で任意２頂点の最短距離
    def __init__(self,n,_first_index=0):
        self.v = n
        self._first_idx=_first_index
        self.d = [[float("INF")]*(n) for _ in range(n)]
        for i in range(n):
            self.d[i][i] = 0

    def path(self,x,y,c):
        if x == y:
            return False
        f=self._first_idx
        self.d[x-f][y-f] = c
        self.d[y-f][x-f] = c
        return True

    def build(self):
        for k in range(self.v):
            for i in range(self.v):
                for j in range(self.v):
                    self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])
        return self.d
n,m,r=map(int,input().split())
rs=[x-1 for x in map(int,input().split())]
w=WarshallFloyd(n,1)
for i in range(m):w.path(*map(int,input().split()))
v=w.build()
from itertools import permutations as pe
print(min(sum(v[f][t]for f,t in zip(i,i[1:]))for i in pe(rs)))

Submission status: Accepted

Solution code:
from itertools import permutations

def main():
    N: int
    M: int
    R: int
    A: int
    B: int
    C: int
    ans: int    
    INF: int
    INF = 10 ** 10
    N, M, R = map(int, input().split())
    r: list = list(map(lambda x: x - 1, map(int, input().split())))
    dist :list = [[float('inf')] * N for _ in range(N)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        A -= 1
        B -= 1
        dist[A][B] = C
        dist[B][A] = 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][j], dist[i][k] + dist[k][j])
    ans = INF
    for item in permutations(r):
        L: int = len(item)
        d: int = 0
        for i in range(1,L):
            pre: int = item[i-1]
            now: int = item[i]
            d += dist[pre][now]
        ans = min(ans, d)
    print(ans)  

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from copy import deepcopy
from itertools import permutations


def warshallfloyd(N):  # ワーシャルフロイド法:全頂点対最短経路 O(n**3)
    DIST = deepcopy(mat)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                DIST[i][j] = min(DIST[i][j], DIST[i][k] + DIST[k][j])
    return DIST


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

mat = [[10 ** 10] * n for _ in range(n)]
for i in range(n):
    mat[i][i] = 0
for a, b, c in abc:
    mat[a - 1][b - 1] = c
    mat[b - 1][a - 1] = c

ans = float('inf')
dist = warshallfloyd(n)
for route in permutations(town, r):
    bfo, tmp = route[0], 0
    for i in route[1:]:
        tmp += dist[bfo - 1][i - 1]
        bfo = i
    ans = min(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy
from itertools import permutations


def warshallfloyd(N, LIST):  # ワーシャルフロイド法:全頂点対最短経路 O(n**3)
    DIST = deepcopy(LIST)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                DIST[i][j] = min(DIST[i][j], DIST[i][k] + DIST[k][j])
    return DIST


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

mat = [[10 ** 10] * n for _ in range(n)]
for i in range(n):
    mat[i][i] = 0
for a, b, c in abc:
    mat[a - 1][b - 1] = c
    mat[b - 1][a - 1] = c

ans = float('inf')
dist = warshallfloyd(n, mat)
for route in permutations(town, r):
    bfo, tmp = route[0], 0
    for i in route[1:]:
        tmp += dist[bfo - 1][i - 1]
        bfo = i
    ans = min(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy
from itertools import permutations


def warshallfloyd(N, LIST):  # ワーシャルフロイド法:全頂点対最短経路 O(n**3)
    DIST = deepcopy(LIST)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                DIST[i][j] = min(DIST[i][j], DIST[i][k] + DIST[k][j])
    return DIST


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

mat = [[10 ** 10] * n for _ in range(n)]
for i in range(n):
    mat[i][i] = 0
for a, b, c in abc:
    mat[a - 1][b - 1] = c
    mat[b - 1][a - 1] = c

ans = float('inf')
dist = warshallfloyd(n, mat)
for route in permutations(town, r):
    tmp = 0
    for i, j in zip(route[:-1], route[1:]):
        tmp += dist[i - 1][j - 1]
    ans = min(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n,m,r=map(int,input().split())
rlst=list(map(int,input().split()))
abc=[list(map(int,input().split())) for i in range(m)]

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

n,w = n,m #n:頂点数　w:辺の数

d = [[float("inf") for i in range(n)] for i in range(n)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(w):
    x,y,z = abc[i]
    x-=1
    y-=1
    d[x][y] = z
    d[y][x] = z
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
lst=warshall_floyd(d)
# print(lst)
pro=list(permutations(range(r)))
# print(pro)
ans=float('inf')
for i in pro:
    tmp=0
    for j in range(r-1):
        now=i[j]
        nxt=i[j+1]
        tmp+=lst[rlst[now]-1][rlst[nxt]-1]
    ans=min(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
import itertools
N, M, R = map(int, input().split())
r=[int(x) for x in input().split()]
r=[i-1 for i in r]
d=[[float("inf")]*N for _ in range(N)]
for i in range(N):
	d[i][i]=0
for _ in range(M):
	a, b, c = map(int, input().split())
	a-=1
	b-=1
	d[a][b]=min(d[a][b], c)
	d[b][a]=min(d[b][a], c)

#d[i][j]は2頂点間i, j間の移動コストを格納, Vは頂点数
def warshall_floyd(d, V): 
	for k in range(V):
		for i in range(V):
			for j in range(V):
				d[i][j] = min(d[i][j], d[i][k] + d[k][j])

	return d #d[i][j]に頂点i, j間の最短距離を格納

d=warshall_floyd(d, N)
ans=float("inf")
for l in list(itertools.permutations(r)):
	temp=sum([d[l[i]][l[i+1]] for i in range(R-1)])
	ans=min(ans, temp)
print(ans)

Submission status: Accepted

Solution code:
import heapq

N, M, R = map(int, input().split())
D = [int(a) - 1 for a in input().split()]
D.sort()
Dtod = {}
dtoD = {}
Dest = set()
for i, d in enumerate(D):
    Dtod[d] = i
    dtoD[i] = d
    Dest.add(d)
Map = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    Map[a].append((b, c))
    Map[b].append((a, c))

Roots = [[float('inf')] * R for _ in range(R)]
for i, d in enumerate(D):
    Roots[i][i] = 0
    Q = [d]
    Root = [float('inf')] * N
    Root[d] = 0
    while Q and (float('inf') in Roots[i]):
        q = heapq.heappop(Q)
        fatigue, now = divmod(q, 10**3)
        if now in Dest:
            Roots[i][Dtod[now]] = min(fatigue, Roots[i][Dtod[now]])
            Roots[Dtod[now]][i] = min(fatigue, Roots[Dtod[now]][i])
        for nex, cost in Map[now]:
            if Root[nex] > cost + fatigue:
                Root[nex] = cost + fatigue
                heapq.heappush(Q, (cost + fatigue) * 10**3 + nex)

DP = [[float('inf')] * (1 << R) for _ in range(R)]
bit_count = [0]
for _ in range(R):
    bit_count += [x+1 for x in bit_count]

for i in range(1 << R):
    cnt = bit_count[i]
    for j in range(R):
        if (i >> j) & 1 ==1:
            if cnt == 1:
                DP[j][i] = 0
            for k in range(R):
                if j == k:
                    continue
                DP[k][i|(1 << k)] = min(DP[k][i|(1 << k)], DP[j][i] + Roots[j][k])
ans = float('inf')
for i in range(R):
    ans = min(ans, DP[i][-1])
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
from operator import itemgetter
#from heapq import heappush, heappop
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
#from scipy.sparse import csr_matrix

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

stdin = sys.stdin

ni = lambda: int(ns())
nf = lambda: float(ns())
na = lambda: list(map(int, stdin.readline().split()))
nb = lambda: list(map(float, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

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

g = np.array(g)
d = shortest_path(g)

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

Submission status: Accepted

Solution code:
def warshall_floyd(d):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
N, M, R = map(int,input().split())
r = list(map(int,input().split()))
d = [[float("inf")]*N for i in range(N)]
edge = [[] for i in range(N)]
for i in range(M):
    x, y, z = map(int,input().split())
    d[x-1][y-1] = z
    d[y-1][x-1] = z
for i in range(N):
    d[i][i] = 0

warshall_floyd(d)
ans = float('inf')

import itertools
for i in itertools.permutations(r):
    tmp = 0
    for k in range(1,R):
        tmp += d[i[k-1]-1][i[k]-1]
    ans = min(ans,tmp)
print(ans)

Submission status: Accepted

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

N,M,R = map(int,readline().split())
r = list(map(int,readline().split()))
INF = 10 ** 10

G = [[INF] * N for i in range(N)]
for i in range(M):
  a,b,c = map(int,readline().split())
  G[a - 1][b - 1] = c
  G[b - 1][a - 1] = c
  
for i in range(N):
  G[i][i] = 0
  
for k in range(N):
  for i in range(N):
    for j in range(N):
      G[i][j] = min(G[i][j], G[i][k] + G[k][j])
      
import itertools
ans = INF
for perm in itertools.permutations(range(R)):
  dist = 0
  for i in range(1, len(perm)):
    dist += G[r[perm[i - 1]] - 1][r[perm[i]] - 1]
  if ans > dist:
    ans = dist
    
print(ans)

Submission status: Accepted

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

with open(0) as f:
    N, M, R = map(int, f.readline().split())
    r = list(map(int, f.readline().split()))
    path = [tuple(map(int, line.split())) for line in f.readlines()]

graph = np.full((N,N), np.inf)
for a, b, c in path:
    graph[a-1, b-1] = c
    graph[b-1, a-1] = c

graph = dijkstra(graph, directed=False)
ans = np.inf
permutation = list(permutations(r))
for p in permutation:
    way = 0
    for x,y in zip(p[:len(r)], p[1:]):
        way += graph[x-1, y-1]
    ans = min(ans, way)
print(int(ans))

Submission status: Accepted

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

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

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

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

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

N, M, R = getNM()

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

def warshall_floyd(dist):
    for k in range(N):
        # i:start j:goal k:中間地点でループ回す
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    #return dist

warshall_floyd(d)

ans = float('inf')
for case in permutations(list_R):
    x1 = case[0]
    opt = 0
    for j in range(1, R):
        x2 = case[j]
        opt += d[x1][x2]
        x1 = x2
    ans = min(ans, opt)
print(ans)

Submission status: Accepted

Solution code:
import math
from typing import List, Counter, Tuple
from collections import Counter
from itertools import permutations


def read_int() -> int:
    return int(input().strip())


def read_ints() -> List[int]:
    return list(map(int, input().strip().split(' ')))


def solve() -> int:
    N, M, R = read_ints()
    r = [a-1 for a in read_ints()]
    inf = 10**10
    D = [
        [inf for _ in range(N)] for _ in range(N)
    ]
    for i in range(N):
        D[i][i] = 0
    for _ in range(M):
        a, b, c = read_ints()
        D[a-1][b-1] = D[b-1][a-1] = c
    for k in range(N):
        for i in range(N):
            for j in range(N):
                D[i][j] = min(D[i][j], D[i][k]+D[k][j])
    min_cost: int = inf
    for path in permutations(r):
        cost: int = 0
        for i in range(1, len(path)):
            cost += D[path[i-1]][path[i]]
        min_cost = min(min_cost, cost)
    return min_cost


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
from itertools import permutations
N,M,R = map(int,input().split())
r = list(map(int,input().split()))
for i in range(R):
  r[i] -= 1
g = [[10 ** 8] * N for i in range(N)]
for i in range(M):
  A,B,C = map(int,input().split())
  A -= 1 
  B -= 1
  g[A][B] = C
  g[B][A] = C
def warchall_floyd(n):
  for i in range(n):
    #経由する頂点
    for j in range(n):
      #始点
      for k in range(n):
        #終点
        g[j][k] = min(g[j][k],g[j][i]+g[i][k])
        
warchall_floyd(N)
ans = float('inf')
for i in permutations(r):
  now = 0
  for j in range(R-1):
    now += g[i[j]][i[j+1]]
  if now < ans:
    ans = now
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations as p


INF = float('inf')
N, M, R = map(int, input().split())
r = list(map(lambda x:int(x) - 1, input().split()))

# 隣接行列
dist = [[INF] * N for _ in range(N)]

# 初期化、対角成分は0、それ以外はINF
for i in range(N):
    dist[i][i] = 0

# 繋がっている街への距離を記録
for _ in range(M):
    A, B, C = map(int, input().split())
    A, B = A - 1, B - 1
    dist[A][B] = dist[B][A] = C


# Warshall-Floyd
def main():
    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])

    ans = INF
    # rの全ての並び替えに対して、スタートからゴールまでのdistを足し合わせて最小を求める
    for combi in p(r, R):
        temp = 0
        for i in range(R - 1):
            cost = dist[combi[i]][combi[i + 1]]
            if cost < INF:
                temp += cost
            # 繋がってない場合はbreak
            else:
                break
        else:
            ans = min(ans, temp)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import permutations as p


INF = float('inf')
N, M, R = map(int, input().split())
r = list(map(lambda x:int(x) - 1, input().split()))
dist = [[INF] * N for _ in range(N)]

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

for _ in range(M):
    A, B, C = map(int, input().split())
    A, B = A - 1, B - 1
    dist[A][B] = dist[B][A] = C


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

    ans = INF
    for combi in p(r, R):
        temp = 0
        for i in range(R - 1):
            cost = dist[combi[i]][combi[i + 1]]
            if cost < INF:
                temp += cost
            else:
                break
        else:
            ans = min(ans, temp)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

##############################
n,m,r = map(int,input().split()) #n:頂点数  w:辺の数
arr=list(map(int,input().split()))

d = [[float("inf")]*n for i in range(n)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(m):
    x,y,z = map(int,input().split())
    x-=1
    y-=1
    d[x][y] = z
    d[y][x] = z
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０

table=warshall_floyd(d)

ans=float('inf')
for lst in itertools.permutations(arr,r):
  cnt=0
  for i in range(r-1):
    cnt+=table[lst[i]-1][lst[i+1]-1]

  ans=min(ans,cnt)


print(ans)

Submission status: Accepted

Solution code:
import itertools

n,m,r = map(int,input().split())
R = list(map(int,input().split()))
V = [[] for i in range(n+1)]
for i in range(m):
    a,b,c = map(int,input().split())
    V[a].append([b,c])
    V[b].append([a,c])
    
cost = [[float("Inf") for j in range(n+1)] for i in range(n+1)]
for i in range(1,n+1):
    for j in range(1,n+1):
        for v,d in V[i]:
            if v == j:
                cost[i][j] = d

for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            if cost[i][j] > cost[i][k] + cost[k][j]:
                cost[i][j] = cost[i][k] + cost[k][j]

L = list(itertools.permutations(R, r))
ans = float("Inf")

for x in L:
    p = 0
    for i in range(len(x)-1):
        p += cost[x[i]][x[i+1]]
        
    ans = min(ans, p)
print(ans)

Submission status: Accepted

Solution code:
def main():
    from sys import stdin
    input = stdin.readline

    n, m, r = map(int, input().split())
    l = [int(i) - 1 for i in input().split()]
    d = [[10**8] * n for _ in range(n)]
    for _ in range(m):
        i, j, k = map(int, input().split())
        d[i-1][j-1] = k
        d[j-1][i-1] = k

    # Warshall-Floyd algorithm
    for k in range(n):
        for i in range(n-1):
            for j in range(i+1, n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
                    d[j][i] = d[i][j]

    # full search
    # 8! = 40320
    from itertools import permutations

    answer = float('inf')
    for i in permutations(l):
        ans = 0
        for j in range(r-1):
            ans += d[i[j]][i[j+1]]
        if ans < answer:
            answer = ans

    print(answer)

main()

Submission status: Accepted

Solution code:
def main():
    from sys import stdin
    input = stdin.readline

    n, m, r = map(int, input().split())
    l = [int(i) - 1 for i in input().split()]
    d = [[10**8] * n for _ in range(n)]
    for _ in range(m):
        i, j, k = map(int, input().split())
        d[i-1][j-1] = k
        d[j-1][i-1] = k

    # Warshall-Floyd algorithm
    for k in range(n):
        for i in range(n-1):
            for j in range(i+1, n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
                    d[j][i] = d[i][j]

    # full search
    # 8! = 40320
    from itertools import permutations

    answer = 10**8
    for i in permutations(l):
        ans = 0
        for j in range(r-1):
            ans += d[i[j]][i[j+1]]
        if ans < answer:
            answer = ans

    print(answer)

main()

Submission status: Accepted

Solution code:
def main():
    from sys import stdin
    input = stdin.readline

    n, m, r = map(int, input().split())
    l = list(map(int, input().split()))
    for i in range(r):
        l[i] -= 1
    d = [[10**8] * n for _ in range(n)]
    for _ in range(m):
        i, j, k = map(int, input().split())
        d[i-1][j-1] = k
        d[j-1][i-1] = k

    # Warshall-Floyd algorithm
    for k in range(n):
        for i in range(n-1):
            for j in range(i+1, n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
                    d[j][i] = d[i][j]

    # full search
    # 8! = 40320
    from itertools import permutations

    answer = 10**8
    for i in permutations(l):
        ans = 0
        for j in range(r-1):
            ans += d[i[j]][i[j+1]]
        if ans < answer:
            answer = ans

    print(answer)

main()

Submission status: Accepted

Solution code:
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n,m,r=map(int,input().split())
r=list(map(int,input().split()))
abc=[list(map(int,input().split())) for i in range(m)]

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

n,w = n,m

d = [[float("inf") for i in range(n)] for i in range(n)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(w):
    x,y,z = abc[i]
    x,y=x-1,y-1
    d[x][y] = z
    d[y][x] = z
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
d=warshall_floyd(d)

# print(range(r))
lst=list(permutations(r))
# print(lst)
ans=float('inf')
for i in lst:
    tmp=0
    for j in range(len(i)-1):
        tmp+=d[i[j]-1][i[j+1]-1]
    ans=min(ans,tmp)
print(ans)