Problem:


Score : 400 points

Problem Statement

There are N towns in the State of Atcoder, connected by M bidirectional roads.

The i-th road connects Town A_i and B_i and has a length of C_i.

Joisino is visiting R towns in the state, r_1,r_2,..,r_R (not necessarily in this order).

She will fly to the first town she visits, and fly back from the last town she visits, but for the rest of the trip she will have to travel by road.

If she visits the towns in the order that minimizes the distance traveled by road, what will that distance be?

Constraints

2≤N≤200

1≤M≤N×(N-1)/2

2≤R≤min(8,N) (min(8,N) is the smaller of 8 and N.)

r_i≠r_j (i≠j)

1≤A_i,B_i≤N, A_i≠B_i

(A_i,B_i)≠(A_j,B_j),(A_i,B_i)≠(B_j,A_j) (i≠j)

1≤C_i≤100000

Every town can be reached from every town by road.

All input values are integers.

Input

Input is given from Standard Input in the following format:

N M R
r_1 ... r_R
A_1 B_1 C_1
:
A_M B_M C_M

Output

Print the distance traveled by road if Joisino visits the towns in the order that minimizes it.

Sample Input 1

3 3 3
1 2 3
1 2 1
2 3 1
3 1 4

Sample Output 1

2

For example, if she visits the towns in the order of 1, 2, 3, the distance traveled will be 2, which is the minimum possible.

Sample Input 2

3 3 2
1 3
2 3 2
1 3 6
1 2 2

Sample Output 2

4

The shortest distance between Towns 1 and 3 is 4. Thus, whether she visits Town 1 or 3 first, the distance traveled will be 4.

Sample Input 3

4 6 3
2 3 4
1 2 4
2 3 3
4 3 1
1 4 1
4 2 2
3 1 6

Sample Output 3

3



Sample input:
3 3 3
1 2 3
1 2 1
2 3 1
3 1 4


Sample output:
2

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall as wf
from itertools import permutations
import sys
input = sys.stdin.readline

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

    MAX = int(1e9)
    link = [[MAX if i != j else 0 for j in range(N)] for i in range(N)]

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

    ans = -1
    for t in permutations(r):
        tmp = 0
        for i in range(1, R):
            tmp += link[t[i-1]-1][t[i]-1]
        if ans == -1:
            ans = tmp
        else:
            ans = min(ans, tmp)
    print(int(ans))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools

def war(N,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

def main():
    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(M):
        A, B, C = map(int, input().split())
        A -= 1
        B -= 1
        d[A][B] = C
        d[B][A] = C

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

    war(N,d)
    ans = float('inf')

    for a in itertools.permutations(r):
        tmp = 0
        for i in range(len(a)-1):
            tmp += d[a[i]-1][a[i+1]-1]
        ans = min(ans, tmp)

    print(ans)


main()

Submission status: Accepted

Solution code:
import itertools
 
N, M, R = map(int, input().split())
r = [int(x) - 1 for x in input().split()]
 
dist = [[float('inf')] * N for _ in range(N)]
for _ in range(M):
	a, b, c = map(int, input().split())
	a -= 1
	b -= 1
	dist[a][b] = dist[b][a] = c
 
for k in range(N):
	for i in range(N):
		for j in range(N):
			dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
 
ans = float('inf')
k = list(itertools.permutations(r))
for i in k:
	sumDist = 0
	for j in range(len(i) - 1):
		sumDist += dist[i[j]][i[j+1]]
	ans = min(ans, sumDist)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations as p
def wf(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())
d=[[10**9]*n for i in range(n)] 
rl=list(map(int,input().split()))
for i in range(m):
    a,b,c=map(int,input().split())
    d[a-1][b-1]=c
    d[b-1][a-1]=c
for i in range(n):
    d[i][i]=0
dl=wf(d)
pl=list(p(rl,r))
x=10**9
for i in pl:
  t=0
  for j in range(r-1):
    t+=dl[i[j]-1][i[j+1]-1]
  x=min(x,t)
print(x)

Submission status: Accepted

Solution code:
n,m,r = map(int,input().split())
l = list(map(int,input().split()))
g = [[10**10]*(n+1) for _ in range(n+1)]
for i in range(n+1):
  g[i][i] = 0
for _ in range(m):
  a,b,c = map(int,input().split())
  g[a][b] = c
  g[b][a] = c
for k in range(1,n+1):
  for i in range(1,n):
    for j in range(i+1,n+1):
      if g[i][j] >= g[i][k] + g[k][j]:
        g[i][j] = g[i][k] + g[k][j]
        g[j][i] = g[i][j]
g[0] = [0]*(n+1)
def dfs(cur,res,dis,use):
  if res == 0:
    return dis
  ans = 10**10
  for i in range(r):
    if not use[i]:
      use[i] = 1
      ans = min(ans, dfs(l[i],res-1,dis+g[cur][l[i]],use))
      use[i] = 0
  return ans
print(dfs(0,r,0,[0]*r))

Submission status: Accepted

Solution code:
import sys,itertools
input=sys.stdin.readline
INF=float('inf')
n,m,r=map(int,input().split())
R=list(map(int,input().split()))
distance=[[INF]*n for _ in range(n)]
for _ in range(m):
   a,b,c=map(int,input().split())
   distance[a-1][b-1]=c
   distance[b-1][a-1]=c

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

ans=INF
for p in itertools.permutations(R):
   cnt=0
   for q in range(r-1):
      cnt+=distance[p[q]-1][p[q+1]-1]
   ans=min(ans,cnt)

print(ans)

Submission status: Accepted

Solution code:
n, m, r = map(int,input().split())
R = list(map(int,input().split()))
A = [list(map(int,input().split())) for i in range(m)]

M = [[float("inf")] * (n+1) for i in range(n+1)]

for i in range(1, n+1):
    M[i][i] = 0
for i in range(m):
    M[A[i][0]][A[i][1]] = A[i][2]
    M[A[i][1]][A[i][0]] = A[i][2]

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

from scipy.sparse.csgraph import floyd_warshall
M = floyd_warshall(M)

import itertools
R1 = list(itertools.permutations(R))

ans = float("inf")
for i in range(len(R1)):
    ans1 = 0
    for j in range(r-1):
        ans1 += M[R1[i][j]][R1[i][j+1]]
    ans = min(ans, ans1)

print(int(ans))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#A
def A():
    s = S()
    if "9" in s:
        print("Yes")
    else:
        print("No")
    return

#B
def B():
    n = II()
    ans = 0
    for _ in range(n):
        l, r = LI()
        ans += r - l + 1
    print(ans)
    return

#C
def C():
    n = II()
    A = {}
    for _ in range(n):
        k = II()
        if not k in A:
            A[k] = 1
        else:
            A[k] += 1
    ans = 0
    for item in A.values():
        ans += item % 2
    print(ans)
    return

#D
def D():
    n, m, R = LI()
    r = LI()
    edg = [[0 if i == k else inf for k in range(n)] for i in range(n)]
    for _ in range(m):
        a, b, c = LI_()
        edg[a][b] = c + 1
        edg[b][a] = c + 1
    for k in range(n):
        for a in range(n):
            for b in range(n):
                edg[a][b] = min(edg[a][b], edg[a][k] + edg[k][b])
    ans = inf
    fullserch = itertools.permutations(range(R), R)
    for fulls in fullserch:
        b = 0
        for i in range(R - 1):
            b += edg[r[fulls[i]] - 1][r[fulls[i + 1]] - 1]
        ans = min(ans, b)
    print(ans)
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC73 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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 = LI()
r = LI()
d = [[inf]*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

d = warshall_floyd(d)
ans = inf
for i in permutations(r,R):
    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:
from itertools import permutations
from scipy.sparse.csgraph import floyd_warshall

n,m,R=map(int,input().split())
r=list(map(int,input().split()))
s=[[0]*n for i in range(n)]
for i in range(m):
    a, b, c = list(map(int, input().split()))
    a, b = a-1, b-1
    s[a][b] = c
    s[b][a] = c
s=floyd_warshall(s)   

ans=float('inf')
for i in permutations(r):
    an=0
    for j in range(R-1):
        an+=s[i[j]-1][i[j+1]-1]
    ans=min(ans,an)
print(int(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()]
v = [[] for _ in range(N)]
for _ in range(M) :
    A, B, C = map(int, input().split())
    v[A-1].append((B-1, C))
    v[B-1].append((A-1, C))

def dijkstra(s) :
    queue = [(s, 0)]
    dist = [float('inf')] * N
    dist[s] = 0
    while queue :
        cur, ccost = queue.pop()
        for nex, ncost in v[cur] :
            if ccost + ncost < dist[nex] :
                dist[nex] = ccost + ncost
                queue.append((nex, ccost + ncost))
    return dist
    
dist = dict()
for rr in r :
    dist[rr] = dijkstra(rr)

lr = len(r)
m = float('inf')
for perm in permutations(r) :
    tot = 0
    for i in range(lr-1) :
        tot += dist[perm[i]][perm[i+1]]
    m = min(m, tot)
    
print(m)

Submission status: Accepted

Solution code:
import itertools

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

def main():
    n,m,r = map(int,input().split())
    ls = [int(x) for x in input().split()]
    map_ls = [[float("inf") for _ in range(n+1)] for _ in range(n+1)]
    for _ in range(m):
        a,b,c = map(int,input().split())
        map_ls[a][b] = c
        map_ls[b][a] = c
    edes = Warshall_Floyd(map_ls,n+1)
    ans = int(10**9+7)
    for i in list(itertools.permutations(ls)):
        cnt = 0
        for j in range(1,r):
            now_,next_ = i[j-1],i[j]
            
            cnt += edes[now_][next_]
        ans = min(ans,cnt)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    N, M, R = map(int, input().split())
    Rs = list(map(int, input().split()))

    INF = 100000*200*200
    dp = [[INF for _ in range(N)] for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        dp[a-1][b-1] = c
        dp[b-1][a-1] = c

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


    def ind(i, R, rem, l, ans):
        if i == R:
            ans.append(l)
            return ans
        for r in rem:
            nl = l[:]
            nl.append(r)
            nr = rem[:]
            nr.remove(r)
            ans = ind(i+1, R, nr, nl, ans)
        return ans

    inds = ind(0, R, [i for i in range(R)], [], [])

    for k, ind in enumerate(inds):
        D = 0
        for j in range(R-1):
            D += dp[Rs[ind[j]]-1][Rs[ind[j+1]]-1]
        if k == 0:
            ans = D
        ans = min(ans, D)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

n,m,r=[int(x) for x in input().split()]
rlist=[int(x)-1 for x in input().split()]
abc=[[int(x) for x in input().split()] for _ in range(m)]

adj=[[float("inf")]*n for _ in range(n)]

for item in abc:
  if item[2]<adj[item[0]-1][item[1]-1]: adj[item[0]-1][item[1]-1]=item[2]
  if item[2]<adj[item[1]-1][item[0]-1]: adj[item[1]-1][item[0]-1]=item[2] 

adj=floyd_warshall(adj)

res=float("inf")

for route in itertools.permutations(rlist):
  tmp=sum([adj[route[i]][route[i+1]] for i in range(len(route)-1)])
  if tmp<res: res=tmp

print(int(res))

Submission status: Accepted

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

n,m,r=[int(x) for x in input().split()]
rlist=[int(x)-1 for x in input().split()]
abc=[[int(x) for x in input().split()] for _ in range(m)]

adj=[[float("inf")]*n for _ in range(n)]

for item in abc:
  if item[2]<adj[item[0]-1][item[1]-1]: adj[item[0]-1][item[1]-1]=item[2]
  if item[2]<adj[item[1]-1][item[0]-1]: adj[item[1]-1][item[0]-1]=item[2] 

d=floyd_warshall(adj)

res=float("inf")

for route in itertools.permutations(rlist):
  tmp=sum([d[route[i]][route[i+1]] for i in range(len(route)-1)])
  if tmp<res: res=tmp

print(int(res))

Submission status: Accepted

Solution code:
import itertools

inf = 10 ** 9
n, m, r = map(int, input().split())
r_list = [int(i) - 1 for i in input().split()]
a_list = [[inf for _ in range(n)] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    a_list[a][b] = a_list[b][a] = c
for k in range(n):
    for i in range(n):
        for j in range(i + 1, n):
            x = a_list[i][k] + a_list[k][j]
            if x < a_list[i][j]:
                a_list[i][j] = a_list[j][i] = x
k = list(itertools.permutations(r_list))
ans = inf
for kk in k:
    temp = 0
    for k1, k2 in zip(kk[:-1], kk[1:]):
        temp += a_list[k1][k2]
    if ans > temp:
        ans = temp
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
import numpy as np

MAX = 1e9
N, M, r = map(int, input().split())
R = list(map(lambda x: int(x) - 1, input().split()))
E = np.array([MAX]*(N**2), dtype=int).reshape((N, N))
for i in range(N):
    E[i, i] = 0
for _ in range(M):
    s, t, d = map(int, input().split())
    E[s-1, t-1] = d
    E[t-1, s-1] = d

for k in range(N):
    for i in range(N):
        E[i, :] = np.minimum(E[i, :], E[i, k] + E[k, :])

perm = permutations(R)
ans = MAX
for p in perm:
    c = 0
    for i in range(r-1):
        c += E[p[i]][p[i+1]]
    ans = min(ans, c)
print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n,m = LI()
    a = LIR(n)
    ans = 0
    for i in range(2):
        for j in range(2):
            for k in range(2):
                a.sort(key = lambda x:(-1)**i*x[0]+(-1)**j*x[1]+(-1)**k*x[2])
                p = [0,0,0]
                for l in range(m):
                    p[0] += a[l][0]
                    p[1] += a[l][1]
                    p[2] += a[l][2]
                p = abs(p[0])+abs(p[1])+abs(p[2])
                if p > ans:
                    ans = p
    print(ans)
    return

#B
def B():
    def root(x):
        if x == par[x]:
            return x
        par[x] = root(par[x])
        return par[x]

    def unite(x,y,su):
        x = root(x)
        y = root(y)
        su += comb_2(s[x])+comb_2(s[y])
        if rank[x] < rank[y]:
            s[y] += s[x]
            su -= comb_2(s[y])
            par[x] = y
        else:
            s[x] += s[y]
            su -= comb_2(s[x])
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1
        return su

    def comb_2(a):
        return a*(a-1)//2

    n,m = LI()
    v = LIR(m)
    par = [i for i in range(n)]
    rank = [0]*n
    s = [1]*n
    su = comb_2(n)
    ans = [su]
    for a,b in v[:0:-1]:
        a -= 1
        b -= 1
        if root(a) != root(b):
            su = unite(a,b,su)
        ans.append(su)
    for i in ans[::-1]:
        print(i)
    return

#C
def C():
    def root(x):
        if par[x] == x:
            return par[x]
        r = root(par[x])
        d[x] += d[par[x]]
        par[x] = r
        return par[x]

    def weight(x):
        root(x)
        return d[x]

    def unite(x,y,w):
        w += weight(x)
        w -= weight(y)
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
            d[x] = -w
        else:
            par[y] = x
            d[y] = w
            if rank[x] == rank[y]:
                rank[x] += 1
    n,m = LI()
    par = [i for i in range(n)]
    rank = [0]*n
    d = [0]*n
    for i in range(m):
        l,r,w = LI()
        l -= 1
        r -= 1
        if root(l) != root(r):
            unite(l,r,w)
        else:
            if weight(r)-weight(l) != w:
                print("No")
                return
    print("Yes")
    return

#D
def D():
    h,w = LI()
    n = I()
    a = LI()
    ans = [0]*h*w
    p = 0
    for i in range(n):
        for j in range(a[i]):
            ans[p+j] = i+1
        p += a[i]
    for i in range(h):
        s = ans[i*w:(i+1)*w]
        if i%2:
            print(*s[::-1])
        else:
            print(*s)
    return

#E
def E():
    n,k = LI()
    s = [int(x) for x in input()]
    f = [0]*n
    j = 0
    su = 1
    p = s[0]
    for i in range(1,n):
        if s[i] != p:
            f[j] = su
            j += 1
            su = 1
            p = s[i]
        else:
            su += 1
    f[j] = su
    f.append(0)
    if s[0]:
        m = sum(f[:2*k+1])
        ans = m
        for i in range(2*k+1,n):
            m -= f[i-2*k-1]
            if not i%2:
                m += f[i-1]
                m += f[i]
            ans = max(m,ans)
    else:
        m = sum(f[:2*k])
        ans = m
        for i in range(2*k,n):
            m -= f[i-2*k]
            if not i%2:
                m += f[i]
                m += f[i+1]
            ans = max(m,ans)
    print(ans)
    return

#F
def F():
    n = I()
    a = LI()
    s = [0,0,0]
    for i in a:
        if i%4 == 0:
            s[0] += 1
        elif i%2 == 0:
            s[1] += 1
        else:
            s[2] += 1
    a = [0]
    while 1:
        if s[2]:
            if a[-1] == 2:
                print("No")
                return
            s[2] -= 1
            a.append(2)
            if s[0]:
                s[0] -= 1
                a.append(0)
        elif s[1]:
            if a[-1] == 2:
                print("No")
            else:
                print("Yes")
            return
        else:
            print("Yes")
            return
    return

#G
def G():
    n,m,l = LI()
    r = LI()
    for i in range(l):
        r[i] -= 1
    d = [[float("inf")]*n for i in range(n)]
    for i in range(n):
        d[i][i] = 0
    for i in range(m):
        a,b,c = LI()
        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])
    m = 1<<l
    dp = [[float("inf")]*l for i in range(m)]
    for i in range(l):
        dp[1<<i][i] = 0
    for b in range(m):
        for i in range(l):
            x = r[i]
            if not b&(1<<i):
                continue
            for j in range(l):
                if b&(1<<j):
                    continue
                nb = b|(1<<j)
                y = r[j]
                res = dp[b][i]+d[x][y]
                if res < dp[nb][j]:
                    dp[nb][j] = res
    print(min(dp[m-1]))
    return

#H
def H():

    return

#I
def I_():

    return

#Solve
if __name__ == "__main__":
    G()

Submission status: Accepted

Solution code:
from itertools import permutations

n,m,r=map(int,input().split())
*R,=map(int,input().split())
INF=float("inf")
dist=[[INF]*n for _ in range(n)]
for i in range(n):
	dist[i][i]=0
for _ in range(m):
	a,b,c=map(int,input().split())
	dist[a-1][b-1]=c
	dist[b-1][a-1]=c
for k in range(n):
	for i in range(n):
		for j in range(n):
			dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])
v=[]
for i in R:
	t=[]
	for j in R:
		t.append(dist[i-1][j-1])
	v.append(t)
mn=INF
for t in permutations(range(r)):
	a=0;f=1
	for i,j in zip(t,t[1:]):
		if v[i][j]==INF:
			f=0
			break
		else:
			a+=v[i][j]
	if f:
		mn=min(mn,a)
print(mn)

Submission status: Accepted

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
# import sys
# sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########
    

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

def main():
    # https://atcoder.jp/contests/abc016/tasks/abc016_3
    N, M, R = l_inpl()
    r = list(map(int, input().split()))
    r = [ ri - 1 for ri in r ]

    # 隣接行列 G, 存在しない辺はINF
    G = [[INF] * N for _ in range(N)]

    # 自身に向かうコストは0
    for i in range(N):
        G[i][i] = 0

    for _ in range(M):
        a, b, c = l_inpl()
        a, b = a-1, b-1
        G[a][b] = c
        G[b][a] = c

    G = warshall_floyd(G)

    ans = INF
    for l in permutations(r):
        tmp = 0
        for i in range(len(l)-1):
            tmp += G[l[i]][l[i+1]]
        ans = min(tmp, ans)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math
import itertools
 
# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev
 
def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N,M,R = inputMap()
    r = inputList()
    A = [[float('inf') for _ in range(N)] for _ in range(N)]
    
    for _ in range(M):
        a,b,c = inputList()
        A[a-1][b-1] = c
        A[b-1][a-1] = c
    
    for i in range(N):
        A[i][i] = 0
        
    A = warshall_floyd(A, N)
        
    ans = -1
    visi = list(itertools.permutations(r))
    for sp in visi:
        tmp = 0
        for i, val in enumerate(sp):
            if i == 0:
                continue
            tmp += A[sp[i-1]-1][sp[i]-1]
            
        if ans == -1 or ans > tmp:
            ans = tmp
            
    print(ans)
        
def warshall_floyd(d, n):
	#d[i][j]: iからjへの最短距離
	for k in range(n):
		for i in range(n):
			for j in range(n):
				d[i][j] = min(d[i][j], d[i][k] + d[k][j])
	return d
		
            	
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math
import itertools

# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N,M,R = inputMap()
    r = inputList()
    A = [[100000000000000000 for _ in range(N)] for _ in range(N)]
    
    for _ in range(M):
        a,b,c = inputList()
        A[a-1][b-1] = c
        A[b-1][a-1] = c
    
    for i in range(N):
        A[i][i] = 0
        
    A = warshall_floyd(A, N)
        
    ans = -1
    visi = list(itertools.permutations(r))
    for sp in visi:
        tmp = 0
        for i, val in enumerate(sp):
            if i == 0:
                continue
            tmp += A[sp[i-1]-1][sp[i]-1]
            
        if ans == -1 or ans > tmp:
            ans = tmp
            
    print(ans)
        
def warshall_floyd(d, n):
	#d[i][j]: iからjへの最短距離
	for k in range(n):
		for i in range(n):
			for j in range(n):
				d[i][j] = min(d[i][j], d[i][k] + d[k][j])
	return d
		
            	
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:

import itertools
from scipy.sparse.csgraph import floyd_warshall as wf

def do():
    N,M,R = list(map(int,input().split(" ")))
    rs = list(map(int,input().split(" ")))
    INF = float('inf')

    graph = [ [INF for _ in range(N + 1)]for _ in range(N + 1)]
    for _ in range(M):
        a,b,c = (map(int, input().split(" ")))
        graph[a][b] = c
        graph[b][a] = c

    graph = wf(graph)

    perms = itertools.permutations(rs)
    ans = INF
    for temp in perms:
        cand = 0
        for i in range(0,R-1):
            fr = temp[i]
            to = temp[i + 1]
            cand+= graph[fr][to]
        ans = min(cand,ans)
    print(int(ans))

if __name__ == "__main__":
    do()

Submission status: Accepted

Solution code:
import heapq
import itertools

def dijkstra(s):
    cost = [10**20] * (N+1)
    visited = [False] * (N+1)
    visited[s], cost[s] = True, 0
    q = []

    for r in route[s]:
        heapq.heappush(q, r)

    while q:
        c, r = heapq.heappop(q)

        if not visited[r]:
            visited[r] = True
            cost[r] = min(cost[r], c)

            for c_, n in route[r]:
                if not visited[n]:
                    heapq.heappush(q, (c+c_, n))

    return cost

N, M, R = map(int, input().split())
r_ = list(map(int, input().split()))
ans = 10**10
route = [[] for i in range(N+1)]

for i in range(M):
    A, B, C = map(int, input().split())
    route[A].append((C, B))
    route[B].append((C, A))

cost = {r:dijkstra(r) for r in r_}
for r in itertools.permutations(r_):
    total = 0

    for i in range(R-1):
        total += cost[r[i]][r[i+1]]
    ans = min(ans, total)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import itertools
from scipy.sparse.csgraph import floyd_warshall as wf
import sys


MAX = 1e9


def main():
    n, m, r = map(int, input().split())
    R = list(map(int, input().split()))
    link = [[MAX if j != i else 0 for j in range(n+1)] for i in range(n+1)]
    for i in range(m):
        a, b, c = map(int, input().split())
        link[a][b] = c
        link[b][a] = c
    link = wf(link)
    ans = MAX
    for per in list(itertools.permutations(R)):
        tmp = 0
        for i in range(r-1):
            tmp += link[per[i]][per[i+1]]
        ans = min(ans, tmp)
    print(int(ans))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
import itertools
from scipy.sparse.csgraph import floyd_warshall as wf
import sys
input = sys.stdin.readline

MAX = 1e9

def main():
    N, M, R = map(int, input().split())
    r = list(map(int, input().split()))
    link = [[MAX if j != i else 0 for j in range(N+1)] for i in range(N+1)]

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

    link = wf(link)

    ans = MAX
    for per in list(itertools.permutations(r)):
        tmp = 0
        for i in range(R-1):
            tmp += link[per[i]][per[i+1]]
        ans = min(ans, tmp)
    print(int(ans))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m,r=map(int,input().split())
r_list=list(map(int,input().split()))
dp=[]
INF=10**9
for i in range(n):
    sub_list=[INF]*n
    dp.append(sub_list)
for i in range(n):
    dp[i][i]=0
for i in range(m):
    a,b,c=map(int,input().split())
    dp[a-1][b-1]=c
    dp[b-1][a-1]=c
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])
R=[i for i in range(r)]
import itertools
Rp=itertools.permutations(R,r)
ans=INF
count=0
for i in Rp:
    temp=0
    for j in range(r-1):
        temp+=dp[r_list[i[j]]-1][r_list[i[j+1]]-1]
    ans=min(ans,temp)
print(ans)