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 solve(n, m, r):
    ans = 10**18
    d = [[10**18]*n for _ in range(n)]
    rx = list(i-1 for i in map(int, input().split()))

    for i in range(m):
        s, t, length = map(int, input().split())
        d[s-1][t-1] = length
        d[t-1][s-1] = length

    for i in range(n):
        d[i][i] = 0

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

    for p in permutations(rx):
        from_p1_to_pr = 0
        for p_j,  p_next in zip(p, p[1:]):
            from_p1_to_pr += d[p_j][p_next]
        if from_p1_to_pr < ans:
            ans = from_p1_to_pr

    return ans


if __name__ == '__main__':
    n, m, r = map(int, input().split())
    print(solve(n, m, r))

Submission status: Accepted

Solution code:
import itertools
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
r = list(map(lambda x: x - 1, r))
d = [[10 ** 10] * 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

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 = 10 ** 10

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

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
N,M,R=map(int,input().split())
r=list(map(int,input().split()))
inf=10**9
d=[[inf]*N for i 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 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 l in permutations(r):
  start=0
  for j in range(R-1):
    start+=d[l[j]-1][l[j+1]-1]
  ans=min(start,ans)
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

# 距離表の初期化
INF = 10 ** 12
dist = [[INF] * N for _ in range(N)]
for i in range(N):
	dist[i][i] = 0

# グラフを読み込みつつ距離表の更新
for a, b, c in ABC:
	a, b = 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])

#print(dist)

# 全探索(*^_^*)つ[rCr]
min_dist = INF
for p in itertools.permutations(r):
	d = 0
	for n in range(1, R):
		d += dist[p[n] - 1][p[n - 1] - 1]
	if d < min_dist:
		min_dist = d
		#print(d, p)
print(min_dist)

Submission status: Accepted

Solution code:
from itertools import permutations
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(M)]

graph = [[float('inf')] * N for _ in range(N)]
for i in range(N):
    graph[i][i] = 0

for u, v, l in edges:
    graph[u - 1][v - 1] = l
    graph[v - 1][u - 1] = l

for k in range(N):
    for i in range(N):
        if graph[i][k] == float('inf'):
            continue
        for j in range(N):
            if graph[k][j] == float('inf'):
                continue
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

ans = 10 ** 9 + 7
for l in permutations(r, R):
    ans = min(ans, sum(graph[l[i] - 1][l[i + 1] - 1] for i in range(R - 1)))
        
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!


"""
Dijkstra法: 単一始点最短路（距離が正）
g: g[i] = [(子、距離),...]の隣接リスト
start: 始点
"""
from heapq import heappush, heappop
def dijkstra(g,start): #g: 隣接リスト
    dist = [1e18]*(len(g)) #初期化
    q = [(0,start)] #(そこまでの距離、点)
    dist[start] = 0
    pending = len(g)-1
    while q and pending:
        c,v = heappop(q)
        if dist[v] < c: continue
        pending -= 1
        for to, cost in g[v]:
            if dist[v] + cost < dist[to]:
                dist[to] = dist[v] + cost
                heappush(q, (dist[to], to))
    return dist


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

inf = 10**9
g = [[] for _ in range(n)]
for _ in range(m):
    a,b,c = [int(i) for i in input().split()]
    g[a-1].append((b-1, c))
    g[b-1].append((a-1, c))


dvec = [None]*R
for i, ri in enumerate(r):
    dvec[i] = dijkstra(g, ri)

m = {ri:i for i, ri in enumerate(r)}    

ans = inf
import itertools
for x in itertools.permutations(r):
    c = 0
    for i, xi in enumerate(x):
        if i > 0:
            c += dvec[m[xi]][x[i-1]]
    if c < ans:
        ans = c
            
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

from heapq import heappush, heappop
def dijkstra(g,start): #g: 隣接リスト
    inf = float("inf")
    dist = [inf]*(len(g))
    q = [(start,0)] #(点、そこまでの距離)
    dist[start] = 0
    while q:
        v,c = heappop(q)
        if dist[v] < c: continue
        for to, cost in g[v]:
            if dist[v] + cost < dist[to]:
                dist[to] = dist[v] + cost
                heappush(q, (to, dist[to]))
    return dist


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

inf = 10**9
g = [[] for _ in range(n)]
for _ in range(m):
    a,b,c = [int(i) for i in input().split()]
    g[a-1].append((b-1, c))
    g[b-1].append((a-1, c))


dvec = [None]*R
for i, ri in enumerate(r):
    dvec[i] = dijkstra(g, ri)

m = {ri:i for i, ri in enumerate(r)}    

ans = inf
import itertools
for x in itertools.permutations(r):
    c = 0
    for i, xi in enumerate(x):
        if i > 0:
            c += dvec[m[xi]][x[i-1]]
    if c < ans:
        ans = c
            
print(ans)

Submission status: Accepted

Solution code:
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 = [int(x) for x in input().split()]
graph = [[float('inf')]*(N+1) for _ in range(N+1)]
r = [int(x) for x in input().split()]

for _ in range(M):
    s,d,w = [int(x) for x in input().split()]
    graph[s][d] = w
    graph[d][s] = w

warshall_floyd(graph,N+1)
ans = float('inf')
for _r in itertools.permutations(r):
    di = 0
    for ind,j in enumerate(_r[:-1]):
        di+=graph[j][_r[ind+1]]
    ans = min(ans,di)

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import string
import sys
from itertools import chain, dropwhile, takewhile, permutations


def read(
    *shape, f=int, it=chain.from_iterable(sys.stdin), whitespaces=set(string.whitespace)
):
    def read_word():
        w = lambda c: c in whitespaces
        nw = lambda c: c not in whitespaces
        return f("".join(takewhile(nw, dropwhile(w, it))))

    if not shape:
        return read_word()
    elif len(shape) == 1:
        return [read_word() for _ in range(shape[0])]
    elif len(shape) == 2:
        return [[read_word() for _ in range(shape[1])] for _ in range(shape[0])]


def readi(*shape):
    return read(*shape)


def readi1(*shape):
    return [i - 1 for i in readi(*shape)]


def readf(*shape):
    return read(*shape, f=float)


def reads(*shape):
    return read(*shape, f=str)


def arr(*shape, fill_value=0):
    if len(shape) == 1:
        return [fill_value] * shape[fill_value]
    elif len(shape) == 2:
        return [[fill_value] * shape[1] for _ in range(shape[0])]


def dbg(**kwargs):
    print(
        ", ".join("{} = {}".format(k, repr(v)) for k, v in kwargs.items()),
        file=sys.stderr,
    )


def main():
    N, M, R = readi(3)
    rs = readi1(R)

    G = arr(N, N, fill_value=10 ** 10)
    for i in range(N):
        G[i][i] = 0

    for _ in range(M):
        a, b, c = readi(3)
        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][j], G[i][k] + G[k][j])

    ans = 10 ** 10
    for perm in permutations(rs):
        tmp = 0
        for i in range(len(perm) - 1):
            tmp += G[perm[i]][perm[i + 1]]
        ans = min(ans, tmp)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
from itertools import permutations as  P
from operator import itemgetter
from scipy.sparse.csgraph import floyd_warshall as wf

input = sys.stdin.readline

N, M, R = map(int, input().split())
r = list(map(int,input().split()))
edges = [list(map(int,input().split())) for _ in range(M)]
edges.sort(key=itemgetter(2),reverse=True)

G = np.full((N, N), np.inf)
for a, b, c in edges:
    G[a-1, b-1] = c
    G[b-1, a-1] = c
G = wf(G,directed=False)

def cost(G, path):
    ret = 0
    for i in range(len(path) - 1):
        ret += G[path[i] - 1, path[i + 1] - 1]
    return ret

ans = np.inf
for path in P(r):
    ans = min(ans, cost(G, path))

print(int(ans))

Submission status: Accepted

Solution code:
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
abcs = [list(map(int, input().split())) for i in range(M)]
INF = 10**9
dist_list = [[INF if i != j else 0 for j in range(N)] for i in range(N)]

# distance[i][j]で(i, j)間の最短の移動距離を保持
for abc in abcs:
    a = abc[0]-1
    b = abc[1]-1
    c = abc[2]
    if c < dist_list[a][b]:
        dist_list[a][b] = c
        dist_list[b][a] = c
# ワーシャルフロイド
for i in range(1, N):
    for j in range(N):
        for k in range(N):
            dist_list[j][k] = min(dist_list[j][k], dist_list[j][i] + dist_list[i][k])
            dist_list[k][j] = dist_list[j][k]

# 総当たり
result = []


def permutation(data, res):
    global result
    if len(data) == 0:
        result.append(res)
        return

    for i in data:
        _res = res[::]
        _res.append(i)
        _data = data[::]
        _data.remove(i)
        permutation(_data, _res)


permutation(r, [])
min_distance = INF
for res in result:
    distance = 0
    for i in range(1, len(res)):
        x = res[i]-1
        y = res[i-1]-1
        distance += dist_list[x][y]
    if distance < min_distance:
        min_distance = distance
print(min_distance)

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop
from collections import deque
from itertools import permutations
input = sys.stdin.readline

def dijkstra(N, start, adj_dict):
    distance = [float('inf')] * N
    distance[start] = 0
    priority_queue = []
    
    for i in range(N):
        heappush(priority_queue, (distance[i], i))
        
    while len(priority_queue) > 0:
        (current_dist, current_node) = heappop(priority_queue)
        if distance[current_node] < current_dist:
            continue
        for next_node, w in adj_dict[current_node]:
            if distance[next_node] >= distance[current_node] + w:
                distance[next_node] = distance[current_node] + w
                heappush(priority_queue, (distance[next_node], next_node))
    
    return distance

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
adj_dict = {i: deque([]) for i in range(N)}

for _ in range(M):
    a_i, b_i, c_i = map(int, input().split())
    adj_dict[a_i-1].append((b_i-1, c_i))
    adj_dict[b_i-1].append((a_i-1, c_i))

distance_map = [dijkstra(N, start, adj_dict) for start in range(N)]
ans = 1000000000

for route in permutations(r):
    ans_cand = 0
    
    for i in range(len(route)-1):
        ans_cand += distance_map[route[i]-1][route[i+1]-1]
    
    ans = min([ans, ans_cand])

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
N,M,R=map(int,input().split())
INF=10**9
d=[[INF]*N for i in range(N)]
r=list(map(int,input().split()))
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 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=10**9
for L in permutations(r):
  temp=0
  for j in range(R-1):
    temp+=d[L[j]-1][L[j+1]-1]
  ans=min(temp,ans)
print(ans)

Submission status: Accepted

Solution code:
#import time
#t = time.time()
inf = float('inf')

n, m, r = map(int, input().split())
rs = [r-1 for r in list(map(int, input().split()))]


ds = [[inf] * n for _ in range(n)]
for i in range(n):
  ds[i][i] = 0

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

## warshall floyd
for k in range(n):
  for i in range(n):
    for j in range(n):
      ds[i][j] = min(ds[i][j], ds[i][k] + ds[k][j])

#print(f'wf finished {time.time() - t}')
#t = time.time()

#def dfs(dist, before, remain, ds):
#  print(f'dfs({dist}, {before}, {remain})')
#  if remain == []:
#    return dist
#  dd = []
#  for r in remain:
#    if before is not None:
#      dist += ds[before][r]
#    dd.append(dfs(dist, r, list(set(remain) - set([r])), ds))
#  return min(dd)    
#
#print(dfs(0, None, rs, ds))


import itertools
dds = []
for i in itertools.permutations(rs, len(rs)):
  d = 0
  for j in range(len(rs)-1):
    dd = ds[i[j]][i[j+1]]
    d += dd
    #print(f'added {dd}')
  dds.append(d)
print(min(dds))

#print(f'search finished {time.time() - t}')
#t = time.time()

Submission status: Accepted

Solution code:
from collections import defaultdict
import itertools

def main():
    node_num, edge_num, visit_num = map(int, input().split())
    visit_place = list(map(int, input().split()))
    data = [list(map(int, input().split())) for i in range(edge_num)]

    hashi_set = defaultdict(set)
    kyori_data = [defaultdict(int) for i in range(node_num + 1)]

    saitan_data = [[10 ** 10 for i in range(node_num + 1)] for j in range(node_num + 1)]

    for i in range(edge_num):
        a, b, c = data[i]
        hashi_set[a].add(b)
        hashi_set[b].add(a)
        kyori_data[a][b] = c
        kyori_data[b][a] = c
        saitan_data[a][b] = c
        saitan_data[b][a] = c


    for k in range(1, node_num + 1):
        for i in range(1, node_num + 1):
            for j in range(1, node_num + 1):
                if i == j:
                    saitan_data[i][j] = 0
                    continue
                saitan_data[i][j] = min(saitan_data[i][j], saitan_data[i][k] + saitan_data[k][j])

    ans = 10 ** 10
    for ikikata in list(itertools.permutations(visit_place, visit_num)):
        kari = 0
        for i in range(visit_num - 1):
            kari += saitan_data[ikikata[i]][ikikata[i + 1]]
        if kari < ans:
            ans = kari
    print(ans)





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
N, M, R = map(int, input().split())

class Route:
    def __init__(self, B, C):
        self.next = points[B]
        self.distance = C
class Point:
    def __init__(self, id):
        self.id = id
        self.neighbors = []
        self.clear()
    def clear(self):
        self.distances = [-1] * 2
    def set(self, cur):
        self.distances[cur.srcid] = cur.distance
        return self.isWent(0) and self.isWent(1)
    def isWent(self, n):
        return self.distances[n] >= 0
    def addNeighbor(self, B, C):
        self.neighbors.append(Route(B, C))
    def optimize(self):
        self.neighbors = sorted(self.neighbors, key=lambda obj:obj.distance)

class MeetInfo:
    def __init__(self):
        self.clear()
    def clear(self):
        self.distance = -1
    def isMet(self):
        return self.distance >= 0

class Cursor:
    def __init__(self, ri, pt, meetinfo, dist=0):
        self.srcid = ri
        self.point = pt
        self.cur_route = 0
        self.distance = dist
        self.meetinfo = meetinfo
        if self.point.set(self):
            meetinfo.distance = self.point.distances[0] + self.point.distances[1]

    def cost(self):
        while self.cur_route < len(self.point.neighbors):
            rt = self.point.neighbors[self.cur_route]
            if not rt.next.isWent(self.srcid):
                break
            self.cur_route+= 1
        else:
            return None

        return self.distance + rt.distance

    def progress(self):
        nextrt = self.point.neighbors[self.cur_route]
        addcursor(Cursor(self.srcid, nextrt.next, self.meetinfo, self.distance + nextrt.distance))
        self.cur_route += 1
        addcursor(self)
    def __lt__(self, other):
        return True
points = [Point(i) for i in range(N+1)]

in_r = [ri for ri in map(int, input().split())]
for A, B, C in (map(int, input().split()) for _ in range(M)):
    points[A].addNeighbor(B, C)
    points[B].addNeighbor(A, C)

for x in points:
    x.optimize()

def addcursor(cur):
    c = cur.cost()
    if not c is None:
        heapq.heappush(hq, (c, cur))

def getRs(rs = None, cnt = -1, ret = None):
    if rs is None:
        rs = [False] * R
        ret = []
        cnt = R

    if cnt <= 0:
        yield ret
        return

    cnt -= 1

    for i in range(R):
        if not rs[i]:
            rs[i] = True
            ret.append(i)
            yield from getRs(rs, cnt, ret)
            ret.pop()
            rs[i] = False

Rmatrix = [[-1 for _ in range(R)] for _ in range(R) ]

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

        meetinfo = MeetInfo()
        for x in points:
            x.clear()
        rs = [Cursor(i, points[ri], meetinfo)  for i, ri in enumerate((in_r[i], in_r[j]))]
        hq = []
        addcursor(rs[0])

        while not meetinfo.isMet():
            cost, cursor = heapq.heappop(hq)
            cursor.progress()

        Rmatrix[i][j] = meetinfo.distance
        Rmatrix[j][i] = meetinfo.distance

M = 10 ** 9
for r in getRs():
    #print(r)
    w = 0
    for i in range(R-1):
        w += Rmatrix[r[i]][r[i+1]]    
    M = min(M, w)

print(M)

Submission status: Accepted

Solution code:
from itertools import permutations
from scipy.sparse.csgraph import dijkstra as di
N,M,R=map(int,input().split())
r=list(map(int,input().split()))
dp=[[0 for _ in range(N)] for _ in range(N)]
 
for _ in range(M):
  A,B,C=map(int,input().split())
  if dp[A-1][B-1]==0 or dp[A-1][B-1]>C:
    dp[A-1][B-1]=C
    dp[B-1][A-1]=C
distance=di(dp)
'''
def get_target_min_index(min_index, distance, unsearched_nodes):
    start = 0
    while True:
        index = distance.index(min_index, start)
        found = index in unsearched_nodes
        if found:
            return index
        else:
            start = index + 1
 
 
distance = [[100001]*N] * N # ノードごとの距離のリスト
 
 
for i in range(R):
  for j in range(i+1,R):
    dist=[100001]*N
    dist[r[i]]=0
    unsearched_nodes = list(range(N)) # 未探索ノード
    previous_nodes = [-1] * N # 最短経路でそのノードのひとつ前に到達するノードのリスト
    while(len(unsearched_nodes) != 0): #未探索ノードがなくなるまで繰り返す
    # まず未探索ノードのうちdistanceが最小のものを選択する
      posible_min_distance = 100001 # 最小のdistanceを見つけるための一時的なdistance。初期値は inf に設定。
      for node_index in unsearched_nodes: # 未探索のノードのループ
          if posible_min_distance > dist[node_index]: 
              posible_min_distance = dist[node_index] # より小さい値が見つかれば更新
      target_min_index = get_target_min_index(posible_min_distance, dist, unsearched_nodes) # 未探索ノードのうちで最小のindex番号を取得
      unsearched_nodes.remove(target_min_index) # ここで探索するので未探索リストから除去
 
      target_edge = dp[target_min_index] # ターゲットになるノードからのびるエッジのリスト
      for index, route_dis in enumerate(target_edge):
          if route_dis != 0:
              if dist[index] > (dist[ target_min_index] + route_dis):
                  dist[index] = dist[ target_min_index] + route_dis # 過去に設定されたdistanceよりも小さい場合はdistanceを更新
                  previous_nodes[index] =  target_min_index #　ひとつ前に到達するノードのリストも更新
    #print("-----経路-----")
    previous_node = r[j]
    while previous_node != -1:
      if previous_node !=i:
        #print(str(previous_node + 1) + " <- ", end='')
      else:
        #print(str(previous_node + 1))
      previous_node = previous_nodes[previous_node]
 
    #print("-----距離-----")
    #print(dist[j])
    distance[i][j]=dist[j]
    distance[j][i]=dist[j]
'''
 
ans=10**11
for tmp in permutations(r):
  tmpans=0
  for i in range(len(tmp)-1):
    tmpans+=distance[tmp[i]-1][tmp[i+1]-1]
  if ans>tmpans:
    ans=tmpans
print(int(ans))

Submission status: Accepted

Solution code:
n,m,rrr = map(int,input().split())
R = tuple(map(int,input().split()))
ABC = [list(map(int,input().split())) for _ in range(m)]
inf = 1000000000

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

for a,b,c in ABC:
    edge[a][b] = c
    edge[b][a] = c
    
def dijkstra(start,e,N):
    for _ in range(3):
        for v in range(1,N+1):#中間
            for g in range(1,N+1):#ゴール
                e[start][g] = min(e[start][g],e[start][v] + e[v][g])
                e[g][start] = e[start][g]
    return e[start]

dic = {}
for rr in R:
    dic[rr] = dijkstra(rr,edge,n)

from itertools import permutations as pm

temp = list(pm(R))

ans = 10000000000
for RR in temp:
    cost = 0
    for i in range(rrr-1):
        cost += dic[RR[i]][RR[i+1]]
    if cost < ans:
        ans = cost
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import permutations
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
MOD = 1000000007
def POW(x, y): return pow(x, y, MOD)
def INV(x, m=MOD): return pow(x, m - 2, m)
def DIV(x, y, m=MOD): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LLI(n): return [[int(x) for x in input().split()] for _ in range(n)]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


N,M,R = LI()
RS=LI()
mp = [[10**10]*(N+1) for _ in range(N+1)]
for a,b,c in LLI(M):
    mp[a][b] = c
    mp[b][a] = c

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

res = INTMAX
for l in permutations(RS):
    sc = 0
    for i in range(R-1): 
        sc += mp[l[i]][l[i+1]]
    res = min(res,sc)
print(res)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from itertools import permutations
 
def warshall_floyd(conn):
    n = len(conn)
    dp = [[v for v in A] for A in conn]
    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])
    return dp
 
 
def solve(N: int, M: int, R: int, r: "List[int]", A: "List[int]", B: "List[int]", C: "List[int]"):
    conn = [[float('inf') for _ in range(N)] for _ in range(N)]
    for i in range(N):
        conn[i][i] = 0
    for j in range(M):
        a = A[j] - 1
        b = B[j] - 1
        conn[a][b] = min(conn[a][b], C[j])
        conn[b][a] = min(conn[b][a], C[j])
    dp = warshall_floyd(conn)
    #print(dp)
    ret = float('inf')
    perms = list(permutations(list(range(R))))
    for order in perms:
        tmp = 0
        for i in range(R - 1):
            s = r[order[i]] - 1
            t = r[order[i + 1]] - 1
            #print(r[s], r[t], dp[s][t])
            tmp += dp[s][t]
        ret = min(ret, tmp)
    print(ret)
    return
 
 
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    R = int(next(tokens))  # type: int
    r = [ int(next(tokens)) for _ in range(R) ]  # type: "List[int]"
    A = [int()] * (M)  # type: "List[int]" 
    B = [int()] * (M)  # type: "List[int]" 
    C = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    solve(N, M, R, r, A, B, C)
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
from collections import deque
from functools import reduce
from pprint import pprint
import itertools
import bisect
import copy
import fractions
import math
import random
import sys
import time
import queue
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers): return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers): return reduce(LCM, numbers)
def LCM(m, n): return (m * n // fractions.gcd(m, n))
def warshall_floyd(n):
    # 隣接行列graphを使う
    for i in range(n):  # 経由する頂点
        for j in range(n):  # 開始頂点
            for k in range(n):  # 終端
                graph[j][k] = min(graph[j][k], graph[j][i] + graph[i][k])


N, M, R = MI()
r = LI()
road = [LI() for _ in range(M)]
graph = [[INF] * N for _ in range(N)]
# pprint(graph, width=30)
distance = [[INF] * N for _ in range(N)]
for a, b, c in road:
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c
for i in range(N):
    graph[i][i] = 0

q = queue.PriorityQueue()

# distance = [INF] * N
# while not q.empty():
#     cost, v = q.get()
#     if distance[v] < cost:
#         continue
#     distance[v] = cost
# 
#     for next_v in range(N):
#         if graph[v][next_v] == 0:  # 繋がっていない
#             continue
#         q.put((distance[v] + graph[v][next_v], next_v))

# for begin in range(N):
for begin in r:
    begin -= 1
    q.put((0, begin))  # begin~beginのコストは0, begin番目の頂点始点
    while not q.empty():
        cost, v = q.get()
        if distance[begin][v] < cost:
            continue
        distance[begin][v] = cost

        for next_v in range(N):
            if graph[v][next_v] == 0:
                continue
            q.put((distance[begin][v] + graph[v][next_v], next_v))

mini = INF
for permutation in itertools.permutations(r):
    tmp = 0
    # print(permutation)
    for i in range(R-1):
        tmp += distance[permutation[i]-1][permutation[i+1]-1]
    mini = min(mini, tmp)

print(mini)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import dijkstra as di
from itertools import permutations
N,M,R = map(int, input().split())
r = list(map(int, input().split()))

route = [[0 for i in range(N)] for j in range(N)]
for i in range(M):
    a,b,c = map(int, input().split())
    route[a-1][b-1] = route[b-1][a-1] = c
# for i in range(N):
#     print(route[i])


p_route = di(route)
# print(p_route)

mn = float('INF')
for tmp in permutations(r):
    t_sum = 0
    for i in range(len(tmp)-1):
        t_sum += p_route[tmp[i]-1][tmp[i+1]-1]
    if t_sum < mn:
        mn = t_sum

print(int(mn))

Submission status: Accepted

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

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


graph = [[float('inf') for i in range(n)] for i in range(n)]

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

tip_graph = floyd_warshall(csgraph = graph, directed = False, return_predecessors = False)

ans = 10 ** 9
tmp = 0

for i in list(itertools.permutations(v,r)):
    tmp = 0
    for j in range(r-1):
        tmp += tip_graph[i[j]][i[j+1]]
    ans = min(ans, tmp)
print(int(ans))

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [input() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    from itertools import permutations
    N, M, R = MI()
    r = LI_()
    d=[[float("inf")] * N for i in range(N)]
    for i in range(N):
        d[i][i]=0
    for _ in range(M):
        a, b, c = MI_()
        c += 1
        d[a][b] = c
        d[b][a] = c
    def warshall_floyd(d, N):
        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])


    warshall_floyd(d, N)

    ans=inf
    for p in permutations(r):
        prev = p[0]
        cost = 0
        for to in p[1:]:
            cost += d[prev][to]
            prev = to
        ans=min(cost,ans)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#from numpy import*
#from scipy import*
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby
from operator import mul
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial
from copy import deepcopy
import sys
from scipy.sparse.csgraph import floyd_warshall

#input=sys.stdin.readline  #危険！基本オフにしろ！
sys.setrecursionlimit(10**6)


def main():
    n,m,r=map(int,input().split())
    grid=[[0]*n for i in range(n)]
    *R,=map(int,input().split())
    for i in range(m):
        a,b,c=map(int,input().split())
        grid[a-1][b-1]=c
        grid[b-1][a-1]=c
#    print(grid)
    d,p=floyd_warshall(csgraph=grid, directed=False, return_predecessors=True)
#    print(p)
#    print(d)
    print(int(min(sum(d[i[j]-1][i[j+1]-1]for j in range(len(i)-1))for i in permutations(R))))
    
if __name__ == '__main__':
    main()