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:
from itertools import permutations

def warshall_floyd(A, INF=10**20):
    d = [[INF for i in range(len(A))] for j in range(len(A))]
    for i in range(len(A)):
        d[i][i] = 0
        for j in A[i].keys():
          d[i][j] = A[i][j]

    for k in range(len(A)):
        for i in range(len(A)):
            for j in range(len(A)):
                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()))
r2 = []
for i in range(len(r)):
  r2.append(r[i]-1)
r = r2
G=[{} for _ in range(N)]
for i in range(M):
  a,b,c=map(int,input().split())
  a -= 1
  b -= 1
  G[a][b] = G[b][a] = c

d = warshall_floyd(G)

if R==2:
  print(d[r[0]][r[1]])
  exit()
  
ans = 10**20
for p in 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: Accepted

Solution code:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
import itertools
I = [int(_) for _ in open(0).read().split()]
N, M, R = I[:3]
r = np.array(I[3:3 + R])
ABC = I[3 + R:]
F = floyd_warshall(csr_matrix((ABC[2::3], (ABC[::3], ABC[1::3])), (N + 1, N + 1)), 0).astype(np.int64)
ans = float('inf')
for root in itertools.permutations(r, R):
    ans = min(ans, sum(F[i,j] for i, j in zip(root, root[1:])))
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

def warshall_floyd():
    '''
    すべての頂点間の最短距離を求める (重み付き有向グラフ)
    '''
    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())
city = list(map(int, input().split()))

dist = [[float('inf')] * n for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    dist[a-1][b-1] = c
    dist[b-1][a-1] = c
for i in range(n):
    dist[i][i] = 0

warshall_floyd()

res = float('inf')
for l in permutations(range(r), r):
    d = 0
    for i in range(r-1):
        d += dist[city[l[i]]-1][city[l[i+1]]-1]
    res = min(res, d)

print(res)

Submission status: Accepted

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())
    a -= 1
    b -= 1
    edges[a].append((c, b))
    edges[b].append((c, a))


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

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
    
adj = [[INF]*N for _ in range(N)]
perm_list = []

def make_permutation(l,R):
    if R == 0:
        perm_list.append(l)
    else:
        for a in r:
            if a not in l:
                make_permutation(l+[a],R-1)

def main():
    for _ in range(M):
        A, B, C = map(int, input().split())
        adj[A-1][B-1] = C
        adj[B-1][A-1] = C
    
    # 方針: Warshall-Floydで各頂点間の最短距離を求めてからrの順列全探索
    for k in range(N):
        for i in range(N):
            for j in range(N):
                adj[i][j] = min(adj[i][j], adj[i][k]+adj[k][j])

    make_permutation([],R)
    ans = INF
    for ps in perm_list:
        tmp = 0
        for i in range(R-1):
            tmp += adj[ps[i]-1][ps[i+1]-1]
        ans = min(ans,tmp)
    print(ans)
    # print(perm_list)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m,r = map(int,input().split())
v = list(map(int,input().split()))
for i in range(r):
    v[i] -= 1
INF = float("inf")
g = [[INF]*n for _ 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
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])


dp = [[INF]*r for i in range(2**r)]
for i in range(r):
    dp[2**i][i] = 0


for i in range(1,2**r):
    for j in range(r):
        if dp[i][j] == INF:
            continue
        for k in range(r):
            nxt = i | 2**k
            dp[nxt][k] = min(dp[nxt][k],dp[i][j]+g[v[j]][v[k]])

print(min(dp[-1]))

Submission status: Accepted

Solution code:
from itertools import permutations as per
n,m,r = map(int,input().split())
v = list(map(int,input().split()))
for i in range(r):
    v[i] -= 1
INF = float("inf")
g = [[INF]*n for _ 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
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])

ans = INF
for l in per(range(r)):
    t = 0
    for i in range(r-1):
        t += g[v[l[i]]][v[l[i+1]]]
    ans = min(ans,t)
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import permutations
def input(): return sys.stdin.readline().strip()


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

    # 全点対間最短距離を予め求めておく（ワーシャルフロイド）
    path = [[10**18] * N for _ in range(N)]
    for i in range(N): path[i][i] = 0
    for _ in range(M):
        a, b, c = map(int, input().split())
        path[a - 1][b - 1] = min(c, path[a - 1][b - 1])
        path[b - 1][a - 1] = min(c, path[b - 1][a - 1])
    for k in range(N):
        for i in range(N):
            for j in range(N):
                path[i][j] = min(path[i][j], path[i][k] + path[k][j])

    # あとはRの全順列に対して一つずつ評価すれば良い
    ans = 10**18
    for r in list(permutations(R)):
        d = 0
        for i in range(num - 1):
            d += path[r[i] - 1][r[i + 1] - 1]
        ans = min(ans, d)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from heapq import heapify,heappush,heappop
readline=sys.stdin.readline

def main():
    N,M,R=map(int,readline().split())
    r=list(map(int,readline().split()))
    ew=[tuple(map(int,readline().split())) for _ in range(M)]
    edges=defaultdict(list)
    wt=defaultdict(int)
    for e in ew:
        edges[e[0]].append(e[1])
        edges[e[1]].append(e[0])
        wt[(e[0],e[1])]=e[2]
        wt[(e[1],e[0])]=e[2]
    inf=float('inf')
    def dijkstra(v):
        dist=[inf]*(N+1)
        dist[v]=0
        vw=[(0,v)]
        heapify(vw)
        while vw:
            cvw=heappop(vw)
            if cvw[0]>dist[cvw[1]]:
                continue
            for w in edges[cvw[1]]:
                cand=cvw[0]+wt[(cvw[1],w)]
                if dist[w]>cand:
                    dist[w]=cand
                    heappush(vw,(cand,w))
        return dist
    distdict=dict((v,dijkstra(v)) for v in r)
    mindist=inf
    def permlist(lst):
        tmp=[]
        if not lst:
            return [[]]
        for i,x in enumerate(lst):
            lstx=lst[:i]+lst[i+1:]
            ret=permlist(lstx)
            for e in ret:
                e.append(x)
            tmp.extend(ret)
        return tmp
    #print(distdict,permlist(r))
    pathlist=[sum([distdict[v][w] for v,w in zip(lst,lst[1:])]) for lst in permlist(r)]
    print(min(pathlist))

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import permutations

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, R = map(int, readline().split())
    city = [int(s) - 1 for s in readline().split()]
    ABC = map(int, read().split())

    G = [[INF] * N for _ in range(N)]
    for a, b, c in zip(*[iter(ABC)] * 3):
        G[a - 1][b - 1] = 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):
                if G[i][j] > G[i][k] + G[k][j]:
                    G[i][j] = G[i][k] + G[k][j]

    ans = INF
    for plan in permutations(city):
        res = 0
        for i in range(R - 1):
            res += G[plan[i]][plan[i + 1]]
        if ans > res:
            ans = res

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import permutations as perm
n, m, r = map(int, input().split())
rs = list(map(int, input().split()))
grid = [[float('inf')]*n for _ in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    grid[a-1][b-1] = c
    grid[b-1][a-1] = c
for i in range(n):
    for j in range(n):
        if i == j:
            grid[i][j] = 0
for k in range(n):
    for i in range(n):
        for j in range(n):
            grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j])

perms = rs
res = float('inf')
for p in perm(perms):
    tmp = 0
    for i in range(1,r):
        tmp += grid[p[i]-1][p[i-1]-1]
    res = min(res,tmp)
print(res)

Submission status: Accepted

Solution code:
def abc073_d():
    from scipy.sparse import lil_matrix
    from scipy.sparse.csgraph import floyd_warshall
    from itertools import permutations

    n, m, r = map(int, input().split())
    R = list(map(lambda x: int(x)-1, input().split()))
    graph = lil_matrix((n, n), dtype=int)
    for _ in range(m):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        graph[a, b] = c
        graph[b, a] = c

    dist = floyd_warshall(csgraph=graph)
    #print(dist)

    ans = 10**18
    for route in permutations(R, r):
        tmp = 0
        for i in range(r-1):
            s = route[i]
            t = route[i+1]
            tmp += dist[s][t]
            if tmp > ans: break
        ans = min(ans, tmp)
        #print(route, tmp)

    print(int(ans))

if __name__ == '__main__':
    abc073_d()

Submission status: Accepted

Solution code:
import sys
import heapq
import itertools

INF = 10**18

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def dijkstra(N, s0, edge):

    d = [INF] * N
    pre_v = [-1] * N
    used = [False] * N
    edgelist = [(0, s0, -1)]
    heapq.heapify(edgelist)

    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if used[minedge[1]]:
            continue

        v = minedge[1]
        d[v] = minedge[0]
        used[v] = True
        pre_v[v] = minedge[2]

        for e in edge[v]:
            if d[e[1]] <= (e[0] + d[v]) or used[e[1]]:
                continue
            heapq.heappush(edgelist, (e[0] + d[v], e[1], v))
    return d, pre_v


def main():

    N, M, R = in_nn()
    r = in_nl()
    r = [t - 1 for t in r]
    edge = [[] for _ in range(N)]

    for i in range(M):
        a, b, c = in_nn()
        a, b = a - 1, b - 1
        edge[a].append((c, b))
        edge[b].append((c, a))

    dis = [[-1] * N for _ in range(N)]
    for i in range(R):
        s = r[i]
        d, pre_v = dijkstra(N, s, edge)

        for j in range(R):
            e = r[j]
            dis[s][e] = d[e]

        for j in range(R):
            if i == j:
                continue

            e = r[j]
            tr = set(r) - {e} - {s}
            while e != -1:
                t = pre_v[e]
                if t in tr:
                    dis[s][e] = -1
                    break
                else:
                    e = t

    perm = itertools.permutations(r, R)

    ans = INF
    for per in perm:

        td = 0
        for i in range(R - 1):
            s, e = per[i], per[i + 1]
            if dis[s][e] == -1:
                break
            else:
                td += dis[s][e]
        else:
            ans = min(ans, td)

    # print(dis)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

N,M,R = map(int, input().split())
rs = np.array(list(map(int, input().split()))) -1

nodes = np.full((N,N), np.inf) 
for i in range(M):
  a,b,c = map(int, input().split())
  nodes[a-1,b-1] = nodes[b-1,a-1] = c
min_ds = shortest_path(nodes)
res = float('inf')
for p in itertools.permutations(rs):
  prev = p[0]
  tmp = 0
  for next in p[1:]:
    tmp += min_ds[prev,next]
    prev = next
  res = min(res, tmp)

print(int(res))

Submission status: Accepted

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 x in permutations(range(R),R):
    d = 0
    for k in range(1,R):
        d += dist[r[x[k]]][r[x[k-1]]]
    dmin = min(dmin,d)
print(dmin)

Submission status: Accepted

Solution code:
n, m, r = map(int, input().split())
R = list(map(int, input().split()))
R = [x-1 for x in R]

def warshal_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

d = [[float('inf') for i in range(n)] for j 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

d = warshal_floyd(d)
import itertools
ans = float('inf')
for p in itertools.permutations(R):
    temp = 0
    for i in range(r-1):
        temp += d[p[i]][p[i+1]]
    ans = min(temp, ans)
print(ans)

Submission status: Accepted

Solution code:
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
d = [[float('inf')]*N for _ in range(N)]
for i in range(M): #ひとまず枝があるペアは枝の長さをセット
  a,b,t = map(int, input().split())
  d[a-1][b-1] = t
  d[b-1][a-1] = t

for i in range(N):
  d[i][i] = 0 #自身への最短経路は0
#三重ループ
for k in range(N):
  for i in range(N):
    for j in range(N):
      d[i][j] = min(d[i][j], d[i][k]+d[k][j])

from itertools import groupby, accumulate, product, permutations, combinations

ans = float('inf')
for p in permutations(r,R):
  cnt = 0
  for i in range(1,R):
    cnt += d[p[i-1]-1][p[i]-1]
  ans = min(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools

def warshall_floyd(d, n):
    #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, sys.stdin.readline().split())
r = list(map(int, sys.stdin.readline().split()))

# 全点間の距離
d = [[float("inf")]*N for i in range(N)] 
for _ in range(M):
	a, b, c = map(int, sys.stdin.readline().split())
	d[a-1][b-1] = c
	d[b-1][a-1] = c

d = warshall_floyd(d, N)
# print(d)

# 探索順の全組み合わせを試して、最小を見つける
ans = float("inf")
for comb in itertools.permutations(r):
	dist = 0
	for i in range(R-1):
		dist += d[comb[i]-1][comb[i+1]-1]
	ans = min(ans, dist)

print(ans)

Submission status: Accepted

Solution code:
import itertools
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson

N,M,R = map(int, input().split())
r_list = np.array(list(map(int, input().split()))) -1 

nodes = np.full((N,N), np.inf) 
for i in range(M):
    a,b,c = map(int, input().split())
    nodes[a-1,b-1] = nodes[b-1,a-1] = c
min_ds = shortest_path(nodes)
res = 10**9
for cmb in itertools.permutations(r_list):
    prev = cmb[0]
    tmpres = 0
    for to in cmb[1:]:
        tmpres += min_ds[prev,to]
        prev = to
    res = min(res, tmpres)

print(int(res))

Submission status: Accepted

Solution code:
from collections import deque

N, M, R = map(int, input().split())
Rs = set(map(int, input().split()))

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

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

for _ in range(M):
  a,b,c = map(int, input().split())
  mp[a][b] = c
  mp[b][a] = c
  
for k in range(1,N+1):
  for i in range(1,N+1):
    for j in range(1,N+1):
      mp[i][j] = min(mp[i][j], mp[i][k]+mp[k][j])

rlt = float('inf')
h = deque([])
for r in Rs:
  h.append([r])
  
while h:
  t = h.pop()
  if len(t) == R:
    tmp = 0
    for i in range(R-1):
      tmp += mp[t[i]][t[i+1]]
    rlt = min(rlt, tmp)
  else:
    for r in Rs:
      if r not in t:
        u = t + [r]
        h.append(u)

print(rlt)

Submission status: Accepted

Solution code:
from itertools import permutations
INF=10**18
n,m,r=map(int,input().split())
dist=[[INF for _ in range(n+1)]for _ in range(n+1)]
dp=[[-1 for _ in range(r+1)]for _ in  range((1<<r)+1)]
r_t=list(map(int,input().split()))
for i in range(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(n+1):
  for i in range(n+1):
    for j in range(n+1):
      dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])
r_list=list(permutations(r_t))
fans=INF
for i in r_list:
  ans=0
  for j in range(r-1):
    ans+=dist[i[j+1]][i[j]]
  fans=min(fans,ans)
print(fans)

Submission status: Accepted

Solution code:
N, M, R = map(int, input().split())
*r, = map(lambda x:int(x)-1, input().split())
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())
    D[a-1][b-1] = c
    D[b-1][a-1] = c

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

import itertools
ans = float('inf')
for s in itertools.permutations(r, R):
    tot = [D[s[i]][s[i+1]] for i in range(R-1)]
    tot = sum(tot)
    ans = min(ans, tot)

print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
from operator import mul

INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 組合せnCr
def combinations_count(n, r):
    if n < r:
        return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]



# ここから書き始める
n, m, r = map(int, input().split())
cities = list(map(int, input().split()))
a = [0 for i in range(m)]
b = [0 for i in range(m)]
c = [0 for i in range(m)]
for i in range(m):
    a[i], b[i], c[i] = map(int, input().split())
    a[i] -= 1
    b[i] -= 1

d = [[INF for j in range(n)] for i in range(n)]
for i in range(m):
    d[a[i]][b[i]] = c[i]
    d[b[i]][a[i]] = c[i]
for i in range(n):
    d[i][i] = 0

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

ans = INF
for i in permutations(cities):
    total = 0
    for j in range(1, r):
        total += d[i[j] - 1][i[j - 1] - 1]
    ans = min(ans, total)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

n,m,r=list(map(int,input().split()))
rlst=list(map(int,input().split()))
inf=10**20

d=[[inf]*(n+1) for _ in range(n+1)]

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

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 comb in permutations(rlst,r):
    i=0
    tans=0

    while i+1<r:
        tans+=d[comb[i]][comb[i+1]]
        i+=1
    
    ans=min(ans,tans)

print(ans)

Submission status: Accepted

Solution code:
n, m, r = map(int, input().split())
R = tuple(map(lambda x: int(x)-1, input().split()))
INF = 10**9
dp = [[INF]*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 k in range(n):
    for i in range(n):
        for j in range(n):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

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

Submission status: Accepted

Solution code:
import itertools

INF = 10**10
N, M, R = map(int, input().split())
*r, = map(int, input().split())
r = [v-1 for v in r]

g = [[INF]*N for _ in range(N)]
for i in range(N):
    g[i][i] = 0

for m in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    g[a][b] = c
    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])

ans = INF
for rs in itertools.permutations(r):
    cost = 0
    for i in range(len(rs)-1):
        cost += g[rs[i]][rs[i+1]]
    if cost < ans:
        ans = cost

print(ans)

Submission status: Accepted

Solution code:
N,M,R = map(int,input().split())
R = list(map(int,input().split()))
dp = [[float("INF")]*(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] = min(dp[a][b],c)
    dp[b][a] = min(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][k],dp[j][i]+dp[i][k])

def dfs(p,n,path,cost):
    path.add(n)
    cost += dp[p][n]
    
    if len(path) == len(R):
        return cost
    else:
        res = float("INF")
        for r in R:
            if r not in path:
                res = min(res,dfs(n,r,path,cost))
                path.remove(r)
        return res
ans = float("INF")
for r in R:
    ans = min(ans,dfs(r,r,set(),0))
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import permutations
import heapq

INF = float('inf')
N, M, R = map(int, input().split())
r = list(map(int, input().split()))

Adj_list = defaultdict(set)

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


def dijkstra(x, vertex):
    d = [INF] * x
    d[vertex] = 0
    hq = [(0, vertex)]
    
    while hq:
        u = heapq.heappop(hq)[1]
        for (v, c) in Adj_list[u]:
            if d[v] > d[u] + c:
                d[v] = d[u] + c
                heapq.heappush(hq, (d[u]+c, v))

    return d

ans = INF
t_dis = 0

table = {}
for i in r:
    table[i-1] = dijkstra(N, i-1)

for each in permutations(r):
    t_dis = 0
    for i in range(R-1):
        t_dis += table[each[i]-1][each[i+1]-1]

    ans = min(ans, t_dis)

print(ans)

Submission status: Accepted

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

from itertools import permutations
from collections import defaultdict

N, M, R = map(int, input().split())
G = defaultdict(list)
d =[ [float("inf")] * N for i in range(N)]
listR = list(map(int, input().split()))
for _ in range(M):
    ai, bi, ci = map(int, input().split())
    ai, bi = ai - 1, bi - 1
    G[ai].append((bi, ci))
    G[bi].append((ai, ci))
    d[ai][bi] = d[bi][ai] = ci

# わーしゃるふろいど
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])

# print(d)

# 全てのpermutations (of R)を試す
ans = float("inf")
for perm in permutations(listR):
    cost_perm = 0
    for i in range(len(perm) - 1):
        pi, pj = perm[i] - 1, perm[i + 1] - 1
        cost_perm += d[pi][pj]
    ans = min(ans, cost_perm)
print(ans)

Submission status: Accepted

Solution code:
import itertools

N, M, R = map(int, input().split())
r = map(int, input().split())
A = [[1 << 64]*N for _ in range(N)]
for i in range(N):
    A[i][i] = 0
for _ in range(M):
    a, b, c = map(int, input().split())
    A[a-1][b-1] = A[b-1][a-1] = c

# Warshall-Floyd
for k in range(N):
    for i in range(N):
        for j in range(N):
            A[i][j] = min(A[i][j], A[i][k] + A[k][j])

res = 1 << 64
for perm in itertools.permutations([x-1 for x in r]):
    cost = 0
    for i in range(R-1):
        cost += A[perm[i]][perm[i+1]]
    if cost < res:
        res = cost

print(res)

Submission status: Accepted

Solution code:
from itertools import permutations
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
r = permutations(r, len(r))
INF = 10**10
dist = [[INF]*N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    dist[a-1][b-1] = dist[b-1][a-1] = c
for k in range(N):
    for i in range(N):
        for j in range(N):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] =  dist[j][i] = dist[i][k] + dist[k][j]
ans = INF
for i in r:
    tmp = 0
    for j in range(len(i)-1):
        tmp += dist[i[j]-1][i[j+1]-1]
    ans = min(ans, tmp)
print(ans)