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:
# ABC073D - joisino's travel (218ms)
from collections import defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations


def dijkstra(G: "Array[dict[int]]", size: int, start: int) -> list:
    dist = [float("inf")] * size
    unchecked = size - 1  # vertex_0 won't appear in 1-idx graph
    queue = [(0, start)]
    heapify(queue)
    while queue:
        cost, v = heappop(queue)
        if cost > dist[v]:
            continue
        dist[v] = cost
        for u, next_cost in G[v].items():
            if cost + next_cost < dist[u]:
                heappush(queue, (cost + next_cost, u))
        unchecked -= 1
        if not unchecked:
            break
    return dist


def main():
    global G, N
    N, M, R, *RABC = map(int, open(0).read().split())
    visit, ABC = RABC[:R], RABC[R:]
    G = {v: defaultdict(int) for v in range(1, N + 1)}
    for v, u, cost in zip(*[iter(ABC)] * 3):
        G[v][u] = G[u][v] = cost
    dist = {v: dijkstra(G, N + 1, v) for v in visit}
    ans = float("inf")
    for perm in permutations(visit):
        cur = sum(dist[v][u] for v, u in zip(perm, perm[1:]))
        ans = min(ans, cur)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC073D - joisino's travel
from itertools import permutations
from scipy.sparse.csgraph import dijkstra


def main():
    N, M, R, *RABC = map(int, open(0).read().split())
    visit, ABC = RABC[:R], RABC[R:]
    G = [[float("inf")] * (N + 1) for _ in range(N + 1)]
    for v, u, c in zip(*[iter(ABC)] * 3):
        G[v][u] = G[u][v] = c
    dist = {v: dijkstra(G, N + 1, v) for v in visit}
    ans = float("inf")
    for perm in permutations(visit):
        cur = sum(dist[v][u] for v, u in zip(perm, perm[1:]))
        ans = min(ans, cur)
    print(int(ans))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC073D - joisino's travel
from heapq import heapify, heappop, heappush
from itertools import permutations


def dijkstra(G: "Array[Array[int]]", size: int, start: int) -> list:
    dist = [float("inf")] * size
    queue = [(0, start)]
    unchecked = size - 1  # vertex_0 won't appear in 1-idx graph
    heapify(queue)
    while queue:
        cost, v = heappop(queue)
        if cost > dist[v]:
            continue
        dist[v] = cost
        for next_cost, u in G[v]:
            if cost + next_cost < dist[u]:
                heappush(queue, (cost + next_cost, u))
        unchecked -= 1
        if not unchecked:
            break
    return dist


def main():
    global G, N
    N, M, R, *RABC = map(int, open(0).read().split())
    visit, ABC = RABC[:R], RABC[R:]
    G = [[] for _ in range(N + 1)]
    for v, u, cost in zip(*[iter(ABC)] * 3):
        G[v].append((cost, u)), G[u].append((cost, v))
    dist = {v: dijkstra(G, N + 1, v) for v in visit}
    ans = float("inf")
    for perm in permutations(visit):
        cur = sum(dist[v][u] for v, u in zip(perm, perm[1:]))
        ans = min(ans, cur)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC073D - joisino's travel
from heapq import heapify, heappop, heappush
from itertools import permutations


def dijkstra(G: "Array[Array[int]]", size: int, start: int) -> list:
    dist = [float("inf")] * size
    queue = [(0, start)]
    heapify(queue)
    while queue:
        cost, v = heappop(queue)
        if cost > dist[v]:
            continue
        dist[v] = cost
        for u, next_cost in G[v]:
            if cost + next_cost < dist[u]:
                heappush(queue, (cost + next_cost, u))
    return dist


def main():
    global G, N
    N, M, R, *RABC = map(int, open(0).read().split())
    visit, ABC = RABC[:R], RABC[R:]
    G = [[] for _ in range(N + 1)]
    for v, u, c in zip(*[iter(ABC)] * 3):
        G[v].append((u, c)), G[u].append((v, c))
    dist = {v: dijkstra(G, N + 1, v) for v in visit}
    ans = float("inf")
    for perm in permutations(visit):
        cur = sum(dist[v][u] for v, u in zip(perm, perm[1:]))
        ans = min(ans, cur)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC073D - joisino's travel
from heapq import heapify, heappop, heappush
from itertools import permutations


def dijkstra(G: "Array[Array[int]]", size: int, start: int) -> list:
    dist = [float("inf")] * size
    queue = [(start, 0)]
    heapify(queue)
    while queue:
        v, cost = heappop(queue)
        if cost > dist[v]:
            continue
        dist[v] = cost
        for u, next_cost in G[v]:
            if cost + next_cost < dist[u]:
                heappush(queue, (u, cost + next_cost))
    return dist


def main():
    global G, N
    N, M, R, *RABC = map(int, open(0).read().split())
    visit, ABC = RABC[:R], RABC[R:]
    G = [[] for _ in range(N + 1)]
    for v, u, c in zip(*[iter(ABC)] * 3):
        G[v].append((u, c)), G[u].append((v, c))
    dist = {v: dijkstra(G, N + 1, v) for v in visit}
    ans = float("inf")
    for perm in permutations(visit):
        cur = sum(dist[v][u] for v, u in zip(perm, perm[1:]))
        ans = min(ans, cur)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC073D - joisino's travel
from itertools import permutations
from scipy.sparse.csgraph import dijkstra


def main():
    N, M, R, *RABC = map(int, open(0).read().split())
    visit, ABC = RABC[:R], RABC[R:]
    G = [[float("inf")] * (N + 1) for _ in range(N + 1)]
    for v, u, c in zip(*[iter(ABC)] * 3):
        G[v][u] = G[u][v] = c
    dist = [None] * (N + 1)
    for i in range(1, N + 1):
        dist[i] = dijkstra(G, directed=0, indices=i)
    ans = float("inf")
    for perm in permutations(visit):
        cur = sum(dist[v][u] for v, u in zip(perm, perm[1:]))
        ans = min(ans, cur)
    print(int(ans))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC073D - joisino's travel
from itertools import permutations
from scipy.sparse.csgraph import floyd_warshall


def main():
    N, M, R, *RABC = map(int, open(0).read().split())
    visit, ABC = [i - 1 for i in RABC[:R]], RABC[R:]
    G = [[float("inf")] * N for _ in range(N)]
    for v, u, c in zip(*[iter(ABC)] * 3):
        v, u = v - 1, u - 1
        G[v][u] = G[u][v] = c
    dist = floyd_warshall(G, directed=0)
    ans = float("inf")
    for perm in permutations(visit):
        cur = sum(dist[v][u] for v, u in zip(perm, perm[1:]))
        ans = min(ans, cur)
    print(int(ans))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC073D - joisino's travel
from itertools import permutations
from scipy.sparse.csgraph import floyd_warshall


def main():
    N, M, R, *RABC = map(int, open(0).read().split())
    visit, ABC = RABC[:R], RABC[R:]
    G = [[float("inf")] * (N + 1) for _ in range(N + 1)]
    for v, u, c in zip(*[iter(ABC)] * 3):
        G[v][u] = G[u][v] = c
    dist = floyd_warshall(G, directed=0)
    ans = float("inf")
    for perm in permutations(visit):
        cur = sum(dist[v][u] for v, u in zip(perm, perm[1:]))
        ans = min(ans, cur)
    print(int(ans))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools

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

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 = [[float("inf") for i in range(n)] for i in range(n)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
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 #自身のところに行くコストは０
warshall_floyd(d)

ans=float("inf")
list_r=list(itertools.permutations(r))
# print(r)
# print(list_r)
for i in range(len(list_r)):
    tmp=0
    for j in range(len(r)-1):
        tmp+=d[list_r[i][j]-1][list_r[i][j+1]-1]
    ans=min(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
def dfs(c, l, d):
    if c == r:
        if ans[0] > d: ans[0] = d
        return
    for i in range(r):
        if seen[i]: continue
        seen[i] = True
        if l == -1:
            dfs(c + 1, R[i], 0)
        else:
            dfs(c + 1, R[i], d + dp[l][R[i]])
        seen[i] = False

n, m, r = map(int, input().split())
R = [i - 1 for i in map(int, input().split())]
dp = [[float("Inf") if i != j else 0 for i in range(n)] for j in range(n)]
for i in range(m):
    x, y, z = map(int, input().split())
    dp[x - 1][y - 1] = z
    dp[y - 1][x - 1] = z
for k in range(n):
    for j in range(n):
        for i in range(n):
            if dp[i][j] > dp[i][k] + dp[k][j]:
                dp[i][j] = dp[i][k] + dp[k][j]
seen = [False] * r
ans = [float("Inf")]
dfs(0, -1, 0)
print(*ans)

Submission status: Accepted

Solution code:
def dfs(c, l, d):
    if c == r:
        if ans[0] > d: ans[0] = d
        return
    for i in range(r):
        if seen[i]: continue
        seen[i] = True
        if l == -1:
            dfs(c + 1, R[i], 0)
        else:
            dfs(c + 1, R[i], d + dp[l][R[i]])
        seen[i] = False

n, m, r = map(int, input().split())
R = [i - 1 for i in map(int, input().split())]
dp = [[float("Inf") if i != j else 0 for i in range(n)] for j in range(n)]
for i in range(m):
    x, y, z = map(int, input().split())
    dp[x - 1][y - 1] = z
    dp[y - 1][x - 1] = z
for k in range(n):
    for i in range(n):
        for j in range(n):
            if dp[i][j] > dp[i][k] + dp[k][j]:
                dp[i][j] = dp[i][k] + dp[k][j]
seen = [False] * r
ans = [float("Inf")]
dfs(0, -1, 0)
print(*ans)

Submission status: Accepted

Solution code:
# D - joisino's travel
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)) # 1行目と1列目は使わない
for _ in range(M):
    A, B, C = map(int, input().split())
    edge[A, B] = C

# 2地点間の最短距離　　引数directed=False とすると無向グラフ
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:]:
        p += dist[prev, x]
        prev = x
    answer = min(answer, p)
  
print(answer)

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

# 引数 directed=False とすると無向グラフ
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:]:
    
    p += dist[prev, x]
    prev = x
  answer = min(answer, p)
  
print(answer)

Submission status: Accepted

Solution code:
from itertools import permutations

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

N,M,R = map(int,input().split())
town = list(map(int,input().split()))
street = [list(map(int,input().split())) for _ in range(M)]
distance = [[float("inf") for _ in range(N)] for _ in range(N)]
distance_in_town = [[0 for _ in range(R)] for _ in range(R)]
permutations_r = list(permutations(range(R)))
min_distance = float('inf')

for i in range(N):
    for j in range(N):
        if i==j:
            distance[i][j]=0

for s in street:
    distance[s[0]-1][s[1]-1] = s[2]
    distance[s[1]-1][s[0]-1] = s[2]

warshall_floyd(distance)

k = 0
for i in range(N):
    if i+1 in town:
        l = 0
        for j in range(N):
            if j+1 in town:
                distance_in_town[k][l] = distance[i][j]
                l += 1
        k += 1
        
for p in permutations_r:
    total_distance = 0
    for i in range(R-1):
        total_distance += distance_in_town[p[i]][p[i+1]]
    min_distance = min(min_distance,total_distance)

print(min_distance)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)

def dfs(c,l,d):
    if c == 0:
        ans[0] = min(ans[0],d)
        return
    for i in range(r):
        if seen[i]:continue
        seen[i] = True
        if l == -1:dfs(c-1,i,0)
        else:dfs(c-1,i,d+dp[R[l]-1][R[i]-1])
        seen[i] = False

n,m,r = map(int,input().split())
R = list(map(int,input().split()))
dp = [[0 if i == j else float("Inf") for i in range(n)] for j in range(n)]
for i in range(m):
    x,y,z = map(int,input().split())
    dp[x-1][y-1] = z
    dp[y-1][x-1] = z
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])
ans = [float("Inf")]
seen = [False]*r
dfs(r,-1,0)
print(*ans)

Submission status: Accepted

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

n,m,r=map(int,input().split())
r_l=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(m)]

d=[[float('inf')]*n for i in range(n)]
for i in range(n):
    d[i][i]=0
for i in l:
    d[i[0]-1][i[1]-1]=i[2]
    d[i[1]-1][i[0]-1]=i[2]
d=floyd_warshall(d)

ans=10**9
for i in itertools.permutations(r_l):
    t_ans=0
    for j in range(len(i)-1):
        t_ans+=d[i[j]-1][i[j+1]-1]
    ans=min(ans,t_ans)
print(int(ans))

Submission status: Accepted

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

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

way_cost = [[float('inf')]*N for _ in range(N)]

for idx in range(N):
    way_cost[idx][idx] = 0

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

# ワーシャルフロイド法で全ての街同士の最短距離を求める
shortest_path_cost = floyd_warshall(csgraph=way_cost, directed=False)

# 巡回ルートを総当りで調べ、最小コストを出力する
route_list = list(itertools.permutations(r))

ans = float('inf')
for route in route_list:
    cost = 0
    for idx in range(R-1):
        cost += shortest_path_cost[route[idx]][route[idx+1]]
    ans = min(ans,cost)

print(int(ans))

Submission status: Accepted

Solution code:
from itertools import permutations
from sys import stdin
N, M, R = [int(_) for _ in stdin.readline().rstrip().split()]
Rs = [int(_) for _ in stdin.readline().rstrip().split()]
D = [[10**9]*N for _ in range(N)]

for i in range(M):
    a, b, c = [int(_) for _ in stdin.readline().rstrip().split()]
    D[a-1][b-1] = c
    D[b-1][a-1] = c
for i in range(N):
    D[i][i] = 0

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

warshall_floyd()
p = list(permutations(Rs, R))

ans = 10**9
for i in p:
    tmp = 0
    for j in range(R-1):
        tmp += D[i[j]-1][i[j+1]-1]
    ans = min(ans, tmp)
print(ans)

Submission status: Accepted

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

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

s=[[float('inf') for i in range(N)] for i in range(N)]
for i in range(M):
    a,b,c=l[i]
    s[a-1][b-1]=c
    s[b-1][a-1]=c
for i in range(N):
    s[i][i]=0

s=floyd_warshall(s)
#print(s)
ans=10**9
for i in itertools.permutations(r):
#    print(i)
    temp_ans=0
    for j in range(R-1):
        temp_ans+=s[i[j]-1][i[j+1]-1]
    ans=min(ans,temp_ans)
print(int(ans))

Submission status: Accepted

Solution code:
import itertools
from scipy.sparse.csgraph import dijkstra
import sys 
input = sys.stdin.readline
def solve():
  n,m,R = (int(i) for i in input().split())
  r = list(int(i) for i in input().split())
  d = [[float("Inf")]*n for _ in range(n)]
  for i in range(m):
    a,b,c = (int(i) for i in input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
    
  d = dijkstra(d)

  perm = list(itertools.permutations(range(R)))
  cost = float("Inf")
  for i in range(len(perm)):
    root = perm[i]
    tempcost = 0
    for j in range(R-1):
      na = r[root[j]]-1
      nb = r[root[j+1]]-1
      tempcost += d[na][nb]
    cost = min(tempcost,cost)
  print(int(cost))
solve()

Submission status: Accepted

Solution code:
import itertools
import sys 
input = sys.stdin.readline
def solve():
  n,m,R = (int(i) for i in input().split())
  r = list(int(i) for i in input().split())
  d = [[float("Inf")]*n for _ in range(n)]
  for i in range(m):
    a,b,c = (int(i) for i in 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):
        if d[i][j] > d[i][k] + d[k][j]:
          d[i][j] = d[i][k] + d[k][j]

  perm = list(itertools.permutations(range(R)))
  cost = float("Inf")
  
  for i in range(len(perm)):
    root = perm[i]
    tempcost = 0
    for j in range(R-1):
      na = r[root[j]]-1
      nb = r[root[j+1]]-1
      tempcost += d[na][nb]
    cost = min(tempcost,cost)
  print(cost)
solve()

Submission status: Accepted

Solution code:
import itertools
from scipy.sparse.csgraph import dijkstra
import sys 
input = sys.stdin.readline
def solve():
  n,m,R = (int(i) for i in input().split())
  r = list(int(i) for i in input().split())
  d = [[0]*n for _ in range(n)]
  for i in range(m):
    a,b,c = (int(i) for i in input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
    
  d = dijkstra(d)

  perm = list(itertools.permutations(range(R)))
  cost = float("Inf")
  for i in range(len(perm)):
    root = perm[i]
    tempcost = 0
    for j in range(R-1):
      na = r[root[j]]-1
      nb = r[root[j+1]]-1
      tempcost += d[na][nb]
    cost = min(tempcost,cost)
  print(int(cost))
solve()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
#ts=time.time()
#sys.setrecursionlimit(10**6)
input=sys.stdin.readline
show_flg=False
#show_flg=True

n,m,R=MI()
r=LI_()
g=[[] for _ in range(n)]
for i in range(m):
    a,b,c=LI_()
    g[a].append((b,c+1))
    g[b].append((a,c+1))

show(g)
inf=float('inf')
def wf(e):
    n=len(e)
    d=[[inf]*n for _ in range(n)]
    for a in range(n):
        for b,c in g[a]:
            d[a][b]=c
            d[b][a]=c
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j]>d[i][k]+d[j][k]:
                    d[i][j]=d[i][k]+d[j][k]
    
    return d

ans=inf
md=wf(g)
dists=[]
def search(st,d,ls):
    if len(ls)==1:
        dists.append(d+md[st][ls[0]])
        return
    for gl in ls:
        search(gl,d+md[st][gl],[i for i in ls if i!=gl])
    return

for i in r:search(i,0,[j for j in r if i!=j])
print(min(dists))

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

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

import heapq

def dijkstra(vi):

    min_d_list = [10**27 for i in range(N)]
    min_d_list[vi] = 0
    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
                heapq.heappush(q,[d+d1,v1])

    return min_d_list

D = [[0]*R for i in range(R)]
for i in range(R):
    min_d_list = dijkstra(r[i]-1)
    for j in range(R):
        D[i][j] = min_d_list[r[j]-1]

import itertools
min_ans=10**27
for v in itertools.permutations(range(R)):
    ans = 0
    for i in range(1,R):
        ans+=D[v[i]][v[i-1]]

    min_ans=min(min_ans,ans)

print(min_ans)

Submission status: Accepted

Solution code:
import sys
import heapq
import bisect
import itertools

mod = 10**9+7
dd = ((-1,0),(1,0),(0,-1),(0,1))

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def S(): return(sys.stdin.readline()[:-1])
def IR(n): return([I() for _ in range(n)])

def GCD(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def LCM(a,b):
    return a * b // GCD(a,b)

def Eratosthenes(N):
    r = [True]*(N+1)
    r[0] = False
    r[1] = False
    i = 2
    while i*i<=N:
        if r[i]: 
            j = i
            while i*j<=N:
                prime[i*j]=False
                j+=1
        i+=1
    return(r)

def main():
    N,M,R = LI()
    r = LI()
    node = [[] for _ in range(N)]
    for _ in range(M):
        a,b,c = LI()
        node[a-1].append([b-1,c])
        node[b-1].append([a-1,c])

    dic = {}
    for x in r:
        dic_part = {}
        for y in r:
            dic_part[y-1] = 0
        dic[x-1] = dic_part

    for x in r:
        ques = []
        flag = [True] * len(node)
        heapq.heappush(ques,[0,x-1])
        while ques:
            dist,crt = heapq.heappop(ques)
            if flag[crt]:
                flag[crt] = False
                if (crt+1) in r:
                    dic[x-1][crt] = dist
                    dic[crt][x-1] = dist
                for nxt,nxt_dist in node[crt]:
                    if flag[nxt]:
                        heapq.heappush(ques,[dist+nxt_dist,nxt])
    ans = 10**11
    for tr in itertools.permutations(r):
        tans = 0
        for i in range(len(tr)-1):
            tans += dic[tr[i]-1][tr[i+1]-1]
        ans = min(ans,tans)
    return(ans)

if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce



sys.setrecursionlimit(2147483647)
INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m, r = LI()
graph = [[INF] * n for _ in range(n)]
L = LI()
for u, v, c in LIR(m):
    graph[u - 1][v - 1] = c
    graph[v - 1][u - 1] = c

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


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



ans = INF
for i in permutations(L):
    ret = 0
    for j in range(r - 1):
        ret += graph[i[j]-1][i[j+1]-1]
    ans = min(ans, ret)


print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def S(): return(sys.stdin.readline()[:-1])
def IR(n): return([I() for _ in range(n)])

def main():
    N,M,R = LI()
    rs = [int(x) -1 for x in sys.stdin.readline().split()]
    D = [[10**10]*N for _ in range(N)]
    for _ in range(M):
        A,B,C = LI()
        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**11
    for trs in itertools.permutations(rs):
        tans = 0
        for i in range(R-1):
            tans += D[trs[i]][trs[i+1]]
        ans = min(ans,tans)
    
    return(ans)

if __name__ == "__main__":
    print(main())

Submission status: Accepted

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

def WarshallFloyd(M):
    M = csgraph_from_dense(M)
    return floyd_warshall(M)

N, M, K = map(int, input().split())
R = [int(i) - 1 for i in input().split()]
E = [[0] * N for _ in range(N)]
for a, b, c in (map(int, input().split()) for _ in range(M)):
    a -= 1; b -= 1
    E[a][b] = E[b][a] = c

E = WarshallFloyd(E)
ans = min(sum(E[p[i]][p[i + 1]] for i in range(K - 1)) for p in permutations(R))
print(int(ans))

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N,M,R = map(int,input().split())
    r = list(map(int,input().split()))
    ABC = []
    D = [[float("inf")]*(N+1) for i in range(N+1)]
    for i in range(M):
        a,b,c = map(int,input().split())
        D[a][b] = 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])
                
    import itertools
    ans = float("inf")
    for v in itertools.permutations(r,R):
        #print(v)
        tmp = 0
        for i in range(R-1):
            tmp += D[v[i]][v[i+1]]
        if tmp < ans:
            ans = tmp
    #print(D)
    print(ans)
        
    
    
main()

Submission status: Accepted

Solution code:
from itertools import product, permutations,combinations


import sys
def input():
	return sys.stdin.readline().strip()

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

inf = 10000000000

dist = [[inf]*N for _ in range(N)]

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

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

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

min_dist = inf
for zyunro in permutations(r, len(r)):
	dist_sum = 0
	for i in range(R - 1):
		dist_sum += dist[zyunro[i] - 1][zyunro[i+1] - 1]
	min_dist = min(min_dist, dist_sum)

print(min_dist)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    n,m,r=map(int,input().split())
    R=list(map(lambda x:int(x)-1,input().split()))
    # Adjacency Matrix
    A=[[INF]*n for _ in range(n)]
    for i in range(n): A[i][i]=0
    for _ in range(m):
        a,b,c=map(int,input().split())
        a-=1
        b-=1
        A[a][b]=c
        A[b][a]=c
    # Warshall-Floyd
    from itertools import product
    for k,i,j in product(range(n),repeat=3):
        A[i][j]=min(A[i][j],A[i][k]+A[k][j])
    # calculate
    from itertools import permutations
    per=permutations(R)
    ans=INF
    for R in per:
        score=0
        for i in range(r-1):
            score+=A[R[i]][R[i+1]]
        ans=min(ans,score)
    print(ans)

resolve()

Submission status: Accepted

Solution code:
import itertools

N, M, R = map(int, input().split())
cities = list(map(int, input().split()))
INF = 10**10
dp = [[INF] * (N+1) for _ in range(N+1)]
for _ in range(M):
  s, g, c = map(int, input().split())
  dp[s][g] = c
  dp[g][s] = c
for i in range(N+1):
  dp[i][i] = 0
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])
patterns = itertools.permutations(cities, R)
ans = INF
for ptn in patterns:
  dis = 0
  for i in range(R-1):
    dis += dp[ptn[i]][ptn[i+1]]
  ans = min(ans, dis)
print(ans)

Submission status: Accepted

Solution code:
N, M, R = map(int, input().split())
rs = list(map(int, input().split()))
rs = [r-1 for r in rs]
D = [[100000*2000]*N for i in range(N)]
for i in range(N):
  D[i][i] = 0
for i in range(M):
  A, B, C = map(int, input().split())
  A, B = A-1, B-1
  D[A][B] = C
  D[B][A] = C
for k in range(N):
  for i in range(N):
    for j in range(N):
      D[i][j] = min(D[i][j], D[i][k]+D[k][j])
#print(D)
r = 100000*2000
import itertools
for rs2 in itertools.permutations(rs):
  r2 = 0
  for i in range(1, R):
    r2 += D[rs2[i-1]][rs2[i]]
  r = min(r, r2)
print(r)

Submission status: Accepted

Solution code:
from itertools import*;from scipy.sparse import*
N,M,R=map(int,input().split());r=map(int,input().split())
G=[[9e9]*N for _ in[0]*N]
for _ in[0]*M:A,B,C=map(int,input().split());G[A-1][B-1]=G[B-1][A-1]=C
D=csgraph.dijkstra(csr_matrix(G))
print(int(min(sum(D[i-1,j-1]for i,j in zip(t,t[1:]))for t in permutations(r))))

Submission status: Accepted

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


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


    N, M, R = map(int, input().split())
    r = list(map(int, input().split()))
    D = [[float('inf')]*N for _ in range(N)]
    for i in range(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(D, N)

    ans = float('inf')
    for P in itertools.permutations(r):
        cost = 0
        for i in range(R-1):
            cost += D[P[i]-1][P[i+1]-1]
        ans = min(ans, cost)

    print(ans)


if __name__ == '__main__':
    main()