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

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

# pprint(graph, width=30)
warshall_floyd(N)
# pprint(graph, width=30)

# for i in range(N):
#     for j in range(N):
#         if i != j and graph[i][j] != INF:
#             # i == jの場合は始点と終点が同じ
#             # INFはそもそも繋がっていない
#             print(str(i+1)+' ~ '+str(j+1)+' ===== '+str(graph[i][j]))

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

Submission status: Accepted

Solution code:
#coding:utf-8
import itertools

N,M,R=map(int,raw_input().split())
R=map(int,raw_input().split())
D=[[1145141919810]*300 for _ in range(300)]
for i in range(M):
    a,b,c=map(int,raw_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):
            if D[i][j]>D[i][k]+D[k][j]:
                D[i][j]=D[i][k]+D[k][j]
ans=1145141919810
for P in itertools.permutations(R):
    s=P[0]
    l=0
    for t in P[1:]:
       l+=D[s][t]
       s=t
    ans=min(ans,l)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations


def warshall_floyd(v_count: int, matrix: list) -> list:
    """ ワーシャルフロイド
    v_count: 頂点数
    matrix: 隣接行列(到達不能はfloat("inf"))
    """
    for i in range(v_count):
        for j, c2 in enumerate(row[i] for row in matrix):
            for k, (c1, c3) in enumerate(zip(matrix[j], matrix[i])):
                if c1 > c2+c3:
                    matrix[j][k] = c2+c3
    return matrix


INF = 10 ** 9
N, M, R = map(int, input().split())
m = [[INF for i in range(N)] for j in range(N)]
for i in range(N):
    m[i][i] = 0
r = list(map(lambda x: int(x) - 1, input().split()))
for i in range(M):
    a, b, c = map(int, input().split())
    m[a - 1][b - 1] = c
    m[b - 1][a - 1] = c
m = warshall_floyd(N, m)
ans = INF
for path in permutations(r, R):
    tmp = 0
    for i in range(len(path) - 1):
        tmp += m[path[i + 1]][path[i]]
    ans = min(ans, tmp)
print(ans)

Submission status: Accepted

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

r = list(map(int,input().split()))
e_list = [[] for i in range(N)]
for i in range(M):
    a,b,c = list(map(int,input().split()))
    a=a-1
    b=b-1
    e_list[a].append([b,c])
    e_list[b].append([a,c])

#dijkstra
#you need to prepare e_list = [[orient,dist]]

import heapq
r_dis_list = []
for i in range(len(r)):
    vi = r[i]-1
    min_d_list = [10**27 for i in range(N)]
    min_d_list[vi] = 0
    prev_list = [-1 for i in range(N)]
    q = []
    for i in range(N):
        heapq.heappush(q,[min_d_list[i],i])

    while len(q)>0:
        d,v = heapq.heappop(q)
        for e in e_list[v]:
            v1,d1=e
            if min_d_list[v1]>d+d1:
                min_d_list[v1]=d+d1
                prev_list[v1]=v
                heapq.heappush(q,[d+d1,v1])

    r_dis_list.append([min_d_list[r[i]-1] for i in range(len(r))])

import itertools
min_ans = 10**27
for i in itertools.permutations(range(len(r))):
    ans = 0
    for j in range(len(r)-1):
        ans+=r_dis_list[i[j+1]][i[j]]
    min_ans=min(ans,min_ans)

print(min_ans)

Submission status: Accepted

Solution code:
import heapq
import itertools
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

N, M, _ = list(map(int, sys.stdin.readline().split()))
R = list(map(int, sys.stdin.readline().split()))
A, B, C = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(M)]))


def dijkstra(graph, start):
    """
    マイナスの辺があっちゃダメ
    scipy.sparse.csgraph.dijkstra は内部で使われてるフィボナッチヒープが一部のケースでめっちゃ遅いのであんまり使わないほうがよさげ
    https://atcoder.jp/contests/soundhound2018-summer-qual/submissions/5311823

    :param list of (list of (int, int)) graph:
        graph[from_index]: (to_index, weight)
    :param int start:
    :return:
    """
    dist = [float('inf') for _ in range(len(graph))]
    dist[start] = 0
    heap = []
    heapq.heappush(heap, (0, start))

    while len(heap) > 0:
        w, v = heapq.heappop(heap)
        if w > dist[v]:
            continue
        for u, dw in graph[v]:
            if w + dw < dist[u]:
                dist[u] = w + dw
                heapq.heappush(heap, (w + dw, u))
    return dist


#: :type: list of (list of (int, int))
graph = [[] for _ in range(N + 1)]
for a, b, c in zip(A, B, C):
    graph[a].append((b, c))
    graph[b].append((a, c))

dists = []
for r in R:
    dists.append(dijkstra(graph, r))

ans = INF
for indices in itertools.permutations(range(len(R))):
    s = 0
    for i, j in zip(indices[:-1], indices[1:]):
        s += dists[i][R[j]]
    ans = min(ans, s)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
from heapq import *

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())
    A,B=A-1,B-1
    G[A][B]=C
    G[B][A]=C
def distance(a,b):
    stack=[(G[a][i],i) for i in range(N) if G[a][i]!=INF]
    heapify(stack)
    reached=[0]*N
    reached[0]=1
    dis=[INF]*N
    dis[0]=0
    while(stack):
        c,i=heappop(stack)
        if reached[i]==1:
            continue
        if dis[i]<=c:
            continue
        dis[i]=c
        if i==b:
            return c
        reached[i]=1
        for j in range(N):
            if G[i][j]!=INF and reached[j]==0:
                heappush(stack,(G[i][j]+dis[i],j))
D=[[0]*N for i in range(N)]
for i in r:
    for j in r:
        if i>=j:
            continue
        D[i-1][j-1]=distance(i-1,j-1)
        D[j-1][i-1]=D[i-1][j-1]
ans=10**9
for r_ in permutations(r):
    res=0
    for i in range(R-1):
        res+=D[r_[i]-1][r_[i+1]-1]
    ans=min(ans,res)
print(ans)

Submission status: Accepted

Solution code:
N,M,R=map(int, input().split())
r=list(map(int, input().split()))
ABC=[list(map(int,input().split())) for i in range(M)]
c=[[10**9]*N for i in range(N)]
for i,j,w in ABC:
    c[i-1][j-1]=w
    c[j-1][i-1]=w
mat=[]
for start in r:
    start-=1
    d=[10**9]*N
    d[start]=0
    prev=[-1]*N
    from heapq import heappop,heappush
    q=[]
    heappush(q,(0,start))
    while len(q)>0:
        u=heappop(q)[1]
        for v in range(N):
            if c[u][v]<10**9:
                temp=d[u]+c[u][v]
                if d[v]>temp:
                    d[v]=temp
                    prev[v]=u
                    heappush(q,(d[v],v))
    m=[]
    for i in range(R):
        m.append(d[r[i]-1])
    mat.append(m)
from itertools import permutations
ans=10**9
for i in permutations(range(R),R):
    a=0
    for j in range(R-1):
        a+=mat[i[j]][i[j+1]]
    ans=min(ans,a)
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools

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

d=[  [ float("inf") for j in range(N+1) ]  for i in range(N+1) ]

r=map(int, sys.stdin.readline().split())

for _ in range(M):
	a,b,c=map(int, sys.stdin.readline().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])


C=list(itertools.permutations(r))


ans=float("inf")
for x in C:
	tmp_ans=0
	for i in range(R-1):
		fro=x[i]
		to=x[i+1]
		tmp_ans+=d[fro][to]
	ans=min(ans, tmp_ans)

print ans

Submission status: Accepted

Solution code:
import sys
import itertools

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

d=[  [ float("inf") for j in range(N+1) ]  for i in range(N+1) ]

r=map(int, sys.stdin.readline().split())

for _ in range(M):
	a,b,c=map(int, sys.stdin.readline().split())
	d[a][b]=c
	d[b][a]=c


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


C=list(itertools.permutations(r))


ans=float("inf")
for x in C:
	tmp_ans=0
	for i in range(R-1):
		fro=x[i]
		to=x[i+1]
		tmp_ans+=d[fro][to]
	ans=min(ans, tmp_ans)

print ans

Submission status: Accepted

Solution code:
import sys
import itertools

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

d=[  [ float("inf") for j in range(N+1) ]  for i in range(N+1) ]
for i in range(N+1):
	d[i][i]=0

r=map(int, sys.stdin.readline().split())

for _ in range(M):
	a,b,c=map(int, sys.stdin.readline().split())
	d[a][b]=c
	d[b][a]=c


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

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


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


C=list(itertools.permutations(r))


ans=float("inf")
for x in C:
	tmp_ans=0
	for i in range(R-1):
		fro=x[i]
		to=x[i+1]
		tmp_ans+=d[fro][to]
	ans=min(ans, tmp_ans)

print ans

Submission status: Accepted

Solution code:
import itertools
def w_f(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])
    return d

n, m, r = map(int,input().split())
LR = map(int,input().split())
d = [[float("inf") for i in range(n)] for i in range(n)]
for i in range(m):
    x,y,z = map(int,input().split())
    d[x-1][y-1] = z
    d[y-1][x-1] = z
for i in range(n):
    d[i][i] = 0 

D = w_f(d)
lr = list(itertools.permutations(LR))
ans = float("inf")
for li in lr:
    jd = 0
    for i in range(r-1):
        jd += D[li[i]-1][li[i+1]-1]
    
    if jd < ans:
        ans = jd
print(ans)

Submission status: Accepted

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

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

# 任意の2地点間の距離を求める
edge = np.zeros((N+1,N+1))
for _ in range(M):
  A,B,C = map(int,input().split())
  edge[A,B] = C
  
dist = shortest_path(edge, directed = False).astype(int)

# 全訪問順を試す。8! = 40320なので十分
answer = 10**18
for visit in itertools.permutations(r):
  p = 0
  prev = visit[0]
  for x in visit[1:]:
    if prev != None:
      p += dist[prev,x]
    prev = x
  answer = min(answer,p)
  
print(answer)

Submission status: Accepted

Solution code:
n,m,r = map(int,input().split())
r = list(map(int,input().split()))
node = [list(map(int,input().split())) for _ in range(m)]
dp = [[float('inf')]*(n+1) for _ in range(n+1)]
for x,y,z in node:
    dp[x][y] = z
    dp[y][x] = z
for i in range(n+1):
    dp[i][i] = 0
def wf(d,n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j]>d[i][k]+d[k][j]:
                    d[i][j] = d[i][k]+d[k][j]
    return d
dp = wf(dp,n+1)
import copy
import sys
rest = set(r[:])
def dfs(cost,pre,rest):
    if 0==len(rest):
        return cost
    ret = sys.maxsize
    for i in rest:
        if pre==None:
            next_cost = 0
        else:
            next_cost = cost + dp[pre][i]
        next_rest = copy.copy(rest)
        next_rest.remove(i)
        tmp_ret = dfs(next_cost, i, next_rest)
        ret = min(ret,tmp_ret)
    return ret
print(dfs(0,None,rest))

Submission status: Accepted

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

n,m,l=map(int,input().split())
arr=list(map(int,input().split()))
d=[[10**10 for i in range(n)] for j in range(n)]
for i in range(m):
  u,v,w=map(int,input().split())
  d[u-1][v-1]=w
  d[v-1][u-1]=w
for i in range(n):
  d[i][i]=0
d=floyd_warshall(d,directed=False)
c=list(itertools.permutations(arr,min(8,l)))
ans=10**10
for i in c:
  tmp=0
  for j in range(min(8,l)-1):
    tmp+=d[i[j]-1][i[j+1]-1]
  ans=min(tmp,ans)
print(int(ans))

Submission status: Accepted

Solution code:
N,M,R = [ int(it) for it in input().split() ]
ri = [ int(it) for it in input().split() ]
edge = [ [ int(it) for it in input().split() ]  for i in range(M) ]

li = [ [10000000]*N for i in range(N) ]
for a,b,c in edge:
  li[a-1][b-1]=c
  li[b-1][a-1]=c

for p in range(10000):
  Flag = True
  for i in range(N):
    for j in range(N):
      for k in range(N):
        li_ikj =  li[i][k]+li[k][j]
        if ( li[i][j] > li_ikj ):
          Flag = False
          li[i][j] = li_ikj
  if Flag:
    break

import itertools as ite
ms = 100000000000000000000000000000000000
for route in ite.permutations( ri ):
  s = 0
  for i in range( len(route)-1 ):
    s += li[route[i]-1][route[i+1]-1]
  ms = min(s,ms)
print ( ms )

Submission status: Accepted

Solution code:
N, M, R = map(int, input().split())
R_LIST = list(map(int, input().split()))
ABC = []
for _ in range(M):
    a,b,c = map(int, input().split())
    ABC.append((a,b,c))
    

    
edges = ABC[:]


def warshall_floyd(d, n):
    # d: グラフ二次元リスト
    # n: 頂点数 (0始まり)
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
                
    return d

# グラフ無効グラフ化
graph = [[float("inf") for i in range(N+1)] for i in range(N+1)] 
for x,y,z in edges:
    graph[x][y] = z
    graph[y][x] = z
for i in range(N+1):
    graph[i][i] = 0 #自身のところに行くコストは０

#最短経路
shortest =  warshall_floyd(graph, N+1)
    
# 順列全探索
import sys
INT_MAX = sys.maxsize # 9223372036854775807
ans = INT_MAX

import queue

rest = set(R_LIST[:])

import copy  
def dfs(cost,pre,rest):
    if len(rest) == 0:
        return cost
    
    ret = INT_MAX
    for r in rest:
        if pre == None:
            next_cost = 0
        else:
            next_cost = cost + shortest[pre][r]
        next_rest = copy.copy(rest)
        next_rest.remove(r)
        
        tmp_ret = dfs(next_cost, r, next_rest)
        ret = min(ret, tmp_ret)
        
    return ret
        
    

print(dfs(0, None, rest))

Submission status: Accepted

Solution code:
N, M, R = map(int, input().split())
R_LIST = list(map(int, input().split()))
ABC = []
for _ in range(M):
    a,b,c = map(int, input().split())
    ABC.append((a,b,c))
    

    
edges = ABC[:]


def warshall_floyd(d, n):
    # d: グラフ二次元リスト
    # n: 頂点数 (0始まり)
    #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

# グラフ無効グラフ化
graph = [[float("inf") for i in range(N+1)] for i in range(N+1)] 
for x,y,z in edges:
    graph[x][y] = z
    graph[y][x] = z
for i in range(N+1):
    graph[i][i] = 0 #自身のところに行くコストは０

#最短経路
shortest =  warshall_floyd(graph, N+1)
    
# 順列全探索
import sys
INT_MAX = sys.maxsize # 9223372036854775807
ans = INT_MAX

import queue

rest = set(R_LIST[:])

import copy  
def dfs(cost,pre,rest):
    if len(rest) == 0:
        return cost
    
    ret = INT_MAX
    for r in rest:
        if pre == None:
            next_cost = 0
        else:
            next_cost = cost + shortest[pre][r]
        next_rest = copy.copy(rest)
        next_rest.remove(r)
        
        tmp_ret = dfs(next_cost, r, next_rest)
        ret = min(ret, tmp_ret)
        
    return ret
        
    

print(dfs(0, None, rest))

Submission status: Accepted

Solution code:
from itertools import permutations
from scipy.sparse.csgraph import floyd_warshall
n,m,r=map(int,input().split())
*R,=map(int,input().split())
table=[[0]*n for i in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    table[a-1][b-1]=c
    table[b-1][a-1]=c
d=floyd_warshall(csgraph=table, directed=False, return_predecessors=False)
cost=[sum(d[i[j]-1][i[j+1]-1]for j in range(r-1))for i in permutations(R)]
print(int(min(cost)))

Submission status: Accepted

Solution code:
import itertools

n,m,r = map(int, input().split())
v = list(map(int, input().split()))

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

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

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

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 range(r):
    v[i]-=1

s = list(itertools.permutations(v))

for i in range(len(s)):
    a = 0
    for j in range(r-1):
        a += l[s[i][j]][s[i][j+1]]
    ans = min(ans, a)

print(ans)

Submission status: Accepted

Solution code:
INF = float('inf')

N,M,RR = map(int,input().split(" "))
R = list(map(lambda x:int(x)-1,input().split(" ")))
G = [[] for i in range(N)]
sq = [[0 for x in range(RR)] for y in range(RR)]
for i in range(M):
    a,b,c = map(int,input().split(" "))
    a -= 1
    b -= 1
    G[a].append((b,c))
    G[b].append((a,c))

for i in range(RR):
    E = [INF]*N
    F = [1]*N
    E[R[i]] = 0
    F[R[i]] = 0
    q = R[i]
    c = 1
    while c != N:
        for a,b in G[q]:
            if F[a]:
                E[a] = min(E[a],E[q] + b)
        a = [x for x in range(N) if F[x]]
        q = min(a,key=lambda x:E[x])
        F[q] = 0
        c += 1
    for j in range(RR):
        sq[i][j] = E[R[j]]

q = [[[],0,0]]
s = []
while len(q):
    a,b,c = q.pop()
    if b == RR:
        s.append(c)
        continue
    for i in range(RR):
        if i in a:
            continue
        d = c
        d += b and sq[a[-1]][i]
        q.append([a+[i],b+1,d])

print(min(s))

Submission status: Accepted

Solution code:
INF = float('inf')

N,M,RR = map(int,input().split(" "))
R = list(map(lambda x:int(x)-1,input().split(" ")))
G = [[] for i in range(N)]
sq = [[(x==y)-1 for x in range(RR)] for y in range(RR)]
for i in range(M):
    a,b,c = map(int,input().split(" "))
    a -= 1
    b -= 1
    G[a].append((b,c))
    G[b].append((a,c))

for i in range(RR):
    E = [INF]*N
    F = [1]*N
    E[R[i]] = 0
    F[R[i]] = 0
    q = R[i]
    c = 1
    while c != N:
        for a,b in G[q]:
            if F[a]:
                E[a] = min(E[a],E[q] + b)
        a = [x for x in range(N) if F[x]]
        q = min(a,key=lambda x:E[x])
        F[q] = 0
        c += 1
    for j in range(RR):
        sq[i][j] = E[R[j]]

q = [[[],0,0]]
s = []
while len(q):
    a,b,c = q.pop()
    if b == RR:
        s.append(c)
        continue
    for i in range(RR):
        if i in a:
            continue
        d = c
        d += b and sq[a[-1]][i]
        q.append([a+[i],b+1,d])

print(min(s))

Submission status: Accepted

Solution code:
INF = float('inf')

N,M,RR = map(int,input().split(" "))
R = list(map(lambda x:int(x)-1,input().split(" ")))
G = [[] for i in range(N)]
sq = [[(x==y)-1 for x in range(RR)] for y in range(RR)]
for i in range(M):
    a,b,c = map(int,input().split(" "))
    a -= 1
    b -= 1
    G[a].append((b,c))
    G[b].append((a,c))

for i in range(RR):
    E = [INF for x in range(N)]
    F = [0 for x in range(N)]
    E[R[i]] = 0
    F[R[i]] = 1
    q = R[i]
    c = 1
    while c != N:
        for a,b in G[q]:
            if F[a]:
                continue
            if E[a] == -1:
                E[a] = E[q] + b
            else:
                E[a] = min(E[a],E[q] + b)
        a = [x for x in range(N) if not(F[x]) and E[x] != -1]
        q = min(a,key=lambda x:E[x])
        F[q] = 1
        c += 1
    for j in range(RR):
        sq[i][j] = E[R[j]]

q = [[[],0,0]]
s = []
while len(q):
    a,b,c = q.pop()
    if b == RR:
        s.append(c)
        continue
    for i in range(RR):
        if i in a:
            continue
        if b == 0:
            q.append([a+[i],b+1,0])
        else:
            q.append([a+[i],b+1,c+sq[a[-1]][i]])

print(min(s))

Submission status: Accepted

Solution code:
N,M,RR = map(int,input().split(" "))
R = list(map(lambda x:int(x)-1,input().split(" ")))
G = [[] for i in range(N)]
sq = [[(x==y)-1 for x in range(RR)] for y in range(RR)]
for i in range(M):
    a,b,c = map(int,input().split(" "))
    a -= 1
    b -= 1
    G[a].append((b,c))
    G[b].append((a,c))

for i in range(RR):
    E = [-1 for x in range(N)]
    F = [0 for x in range(N)]
    E[R[i]] = 0
    F[R[i]] = 1
    q = R[i]
    c = 1
    while c != N:
        for a,b in G[q]:
            if F[a]:
                continue
            if E[a] == -1:
                E[a] = E[q] + b
            else:
                E[a] = min(E[a],E[q] + b)
        a = [x for x in range(N) if not(F[x]) and E[x] != -1]
        q = min(a,key=lambda x:E[x])
        F[q] = 1
        c += 1
    for j in range(RR):
        sq[i][j] = E[R[j]]

q = [[[],0,0]]
s = []
while len(q):
    a,b,c = q.pop()
    if b == RR:
        s.append(c)
        continue
    for i in range(RR):
        if i in a:
            continue
        if b == 0:
            q.append([a+[i],b+1,0])
        else:
            q.append([a+[i],b+1,c+sq[a[-1]][i]])

print(min(s))

Submission status: Accepted

Solution code:
from itertools import permutations

N, M, R = (int(i) for i in input().split())
#print(N, M, R)

r=[int(i) for i in input().split()]
#print(r)

dist=[[float('inf') for i in range(201)] for j in range(201)]
for i in range(201):
    dist[i][i] = 0

for i in range(M):
  a,b,c=(int(i) for i in input().split())
  dist[a][b]=c
  dist[b][a]=c

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

dict0=float('inf')
mylist=list(permutations(r,len(r)))
#print(mylist)

for i in mylist:
  tmp=0
  for j in range(len(i)-1):
    tmp+=dist[i[j]][i[j+1]]
  if tmp < dict0:
    dict0=tmp

print(dict0)

Submission status: Accepted

Solution code:
from itertools import permutations

N, M, R = (int(i) for i in input().split())
#print(N, M, R)

r=[int(i) for i in input().split()]
#print(r)

dist=[[float('inf') for i in range(201)] for j in range(201)]
for i in range(201):
    dist[i][i] = 0

for i in range(M):
  a,b,c=(int(i) for i in input().split())
  dist[a][b]=c
  dist[b][a]=c

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

dict0=float('inf')
mylist=list(permutations(r,len(r)))
#print(mylist)

for i in range(len(mylist)):
    tmp=0
    for j in range(len(mylist[i])-1):
        x=mylist[i][j]
        y=mylist[i][j+1]
        tmp+=dist[x][y]
    if tmp < dict0:
      dict0=tmp

print(dict0)

Submission status: Accepted

Solution code:
import heapq

N,M,R = map(int,input().split())
r = list(map(int,input().split()))
r = [a-1 for a in r]
paper = set()
T = [[] for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    T[a].append((c,b))
    T[b].append((c,a))

inf = 1 << 60
memo = {}
def distance(a,b):
    #print('distance(',a,',',b,') =?')
    if (a,b) in memo.keys():
        #print('distance(',a,',',b,') =',memo[(a,b)])
        return memo[(a,b)]
    d = [inf] * N
    d[a] = 0
    q = []
    heapq.heappush(q, (0,a))
    try:
        while True:
            c, t = heapq.heappop(q)
            if t == b:
                memo[(a,b)] = c
                memo[(b,a)] = c
                #print('distance(',a,',',b,') =',c)
                return c
            for i in T[t]:
                if d[i[1]] > c + i[0]:
                    d[i[1]] = c + i[0]
                    heapq.heappush(q, (c + i[0], i[1]))

    except IndexError:
        pass

arrived = [False] * R
ans = inf

def calc(src, rest, total):
    global ans
    if total >= ans:
        return
    if rest == 0:
        ans = min(ans,total)
        return

    for i in range(R):
        if not arrived[i]:
            arrived[i] = True
            calc(r[i], rest-1, total + distance(src,r[i]))
            arrived[i] = False

for i in range(R):
    arrived[i] = True
    calc(r[i], R-1, 0)
    arrived[i] = False

print(ans)

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import itertools
from scipy.sparse import csr_matrix, coo_matrix
from scipy.sparse.csgraph import dijkstra, bellman_ford
#sys.setrecursionlimit(10000)

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

rows = []
cols = []
weights = []

for _ in range(M):
    # u v 間のコスト
    u, v, a = [int(i) for i in input().split()]
    rows.append(u-1)
    cols.append(v-1)
    weights.append(a)

graph = coo_matrix((weights, (rows, cols)), shape=(N, N)).tocsr()
d1 = dijkstra(graph, directed=False, unweighted=False)

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

print(int(ans))

Submission status: Accepted

Solution code:
import itertools as o,scipy.sparse as s;_,r,*t=[map(int,i.split())for i in open(0)];a,b,c=zip(*t);l=s.csgraph.dijkstra(s.csr_matrix((c,(a,b)),[201]*2),0);print(min(sum(int(l[i][j])for i,j in zip(a,a[1:]))for a in o.permutations(r)))

Submission status: Accepted

Solution code:
from itertools import*
from scipy.sparse.csgraph import floyd_warshall
n,m,r=map(int,input().split())
*R,=map(int,input().split())

table=[[0]*n for i in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    table[a-1][b-1]=c
    table[b-1][a-1]=c
d,p=floyd_warshall(csgraph=table, directed=False, return_predecessors=True)
cost=[sum(d[i[j]-1][i[j+1]-1]for j in range(r-1))for i in permutations(R)]
print(int(min(cost)))

Submission status: Accepted

Solution code:
from itertools import product, permutations

INF=1145141919810

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

road=[[0 if x==y else INF for y in range(N+1)] for x in range(N+1)]

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

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

print(min(sum(road[p[i-1]][p[i]] for i in range(1, R)) for p in permutations(r)))

Submission status: Accepted

Solution code:
from itertools import product, permutations

INF=1145141919810

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

road=[[0 if x==y else INF for y in range(N+1)] for x in range(N+1)]

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

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

print(min(sum(road[p[i-1]][p[i]] for i in range(1, R)) for p in permutations(r)))

Submission status: Accepted

Solution code:
from itertools import permutations
n,m,rl=map(int,input().split());r=list(map(int,input().split()))
d=[[float("inf")for _ in range(n)]for _ in range(n)]
for i in range(m):
  x,y,z=map(int,input().split())
  d[x-1][y-1],d[y-1][x-1]=z,z
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])
a=float("inf")
for i in permutations(r,rl):
  aa=0
  for j in range(rl-1):aa+=d[i[j]-1][i[j+1]-1]
  a=min(a,aa)
print(a)

Submission status: Accepted

Solution code:
import itertools

N,M,R = map(int,input().split())
r = list(map(lambda x:int(x)-1,input().split()))
ABC = [list(map(int,input().split())) for _ in range(M)]
INF = 10**7
d = [[INF]*N for _ in range(N)]

for A,B,C in ABC:
    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(i+1,N):
            d[i][j] = min(d[i][j],d[i][k]+d[k][j])
            d[j][i] = d[i][j]
ans = INF * M
for r in itertools.permutations(r):
    S = 0
    for i,ri in enumerate(r[:-1]):
        S += d[ri][r[i+1]]
    ans = min(ans,S)
print(ans)

Submission status: Accepted

Solution code:
class WarshallFloyd():
    def __init__(self, N):
        self.N = N
        self.d = [[float("inf") for i in range(N)]
                  for i in range(N)]  # d[u][v] : 辺uvのコスト(存在しないときはinf)

    def add(self, u, v, c, directed=False):
        """
        0-indexedであるに注意
        u = from, v = to, c = cost
        directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.d[u][v] = c
            self.d[v][u] = c
        else:
            self.d[u][v] = c

    def WarshallFloyd_search(self):
        # これを d[i][j]: iからjへの最短距離 にする
        # TODO verify both in directed and non-directed
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    self.d[i][j] = min(
                        self.d[i][j], self.d[i][k] + self.d[k][j])
        for i in range(self.N):
            self.d[i][i] = 0
        return self.d


import itertools

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
graph = WarshallFloyd(N)
for i in range(M):
    a, b, c = map(int, input().split())
    graph.add(a-1, b-1, c)

d = graph.WarshallFloyd_search()
ans = float('inf')
for each in itertools.permutations(r):
    cur = 0
    for i in range(R - 1):
        cur += d[each[i] - 1][each[i + 1] - 1]
    ans = min(ans, cur)

print(ans)