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:
def main():
    from sys import stdin
    input = stdin.readline

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

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

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

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

    print(answer)

main()

Submission status: Accepted

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

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

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

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

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

    print(answer)

main()

Submission status: Accepted

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

N,M,R=list(map(int,input().split()))
r=list(map(int,input().split()))
ABC = [[float('inf')]*(N+1) for _ in range(N+1)]
#条件のうち、重複経路は最短のみ残す
for _ in range(M):
    a,b,c = map(int,input().split())
    if ABC[a][b]>c:
        ABC[a][b]=c
        ABC[b][a]=c

#各頂点間の最小距離 Warshall-Floyd
dist = [[float('inf')]*(N+1) for _ in range(N+1)]
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            ABC[i][j] = min(ABC[i][j],ABC[i][k] + ABC[k][j])

rotate = itertools.permutations(r)
ans = float('inf')
for rot in rotate:
    tmp = 0
    flag = 0
    for i in range(len(rot)-1):
        tmp +=ABC[rot[i]][rot[i+1]]
        if tmp>ans:
            flag = 1
            break
    if flag==0:
        ans = min(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

def main():
    import heapq
    import itertools

    def dijkstra(s, n):
        hq = [(0, s)]
        heapq.heapify(hq)  # リストを優先度付きキューに変換
        cost = [float('inf')] * n  # 行ったことのないところはinf
        cost[s] = 0  # 開始地点は0
        while hq:
            c, v = heapq.heappop(hq)
            if c > cost[v]:  # コストが現在のコストよりも高ければスルー
                continue
            for d, u in e[v]:
                tmp = d + cost[v]
                if tmp < cost[u]:
                    cost[u] = tmp
                    heapq.heappush(hq, (tmp, u))
        return cost



    N, M, R = MI()
    r = LI()
    e = [[]for _ in range(N)]
    dis_list = [[]for _ in range(N)]
    for i in range(M):
        a, b, c = MI()
        a, b = a - 1, b - 1
        e[a].append((c, b))
        e[b].append((c, a))
    for r_ in r:
        dis_list[r_ - 1] = dijkstra(r_ - 1, N)

    Ans_list = []
    P = itertools.permutations(r)
    for p in P:
        dis = 0
        for i in range(R - 1):
            dis += dis_list[p[i] - 1][p[i + 1] - 1]
        Ans_list.append(dis)
    ans = min(Ans_list)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class Digraph:
    #入力定義
    def __init__(self,vertex=[]):
        self.vertex=set(vertex)

        self.edge_number=0
        self.vertex_number=len(vertex)

        self.adjacent_out={v:{} for v in vertex} #出近傍(vが始点)
        self.adjacent_in={v:{} for v in vertex} #入近傍(vが終点)

    #頂点の追加
    def add_vertex(self,*adder):
        for v in adder:
            if v not in self.vertex:
                self.adjacent_in[v]={}
                self.adjacent_out[v]={}

                self.vertex_number+=1
                self.vertex.add(v)

    #辺の追加(更新)
    def add_edge(self,From,To,weight=1):
        for v in [From,To]:
            if v not in self.vertex:
                self.add_vertex(v)

        if To not in self.adjacent_in[From]:
            self.edge_number+=1

        self.adjacent_out[From][To]=weight
        self.adjacent_in[To][From]=weight

    #辺を除く
    def remove_edge(self,From,To):
        for v in [From,To]:
            if v not in self.vertex:
                self.add_vertex(v)

        if To in self.adjacent_out[From]:
            del self.adjacent_out[From][To]
            del self.adjacent_in[To][From]
            self.edge_number-=1

    #頂点を除く
    def remove_vertex(self,*vertexes):
        for  v in vertexes:
            if v in self.vertex:
                self.vertex_number-=1

                for u in self.adjacent_out[v]:
                    del self.adjacent_in[u][v]
                    self.edge_number-=1
                del self.adjacent_out[v]

                for u in self.adjacent_in[v]:
                    del self.adjacent_out[u][v]
                    self.edge_number-=1
                del self.adjacent_in[v]

    #Walkの追加
    def add_walk(self,*walk):
        pass

    #Cycleの追加
    def add_cycle(self,*cycle):
        pass

    #頂点の交換
    def __vertex_swap(self,p,q):
        self.vertex.sort()

    #グラフに頂点が存在するか否か
    def vertex_exist(self,v):
        return v in self.vertex

    #グラフに辺が存在するか否か
    def edge_exist(self,From,To):
        if not(self.vertex_exist(From) and self.vertex_exist(To)):
            return False
        return To in self.adjacent_out[From]

    #近傍
    def neighbohood(self,v):
        if not self.vertex_exist(v):
            return []
        return list(self.adjacent[v])

    #出次数
    def out_degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent_out[v])

    #入次数
    def in_degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent_in[v])

    #次数
    def degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return self.out_degree(v)-self.in_degree(v)

    #頂点数
    def vertex_count(self):
        return len(self.vertex)

    #辺数
    def edge_count(self):
        return self.edge_number

    #頂点vを含む連結成分
    def connected_component(self,v):
        pass

#Warshall–Floyd
def Warshall_Floyd(D):
    """Warshall–Floyd法を用いて,全点間距離を求める.

    D:負Cycleを含まない有向グラフ
    """
    T={v:{} for v in D.vertex} #T[u][v]:uからvへ
    for u in D.vertex:
        for v in D.vertex:
            if v==u:
                T[u][v]=0
            elif v in D.adjacent_out[u]:
                T[u][v]=D.adjacent_out[u][v]
            else:
                T[u][v]=float("inf")

    for u in D.vertex:
        for v in D.vertex:
            for w in D.vertex:
                T[v][w]=min(T[v][w],T[v][u]+T[u][w])

    return T
#================================================
from itertools import permutations
N,M,R=map(int,input().split())
Y=list(map(int,input().split()))
D=Digraph(list(range(1,N+1)))
for _ in range(M):
    a,b,c=map(int,input().split())
    D.add_edge(a,b,c)
    D.add_edge(b,a,c)

Dist=Warshall_Floyd(D)

Z=float("inf")
for P in permutations(Y):
    X=0
    for i in range(R-1):
        X+=Dist[P[i]][P[i+1]]
    Z=min(Z,X)
print(Z)

Submission status: Accepted

Solution code:
n,m,r = map(int, input().split())
INF = 1 << 40
edges = [[INF]*n for i in range(n)]
rs  = list(map(int, input().split()))
rs = [r-1 for r in rs]
for i in range(m):
    a,b,c = map(int, input().split())
    a -= 1
    b -= 1
    edges[a][b] = c
    edges[b][a] = c

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

from itertools import permutations

ans = 1 << 50
for perm in permutations(rs):
    dist = 0
    for i in range(1,len(perm)):
        f = perm[i-1]
        t = perm[i]
        dist += edges[f][t]
    ans = min(ans, dist)
print(ans)

Submission status: Accepted

Solution code:
"""ABC073D joisino's travel
"""
from itertools import permutations
N,M,R=map(int, input().split())
r = list(map(lambda x: int(x)-1, input().split()))
INF = float("inf")
D = [[INF]*(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
    
def warshall_floyd(adj_mat: list):
    """
    ワーシャルフロイド
    隣接行列を受け取る(隣接していないノードはINF、自身へのコストは0)
    全点の間の最短距離をあらわす行列を返す(V * V)
    O(|V|**3)
    ネスト深くならないバージョン
    """
    V = len(adj_mat)
    for k in range(V): # 経由点
        for i in range(V): # 出発点
            for j in range(V): # 終点
                adj_mat[i][j] = min(
                    adj_mat[i][j],
                    adj_mat[i][k] + adj_mat[k][j]
                )
    return adj_mat
D = warshall_floyd(D)
ans = INF
for tpl in permutations(r, len(r)):
    tmp = 0
    for i in range(len(tpl)-1):
        tmp += D[tpl[i]][tpl[i+1]]
    ans = min(ans, tmp)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import permutations
N, M, R = map(int, input().split())
r = [int(i)-1 for i in input().split()]
inf = float("inf")
mat = [[inf]*N for _ in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    if mat[a-1][b-1] > c:
        mat[a-1][b-1] = mat[b-1][a-1] = c

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


ans = inf
for p in list(permutations(r)):
    dist = 0
    for i in range(1, len(p)):
        dist += mat[p[i]][p[i-1]]
    ans = min(ans, dist)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from itertools import permutations

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

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

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

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

warshall_floyd()
ans = 10**18

for p in permutations(r):
    now = p[0]-1
    cand = 0

    for i in range(1, R):
        cand += d[now][p[i]-1]
        now = p[i]-1

    ans = min(ans, cand)

print(ans)

Submission status: Accepted

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

# iからjへの距離
# 町の番号は0-indexに直す
d = [[10**9 for _ in range(N)] for _ in range(N)]

# 0から0, ..., N-1からN-1への距離
for i in range(N):
    d[i][i] = 0

# aからbへの距離、bからaへの距離を記録
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = 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

# 訪れる町の順列, 0-index
for p in itertools.permutations(r_list):
    tmp = 0
    for i in range(R - 1):
        x = p[i] - 1
        y = p[i + 1] - 1
        tmp += d[x][y]
    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()))
dp=[[float("INF")]*n for i in range(n)]
for i in range(m):
  a,b,c=list(map(int,input().split()))
  dp[a-1][b-1]=c
  dp[b-1][a-1]=c
for i in range(n):
  dp[i][i]=0
for k in range(n):
  for i in range(n):
    for j in range(n):
      dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
from itertools import permutations
per=list(permutations(r,R))
ans=float("INF")
for tup in per:
  ans_kouho=0
  for i in range(R-1):
    ans_kouho=ans_kouho+dp[tup[i]-1][tup[i+1]-1]
  ans=min(ans,ans_kouho)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
INF = 10**12+7
N,M,R = map(int,input().split())
r = list(map(str,input().split()))
d = [[INF]*(N+1) for _ in range(N+1)]
for _ in range(M):
    A,B,C = map(int,input().split())
    d[A][B] = C
    d[B][A] = C
for i in range(1,N+1):
    d[i][i] = 0
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])
#print(d)
ans = INF
que = deque([])
for i in r:
    que.append([i])
while len(que) != 0:
    p = que.popleft()
    if len(p) == R:
        #print(p)
        val = 0
        for i in range(1,R):
            val += d[ int(p[i-1])][int(p[i])]
        ans = min(ans,val)
    else:
        for i in r:
            if not i in p:
                que.append(p+[i])
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import itertools
INF = 10**12+7
N,M,R = map(int,input().split())
r = list(map(int,input().split()))
d = [[INF]*(N+1) for _ in range(N+1)]
for _ in range(M):
    A,B,C = map(int,input().split())
    d[A][B] = C
    d[B][A] = C
for i in range(1,N+1):
    d[i][i] = 0
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])
#print(d)
ans = INF
for i in itertools.permutations(r,len(r)):
    val = 0
    for j in range(1,len(r)):
        val += d[i[j-1]][i[j]]
    ans = min(ans,val)
print(ans)

Submission status: Accepted

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

for i in range(N):
  d[i][i] = 0 #自身への最短経路は0
#三重ループ
for k in range(N):
  for i in range(N):
    for j in range(N):
      d[i][j] = min(d[i][j], d[i][k]+d[k][j])
from itertools import groupby, accumulate, product, permutations, combinations
ans = 1<<30
for per in permutations(R,r):
  cnt = 0
  for i in range(r-1):
    cnt += d[per[i]][per[i+1]]
  ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
from itertools import *
from scipy.sparse.csgraph import *
import numpy as np
N,M,R = map(int,input().split())
T = list(map(int,input().split()))
E = [list(map(int,input().split())) for m in range(M)]
G = np.zeros((N,N))
A = []

for a,b,c in E:
  G[a-1][b-1] = c
  G[b-1][a-1] = c

F = floyd_warshall(G)

for P in permutations(T):
  A+=[sum(F[P[r]-1][P[r+1]-1] for r in range(R-1))]

print(int(min(A)))

Submission status: Accepted

Solution code:
from itertools import permutations
n_node, n_edge, R = map(int,input().split())
r_ls = list(map(int,input().split()))
for i in range(R):
    r_ls[i] -= 1
ad_mat = [[float('inf')]*n_node for _ in range(n_node)]
for i in range(n_node):
    ad_mat[i][i] = 0
for i in range(n_edge):
    a,b,c = map(int,input().split())
    ad_mat[a-1][b-1] = c
    ad_mat[b-1][a-1] = c

# ワーシャルフロイド
for stop in range(n_node):
    for start in range(n_node):
        for end in range(n_node):
            ad_mat[start][end] = min(ad_mat[start][end],ad_mat[start][stop]+ad_mat[stop][end])

ans = float('inf')
for path in permutations(r_ls):
    cost = 0
    for i in range(R-1):
        cost += ad_mat[path[i]][path[i+1]]
    ans = min(ans,cost)
print(ans)

Submission status: Accepted

Solution code:
N, M, K = (int(x) for x in input().split())
R = [int(x)-1 for x in input().split()]

dist = [[10e8 for _ in range(N)] for _ in range(N)]
for i in range(N): dist[i][i] = 0
for _ in range(M):
    a, b, c = (int(x) for x in input().split())
    dist[a-1][b-1] = dist[b-1][a-1] = c 
del a, b, c, K

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

def mindist(x, X):
    global dist
    Y = X.copy()
    Y.remove(x)
    if len(Y) == 0: return 0
    return min([dist[x][y] + mindist(y,Y) for y in Y])

ans = min([mindist(r, R) for r in R])
print(ans)

Submission status: Accepted

Solution code:
N,M,R = map(int,input().split())
R = list(map(int,input().split()))
ABC = [tuple(map(int,input().split())) for i in range(M)]

INF = float('inf')
d = [[INF]*N for _ in range(N)]
for i in range(N):
    d[i][i] = 0
for a,b,c in ABC:
    a,b = a-1,b-1
    d[a][b] = d[b][a] = 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
import itertools
for ptn in itertools.permutations(R):
    tmp = 0
    for a,b in zip(ptn,ptn[1:]):
        tmp += d[a-1][b-1]
    ans = min(ans, tmp)
print(ans)

Submission status: Accepted

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

n, m, r = map(int,input().split())
rlist = list(map(int,input().split()))
for i in range(r):
    rlist[i] -= 1
e = np.zeros((n,n), dtype=int)

for i in range(m):
    a, b, c = map(int,input().split())
    a -= 1
    b -= 1
    e[a][b] = c
    e[b][a] = c
csr = csr_matrix(e)
f = floyd_warshall(csr)

ans = 10**18
for v in itertools.permutations(rlist,r):
    d = 0
    for i in range(r-1):
        d += f[v[i]][v[i+1]]
    ans = min(ans, d)
print(int(ans))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys 
from itertools import permutations
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
INF = 10**31

N, M, R = map(int, readline().split())
r = list(map(int,readline().split()))
len_r = len(r)
cost = [[INF]*(N+1) for i in range(N+1)]

for i in range(M):
    s, t, d = map(int,readline().split())
    cost[s][t] = d
    cost[t][s] = d
  
for i in range(N+1):
    cost[i][i] = 0

for k in range(N+1):
    for i in range(N+1):
        for j in range(N+1):
            if cost[i][k] != INF and cost[k][j] != INF: #costがINFのときその道はつながっていないから
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])

ans = INF
for A in permutations(r,len_r):
    total = 0
    for i in range(len_r-1):
        s = A[i]
        t = A[i+1]        
        total += cost[s][t]
    ans = min(total,ans)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
n,m,r=map(int, input().split())
r_l=[int(i)-1 for i in input().split()]
town = [[float("INF")]*n for _ in range(n)]
for i in range(m):
    a,b,c=map(int, input().split())
    town[a-1][b-1]=c
    town[b-1][a-1]=c

for k in range(n):
    for i in range(n):
        for j in range(n):
            town[i][j] = min(town[i][j],town[i][k]+town[k][j])
res = float("INF")
for root in list(permutations(r_l)):
    tmp = 0
    for i in range(1,r):
        tmp += town[root[i]][root[i-1]]
    res = min(tmp,res)

print(res)

Submission status: Accepted

Solution code:
import itertools
N, M, R = map(int, input().split())
r = list(map(lambda x:int(x)-1, input().split()))
graph = [[] for _ in range(N)]
d = [[float('inf')]*N for _ in range(N)]
for _ in range(M):
  a, b, c = map(int, input().split())
  a -= 1
  b -= 1
  graph[a] += [[b, c]]
  graph[b] += [[c, a]]
  d[a][b] = c
  d[b][a] = c

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

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

d = warshall_floyd(d)
ans = float('inf')
for v in itertools.permutations(r):
  tmp = 0
  for i in range(len(v)-1):
    tmp += d[v[i]][v[i+1]]
  ans = min(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
INF = 10**10

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

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

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

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

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

Submission status: Accepted

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n,m,r = map(int,ipt().split())
    tgt = [int(i)-1 for i in ipt().split()]
    dt = [[10**18]*n for i in range(n)]
    for i in range(n):
        dt[i][i] = 0
    for i in range(m):
        a,b,c = map(int,ipt().split())
        a -= 1
        b -= 1
        dt[a][b] = c
        dt[b][a] = c

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

    mi = 10**18
    for i in itertools.permutations(range(r)):
        nm = 0
        for j in range(r-1):
            nm += dt[tgt[i[j]]][tgt[i[j+1]]]
        if mi > nm:
            mi = nm

    print(mi)

    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict, OrderedDict
#すべてのkeyが用意されてる defaultdict(int)で初期化
#順序を保ったdict
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########

n,m,r=map(int,input().split())
R=[i-1 for i in list(map(int,input().split()))]#いくまち
G=[[] for i in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    a-=1;b-=1
    G[a].append([c,b])
    G[b].append([c,a])  #G[i]:=iから出る道の[重み、行先]の配列


def dijkstra(s):
    dist=[inf for i in range(n)] #sからの距離のリスト
    dist[s]=0
    mirai=[True for i in range(n)] #Trueなら未確定
    mirai[s]=False

    queue=[] #こいつがheapqになる
    for kyori,to in G[s]:
        heapq.heappush(queue , kyori*10**6+to)  #重みと行先を1つの変数で表してる！
    while queue:
        minedge= heapq.heappop(queue)
        #miraiがTrueのやつ(未確定なやつ)から最小距離のものをさがす
        if not mirai[minedge%(10**6)]: continue
        #距離が小さいものから"確定"していく
        v=minedge%(10**6) #最小距離の頂点
        dist[v] = minedge//(10**6) #その距離
        mirai[v]=False
        for kyori,to in G[v]:
            if mirai[to]:
                heapq.heappush(queue, (kyori+dist[v])*(10**6)+to)
                #queueに入る数は、必ず「sからの」距離と行先を持っている
    return dist


from itertools import permutations as per
ans=inf
P=[dijkstra(i) for i in range(n)]
for l in per(R):
    now=0
    for i in range(r-1):
        now+=P[l[i]][l[i+1]]
    ans=min(ans,now)

print(ans)

Submission status: Accepted

Solution code:
import itertools
def warshall_floyd():
    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])
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
d = [[float('inf') if i != j else 0 for j in range(N+1)]for i in range(N+1)]
# print(d)
for m in range(M):
    A, B, C = map(int, input().split())
    d[A][B] = C
    d[B][A] = C
warshall_floyd()
ans = float('inf')
for p in itertools.permutations(r):
    tmp = 0
    for i in range(len(p)-1):
        tmp += d[p[i]][p[i+1]]
    ans = min(tmp, ans)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
N,M,R = map(int,input().split())
RList = list(map(int,input().split()))
dp = [[float("INF")]*(N+1) for _ in range(N+1)]
for i in range(N+1):
    dp[i][i] = 0
for _ in range(M):
    a,b,c = map(int,input().split())
    dp[a][b] = c
    dp[b][a] = c

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

ans = float("INF")
RList = list(permutations(RList))
for Rs in RList:
    tmp = 0
    for i in range(1,R):
        a = Rs[i-1]
        b = Rs[i]
        tmp += dp[a][b]
    ans = min(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

def solve(N: int, M: int, R: int, r: "List[int]", A: "List[int]", B: "List[int]", C: "List[int]"):
    from scipy.sparse import coo_matrix    
    from scipy.sparse.csgraph import floyd_warshall
    from itertools import permutations
    from functools import reduce
    # coo_matrix((data, (i, j)), [shape=(M, N)])
    mat = floyd_warshall(coo_matrix((C, (A, B)), shape=(N+1, N+1)).tocsr(), directed=False)
    f = lambda a, b: (a[0]+mat[a[1]][b], b)
    return int(min(reduce(f, q, (0, s))[0] for s, *q in permutations(r)))

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
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))
    print(solve(N, M, R, r, A, B, C))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

def solve(N: int, M: int, R: int, r: "List[int]", A: "List[int]", B: "List[int]", C: "List[int]"):
    import numpy as np    
    from scipy.sparse import coo_matrix    
    from scipy.sparse.csgraph import floyd_warshall
    from itertools import permutations, islice
    from functools import reduce
    # coo_matrix((data, (i, j)), [shape=(M, N)])
    mat = floyd_warshall(coo_matrix((C, (A, B)), shape=(N+1, N+1), dtype=np.int32).tocsr(), directed=False)
    f = lambda a, b: (a[0]+mat[a[1]][b], b)
    return int(min(reduce(f, q, (0, s))[0] for s, *q in permutations(r)))

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
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))
    print(solve(N, M, R, r, A, B, C))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

Solution code:
import itertools
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
N, M, R = map(int, input().split())
r = [int(i) for i in input().split()]

G = [[10**8]*(N+1) for _ in range(N+1)]
for _ in range(M):
    A, B, C = map(int, input().split())
    G[A][B] = C
    G[B][A] = C

DG = csgraph_from_dense(G, null_value=10**8)
d = floyd_warshall(DG)

ans = 10**8
for route in itertools.permutations(r):
    c = 0
    for i in range(len(route)-1):
        c += d[route[i]][route[i+1]]
    ans = min(ans, c)
print(int(ans))

Submission status: Accepted

Solution code:
import heapq
from itertools import permutations
n, m, r = map(int, input().split())
R = list(map(lambda x: int(x)-1, input().split()))
edges = [[]for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append((c, b))
    edges[b].append((c, a))


def dijkstra(init_v):
    next_v = [(0, init_v)]
    INF = 10**18
    dist = [INF]*n
    dist[init_v] = 0
    while next_v:
        d, v = heapq.heappop(next_v)
        if dist[v] < d:
            continue
        for d, v2 in edges[v]:
            if dist[v2] <= dist[v]+d:
                continue
            dist[v2] = dist[v]+d
            heapq.heappush(next_v, (dist[v2], v2))
    return dist


dists = []
for x in R:
    dist = dijkstra(x)
    dists.append(dist)

INF = 10**18
ans = INF
for subset in permutations(range(r)):
    d = 0
    for v, v2 in zip(subset, subset[1:]):
        d += dists[v][R[v2]]
    if d < ans:
        ans = d

print(ans)