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:
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import permutations
from heapq import heappush, heappop

def dijkstra(graph:list, node:int, start:int) -> list:
    # 未探索のノードは距離INF
    INF = float("inf")
    dist = [INF]*node
    
    # 始点ノードの距離を0とし、dfsのためのpriority queを作成
    dist[start] = 0
    heap = [(0,start)]
    searched = [False for _ in range(node)]
    
    # 未探索のノードをpriority queueに入れる
    while heap:
        cost, cur_node = heappop(heap)
        
        if searched[cur_node] or cost > dist[cur_node]:
            continue
        
        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heappush(heap, (dist[nex_node], nex_node))
    
        searched[cur_node] = True
        
        if sum(searched) == node:
            break
    
    return dist

n,m,r = li()
r = list(li_())
graph = [[] for _ in range(n)]
for _ in range(m):
    a,b,c = li()
    a -= 1
    b -= 1
    graph[a].append((c,b))
    graph[b].append((c,a))
    
dists = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    dists[i] = dijkstra(graph, n, i)

routes = list(permutations(r))

ans = 2**64-1
for route in routes:
    temp = 0
    for i in range(len(route)-1):
        temp += dists[route[i]][route[i+1]]
        
    ans = min(ans,temp)
    
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

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

n,m,r = li()
r = list(li_())
abc = []
graph = np.zeros((n,n))
for _ in range(m):
    a,b,c = li()
    a -= 1
    b -= 1
    graph[a][b] = c
    graph[b][a] = c
    
floyd_warshall(graph, directed=False, overwrite=True)

routes = list(permutations(r))

ans = float("inf")
for route in routes:
    cand = 0
    for i in range(len(route)-1):
        cand += graph[route[i]][route[i+1]]
        
    ans = min(ans, cand)
        
print(int(ans))

Submission status: Accepted

Solution code:
import itertools
N,M,R = map(int,input().split())
towns = list(map(lambda x:int(x)-1,input().split()))
INF = float('inf')
es = [[INF]*N for i in range(N)]
for i in range(N):
    es[i][i] = 0
for i in range(M):
    a,b,c = map(int,input().split())
    a,b = a-1,b-1
    es[a][b] = es[b][a] = c

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

ans = INF
for ptn in itertools.permutations(range(R)):
    tmp = 0
    for a,b in zip(ptn, ptn[1:]):
        t1,t2 = towns[a],towns[b]
        tmp += es[t1][t2]
    ans = min(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
# coding:utf-8

import itertools

INF = float('inf')


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


def dijkstra(graph, start):
    MAX_SIZE = len(graph)
    visited = [False for _ in range(MAX_SIZE)]
    cost = [INF for _ in range(MAX_SIZE)]
    prev = [None for _ in range(MAX_SIZE)]

    cost[start] = 0
    prev[start] = start
    path = [start + 1]
    while True:
        min_cost = INF
        next = -1
        visited[start] = True
        # 頂点の選択
        for i in range(MAX_SIZE):
            if visited[i]: continue  # 探索済みの頂点は飛ばす
            if graph[start][i]:  # 頂点startと接続されているか判定
                dist = cost[start] + graph[start][i]
                if dist < cost[i]:
                    cost[i] = dist
                    prev[i] = start

            if cost[i] < min_cost:
                min_cost = cost[i]
                next = i

        start = next
        path.append(next + 1)
        if next == -1: break

    # print(cost)
    # print(path)
    return cost


def main():
    N, M, R = inpl()
    r = inpl()

    G = [[None for _ in range(N)] for _ in range(N)]
    for i in range(M):
        a, b, c = inpl()
        G[a - 1][b - 1] = c
        G[b - 1][a - 1] = c

    min_cost = {}
    for s in r:
        min_cost[str(s)] = dijkstra(G, s - 1)

    ans = INF
    for root in itertools.permutations(r, R):
        dist = 0
        for i in range(R - 1):
            s = str(root[i])
            dist += min_cost[s][root[i + 1] - 1]
        ans = min(ans, dist)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
fn = lambda: map(int, input().split())
N, M, R = fn()
r = [int(ri) - 1 for ri in input().split()]
A, B, C = [0]*M, [0]*M, [0]*M
for i in range(M):
    A[i], B[i], C[i] = fn()
    A[i], B[i] = A[i]-1, B[i]-1

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
from itertools import permutations

G = csr_matrix(((C, (A, B))), shape=(N, N))
D = floyd_warshall(G, directed=False)

best = float('inf')
for route in permutations(r):
    d = sum([D[route[i], route[i+1]] for i in range(len(route) - 1)])
    best = min(d, best)
print(int(best))

Submission status: Accepted

Solution code:
import sys
from itertools import permutations

from scipy.sparse.csgraph import floyd_warshall

input = sys.stdin.readline

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

g = [[float('inf')] * N for _ in range(N)]
for i in range(M):
    A, B, C = map(int, input().split())
    g[A - 1][B - 1] = C
    g[B - 1][A - 1] = C

dist = floyd_warshall(g, directed=False)
ans = float('inf')
for route in permutations(r):
    res = 0
    for i in range(R - 1):
        res += dist[route[i]][route[i + 1]]
    ans = min(ans, int(res))
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
N,M,R = map(int,input().split())
r = list(map(int,input().split()))

d = [[float('inf') for _ in range(N)] for _ in range(N)]
for _ in range(M):
    a,b,c = map(int,input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
for i in range(N):
    d[i][i]=0
from scipy.sparse import csgraph
d = csgraph.floyd_warshall(d)
ans = float('inf')
for seq in permutations(r):
    s = 0
    for j in range(R-1):
        s += d[seq[j]-1][seq[j+1]-1]
    ans = min(ans,s)
print(int(ans))

Submission status: Accepted

Solution code:
from itertools import permutations
import heapq

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

cost = {}
for i in range(m):
    a, b, c = list(map(int, input().split()))
    if not a in cost.keys():
        cost[a] = [(b, c)]
    else:
        cost[a].append((b, c))
    if not b in cost.keys():
        cost[b] = [(a, c)]
    else:
        cost[b].append((a, c))
        
dist = [[INF]*(n+1) for _ in range(n+1)]
for st in r:
    d = [INF]*(n+1)
    d[st] = 0
    path = [(0, st)]
    heapq.heapify(path)
    while len(path) > 0:
        c, node = heapq.heappop(path)
        if d[node] < c:
            continue
        d[node] = c
        for node_next, c_next in cost[node]:
            if d[node_next] < INF:
                continue
            heapq.heappush(path, (d[node]+c_next, node_next))
    dist[st] = d
# for d in dist: print(d)

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

Submission status: Accepted

Solution code:
from itertools import permutations
import heapq

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

cost = {}
for i in range(m):
    a, b, c = list(map(int, input().split()))
    if not a in cost.keys():
        cost[a] = [(b, c)]
    else:
        cost[a].append((b, c))
    if not b in cost.keys():
        cost[b] = [(a, c)]
    else:
        cost[b].append((a, c))
        
dist = [[INF]*(n+1) for _ in range(n+1)]
for st in r:
    d = [INF]*(n+1)
    d[st] = 0
    path = [(0, st)]
    heapq.heapify(path)
    while len(path) > 0:
        c, node = heapq.heappop(path)
        if d[node] < c:
            continue
        d[node] = c
        for node_next, c_next in cost[node]:
            if d[node]+c_next < d[node_next]:
                heapq.heappush(path, (d[node]+c_next, node_next))
    dist[st] = d
# for d in dist: print(d)

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

Submission status: Accepted

Solution code:
from itertools import permutations

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

from scipy.sparse import csgraph
dist = csgraph.floyd_warshall(dist)
# 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])
# for d in dist: print(d)

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

Submission status: Accepted

Solution code:
from itertools import permutations as p
N,M,R=map(int,input().split())
r=map(int,input().split())
inf=float("inf")
l=[[inf if i!=j else 0 for i in range(N)] for j in range(N)]

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

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

ans=inf
for i in p(r):
  v=0
  for j in range(R-1):
    v+=l[i[j]-1][i[j+1]-1]
  ans=min(ans,v)
print(ans)

Submission status: Accepted

Solution code:
def d_joisino_travel(N, M, R, Route, Road):
    # N:国の中の町の数
    # M:町を結ぶ道の総数
    # R:訪れる町の数
    # Route:訪れる町の番号
    # Road:町の結び方とその間の距離
    from itertools import permutations
    from scipy.sparse import csgraph

    graph = [[float('inf')] * N for j in range(N)]  # 町同士の距離
    for i in range(N):
        graph[i][i] = 0
    for m, n, c in Road:
        graph[m - 1][n - 1] = c
        graph[n - 1][m - 1] = c
    dist = csgraph.floyd_warshall(graph)

    ans = float('inf')
    for route in permutations([x - 1 for x in Route]):
        cost = 0
        for j in range(R - 1):  # route(行く町の順列)の先頭から2つ要素を拾う
            cost += dist[route[j]][route[j + 1]]
        ans = min(ans, cost)
    return int(ans)

N, M, R = [int(i) for i in input().split()]
Route = [int(i) for i in input().split()]
Road = [[int(i) for i in input().split()] for j in range(M)]
print(d_joisino_travel(N, M, R, Route, Road))

Submission status: Accepted

Solution code:
import itertools
n, m, R = map(int, input().split())
r = list(map(int, input().split()))
INF = float("inf")
G = [[INF] * n for i in range(n)]

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

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

num = INF
for per in itertools.permutations(r):
    rec = 0
    pre = per[0] - 1
    for j in range(1, len(r)):
        rec += G[pre][per[j] - 1]
        pre = per[j] - 1
        if rec > num:
            break

    num = min(rec, num)

print(num)

Submission status: Accepted

Solution code:
INF = int(1e9)
N, M, K = list(map(int, input().split()))
R = list(map(lambda x: int(x) - 1, input().split()))

G = [[INF] * N for i in range(N)]
for i in range(N):
    G[i][i] = 0
            
for i in range(M):
    a, b, c = list(map(int, input().split()))
    a = a - 1
    b = b - 1
    G[a][b] = G[b][a] = c
    
ls = range(N)
for k in ls:
    for i in ls:
        for j in range(i+1,N):
            x = G[i][k] + G[k][j]
            if x < G[i][j]:
                G[i][j] = G[j][i] = x

dp = [[INF] * (1<<K) for i in range(K)]
for i in range(K):
    dp[i][1<<i] = 0

for bit in range(1<<K):
    for pre in range(K):
        if (bit >> pre) & 1 == 0:
            continue
        for to in range(K):
            if (bit >> to) & 1 == 1:
                continue
            cost = dp[pre][bit] + G[R[pre]][R[to]]
            nbit = bit | (1<<to)
            if dp[to][nbit] > cost:
                dp[to][nbit] = cost

ans = INF     
for pre in range(K):
    ans = min(ans, dp[pre][(1<<K) - 1])
print (ans)

Submission status: Accepted

Solution code:
from itertools import permutations, product
from collections import defaultdict
from heapq import heappop, heappush

N, M, R = map(int, input().split())
r = [int(x) for x in input().split()]
abc = [[int(x) for x in input().split()] for _ in range(M)]


class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    def __init__(self, graph, start):
        g = graph.graph

        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0
        self.prev = defaultdict(lambda: None)

        Q = []
        heappush(Q, (self.dist[start], start))

        while Q:
            dist_u, u = heappop(Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(Q, (alt, v))

    def shortest_distance(self, goal):
        return self.dist[goal]

    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


g = Graph()
for a, b, c in abc:
    g.add_edge(a - 1, b - 1, c)
    g.add_edge(b - 1, a - 1, c)

D = dict()
for ri in r:
    D[ri - 1] = Dijkstra(g, ri - 1)

ans = float('inf')
for route in permutations(r):
    d = 0
    for i in range(R - 1):
        s = route[i] - 1
        g = route[i + 1] - 1
        d += int(D[s].shortest_distance(g))
    ans = min(ans, d)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations, product
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

N, M, R = map(int, input().split())
r = [int(x) for x in input().split()]
abc = [[int(x) for x in input().split()] for _ in range(M)]

dist = [[float('inf') for _ in range(N)] for _ in range(N)]
A, B, C = [0] * M, [0] * M, [0] * M
for i in range(M):
    a, b, c = abc[i]
    A[i] = a - 1
    B[i] = b - 1
    C[i] = c

g = csr_matrix((C, (A, B)), shape=(N, N), dtype=int)
dist = floyd_warshall(g, directed=False)

ans = float('inf')
for route in permutations(r):
    d = 0
    for i in range(R - 1):
        s = route[i] - 1
        g = route[i + 1] - 1
        d += int(dist[s][g])
    ans = min(ans, d)
print(ans)

Submission status: Accepted

Solution code:
import itertools
N, M, R = map(int, input().split())
r = [int(x) - 1 for x in input().split()]
G = [[10 ** 7 for j in range(N)] for i in range(N)]
for i in range(N):
  G[i][i] = 0
for i in range(M):
  a, b, c = map(int, input().split())
  G[a - 1][b - 1] = c
  G[b - 1][a - 1] = c
def warshall_floyd(G):
  for k in range(N):
    for i in range(N):
      for j in range(N):
        G[i][j] = min(G[i][k] + G[k][j], G[i][j])
  return G
G = warshall_floyd(G)
D = 10 ** 8
for L in itertools.permutations(r):
  d = 0
  pre = L[0]
  for l in L[1:]:
    d += G[pre][l]
    pre = l
  D = min(d, D)
print(D)

Submission status: Accepted

Solution code:
from itertools import permutations, product

N, M, R = map(int, input().split())
r = [int(x) for x in input().split()]
abc = [[int(x) for x in input().split()] for _ in range(M)]

dist = [[float('inf') for _ in range(N)] for _ in range(N)]
for a, b, c in abc:
    dist[a - 1][b - 1] = c
    dist[b - 1][a - 1] = c

for k, i, j in product(range(N), repeat=3):
    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

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

Submission status: Accepted

Solution code:
N, M, R = map(int, input().split())
RL = [int(x) for x in input().split()]

import heapq
def dijkstra(adj, n, st=1):
    dj = [2**64] * (n + 1)
    dj[st] = 0
    q = []
    heapq.heappush(q, (0, st))
    while q:
        fc, fn = heapq.heappop(q)
        if dj[fn] < fc: continue
        for tn, lc in adj[fn]:
            if dj[fn] + lc < dj[tn]:
                dj[tn] = dj[fn] + lc
                heapq.heappush(q, (dj[tn], tn))
    return dj

adj = dict((x, []) for x in range(N + 1))
for _ in range(M):
    a, b, c = map(int, input().split())
    adj[a].append((b, c))
    adj[b].append((a, c))

costs = [None] * len(RL)
for i, r in enumerate(RL):
    costs[i] =  dijkstra(adj, N, r)

import functools
@functools.lru_cache(maxsize=None)
def f(last, cost, left):
    if not left: return cost
    ret = float('inf')
    for i, x in enumerate(left):
        ret = min(ret, f(x, cost + costs[RL.index(last)][x], left[:i] + left[i+1:]))
    return ret

print(min(f(x, 0, tuple(set(RL) - set([x]))) for x in RL))

Submission status: Accepted

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

fn = lambda: [int(x) for x in input().split()]
N, M, R = fn()
r = [int(ri) - 1 for ri in input().split()]
A, B, C = [0]*M, [0]*M, [0]*M
for i in range(M):
    A[i], B[i], C[i] = fn()
    A[i], B[i] = A[i] - 1, B[i] - 1

G = csr_matrix((C, (A, B)), shape=(N, N), dtype=int)
D = floyd_warshall(G, directed=False)

routes = permutations(r)
result = float('inf')
for route in routes:
    d = sum([D[route[i], route[i+1]] for i in range(len(route) - 1)])
    result = min(result, d)
print(int(result))

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

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


N,M,R = inpl()
rr = inpl()

weight = [[INF for i in range(N)] for j in range(R)]
for r in range(R):
	weight[r][rr[r]-1] = 0

lines = defaultdict(set)
for i in range(M):
	a,b,c = inpl()
	a -= 1
	b -= 1
	lines[a].add((b,c))
	lines[b].add((a,c))

def search (s,w_0,r):
	global weight
	global q
	for line in list(lines[s]):
		t = line[0]
		w = w_0 + line[1]
		if weight[r][t] > w:
			heapq.heappush(q, [w,t])
			weight[r][t] = w

for r in range(R):
	q = [ [0, rr[r]-1] ]
	heapq.heapify(q)
	while q:
		w_0,s = heapq.heappop(q)
		search(s,w_0,r)

ans = INF
for li in list(itertools.permutations(range(R))):
	tmp = 0
	for i in range(R-1):
		s = li[i]
		t = li[i+1]
		tmp += weight[s][rr[t]-1]
	ans = min(ans,tmp)

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def warshall_floyd(g):
    d = defaultdict(dict)
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v))
    V = set(V)
    for i in V:
        for j in V:
            if i in g and j in g[i]:
                d[i][j] = g[i][j]
            else:
                d[i][j] = sys.maxsize
    for k in g:
        for i in g:
            for j in g:
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]

    return d


@mt
def slv(N, M, R, ABC):
    g = defaultdict(dict)
    for a, b, c in ABC:
        g[a][b] = c
        g[b][a] = c

    d = warshall_floyd(g)
    ans = sys.maxsize
    for m in permutations(R):
        c = 0
        for i in range(len(R)-1):
            c += d[m[i]][m[i+1]]
        ans = min(ans, c)

    return ans


def main():
    N, M, R = read_int_n()
    R = read_int_n()
    ABC = [read_int_n() for _ in range(M)]
    print(slv(N, M, R, ABC))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from scipy.sparse import*
from itertools import permutations as pm

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

u,v,l = zip(*[map(int,input().split()) for i in range(m)])

A=csgraph.dijkstra(csr_matrix((l,(u,v)),[n+1]*2),0)

s=min(sum(A[i][j] for i,j in zip(a[:-1],a[1:])) for a in pm(r))
print(int(s))

Submission status: Accepted

Solution code:
from scipy.sparse import*
from itertools import permutations as pm

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

u,v,l = zip(*[map(int,input().split()) for i in range(m)])

A=csgraph.dijkstra(csr_matrix((l,(u,v)),(n+1,n+1)),0)

s=min(sum(A[i][j] for i,j in zip(a[:-1],a[1:])) for a in pm(r))
print(int(s))

Submission status: Accepted

Solution code:
import itertools
N,M,R=map(int,input().split())
r=[int(i)-1 for i in input().split()]
P=[set() for i in range(N)]
for i in range(M):
    A,B,C=map(int,input().split())
    P[A-1].add((B-1,C))
    P[B-1].add((A-1,C))
p=[[0 for i in range(R)] for i in range(R)]
def dijkstra(s):
    d=[10**9 for i in range(N)]
    d[s]=0
    Q=set(range(N))
    while(len(Q)>0):
        u=list(Q)[0]
        for v in Q:
            if d[v]<d[u]:
                u=v
        Q-=set([u])
        for v in P[u]:
            if d[v[0]]>d[u]+v[1]:
                d[v[0]]=d[u]+v[1]
    return d
for i in range(R):
    L=dijkstra(r[i])
    for j in range(R):
        p[i][j]=L[r[j]]
S=list(itertools.permutations(range(R),R))
ans=10**9
for sg in S:
    tmp=0
    for i in range(R-1):
        tmp+=p[sg[i]][sg[i+1]]
    if tmp<ans:
        ans=tmp
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

INF = 1 << 40
G, dist = [[] for i in range(N)], [[INF for k in range(N)] for j in range(N)]


def dijkstra(s):
    check = [0 for i in range(N)]
    dist[s][s], pq = 0, []
    heapq.heappush(pq, (0, s))

    while len(pq) != 0:
        u = heapq.heappop(pq)
        check[u[1]] = 2

        if dist[s][u[1]] < u[0]:
            continue

        for v in G[u[1]]:
            if dist[s][u[1]] + v[1] < dist[s][v[0]]:
                dist[s][v[0]], check[v[0]] = dist[s][u[1]] + v[1], 1
                heapq.heappush(pq, (dist[s][v[0]], v[0]))


check_dfs, cost_lst = [0 for m in range(R)], []


def dfs(s, cnt, cost):
    if cnt == 0:
        cost_lst.append(cost)
        return

    for i in range(R):
        if check_dfs[i] == 0:
            check_dfs[i] = 1
            dfs(r[i]-1, cnt-1, cost+dist[s][r[i]-1])
            check_dfs[i] = 0


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

    for i in range(R):
        dijkstra(r[i]-1)

    for i in range(R):
        check_dfs[i] = 1
        dfs(r[i]-1, R-1, 0)
        check_dfs[i] = 0

    print(min(cost_lst))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
from itertools import permutations
#グラフの作成   
def make_list(V,E):
 
    edges = []
    path=[[0]*E for i in range(V) ]   #ルート作成に必要になる
    
    for i in range(V):
        a=[int(x) for x in str(input()).split()]
        for j in range(len(a)):
            #print("j",j)
            path[i][j]=i
           # if j!= i and a[j]==0:
                #a[j]=2000
                #path[i][j]=-2000
	
        edges.append((a))    #  有効辺グラフ
	

   
     
    return edges ,path


#フロイド・ワーシャル
def warshall_floyd(glath):
	
	for k in range(len(glath)):
		for i in range(len(glath)):
			for j in range(len(glath[i])):
				if glath[i][j] > glath[i][k] + glath[k][j]:
                                   glath[i][j] = glath[i][k] + glath[k][j]
                                   glath[j][i] = glath[i][k] + glath[k][j]
				#glath[i][j]= min(int(glath[i][j]),int(glath[i][k])+int(glath[k][j]))
				
	return glath





N, M ,R= [int(x) for x in str(input()).split()]  #グラフの大きさ 

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


graph=[[float("inf")]*N for i in range(N)]


for i in range(M):
	a,b,c=[int(x) for x in str(input()).split()]
	#if a in r and b in r:
	graph[a-1][b-1]=c
	graph[b-1][a-1]=c



#all_cost=warshall_floyd(select_graph)
all_cost=warshall_floyd(graph)


#print(all_cost)
#print(all_cost[r[0]-1-a][r[-1]-1-a])
#print(r[-1]-1-a)

max_count=float("inf")


for i in permutations(r):
        cost=0
        for j in range(len(i)-1):
                
                cost+= all_cost[i[j]-1][i[j+1]-1]
       
        max_count=min(max_count,cost)


#			max_count=min(max_count,all_cost[i-a-1][j-a-1]+all_cost[j-a-1][j-a-1])


print(max_count)

Submission status: Accepted

Solution code:
from itertools import permutations

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

visit = list(map(int, input().split()))
g = [[float('inf')] * N for _ in range(N)]
for i in range(N):
    g[i][i] = 0

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


def dijkstra(start):
    c_l = [float('inf')] * N
    c_l[start] = 0
    visited = [False] * N
    while True:
        min_v = float('inf')
        next = -1
        visited[start] = True
        for i in range(N):
            if visited[i]:
                continue
            if g[start][i]:
                d = c_l[start] + g[start][i]
                if d < c_l[i]:
                    c_l[i] = d
                if min_v > c_l[i]:
                    min_v = c_l[i]
                    next = i
        start = next
        if next == -1:
            break
    return c_l


cost_list = []
for i in range(N):
    cost_list.append(dijkstra(i))

cost = float('inf')
for town in permutations(visit):
    c = 0
    for i in range(R - 1):
        c += cost_list[town[i] - 1][town[i + 1] - 1]
    cost = min(cost, c)
print(cost)

Submission status: Accepted

Solution code:
import itertools

n,m,R = map(int,input().split())
r = list(map(int,input().split()))
data = [[]for _ in range(0,n+1)]
d = [[] for _ in range(0,R)]

for i in range(0,m):
    a,b,c = map(int,input().split())
    data[a].append((b,c))
    data[b].append((a,c))

def dijkstra(start,num):
    g = [float("inf") for _ in range(0,n+1)]
    used = ["false" for _ in range(0,n+1)]
    g[start] = 0
    queue= []
    queue.append((start,data[start]))
    while queue:
        start,edge = queue.pop(0)
        for to,cost in edge:
            if g[to] > g[start] + cost:
                g[to] = g[start] + cost
                queue.append((to,data[to]))
    for i in range(0,R):
        d[num].append(g[r[i]])
    # print(g)
# dijkstra(1,0)

for i in range(0,R):
    dijkstra(r[i],i)
    # print(d[i])
ans = float("inf")
seq = itertools.permutations([i for i in range(0,R)])
for i in seq:
    dis = 0
    for j in range(0,len(i)-1):
        dis += d[i[j]][i[j+1]]
    if ans > dis:
        ans = dis
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

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

INF=float('inf')
d=[[INF for x in range(N)] for y in range(N)]

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

for i in range(N):
  for j in range(N):
    for k in range(N):
      if d[j][i]+d[i][k] < d[j][k]:
        d[j][k]=d[j][i]+d[i][k]

ans=INF
for root in permutations(r):
  cnt=0
  for i in range(R-1):
    cnt+=d[root[i]-1][root[i+1]-1]
    if cnt>ans:
      break
  ans=min(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
N, M, Rs = map(int, input().split())
R = list(map(int, input().split()))
D = [[float("inf")] * (N+1) for i in range(N+1)]
for i in range(M):
    a, b, c = map(int, input().split())
    D[a][b] = D[b][a] = c

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


def full(L):
    if len(L) == 1:
        return [L]
    else:
        L2 = []
        for i in range(len(L)):
            L2.extend([[L[i]] + Lc for Lc in full(L[:i] + L[i+1:])])
        return L2


L = full(R)
ans = float("inf")
for l in L:
    a = 0
    for i in range(Rs-1):
        a += D[l[i]][l[i+1]]
    ans = min(ans, a)

print(ans)