Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

Constraints

2≤N≤200

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

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

r_i≠r_j (i≠j)

1≤A_i,B_i≤N, A_i≠B_i

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

1≤C_i≤100000

Every town can be reached from every town by road.

All input values are integers.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

2

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

Sample Input 2

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

Sample Output 2

4

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

Sample Input 3

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

Sample Output 3

3



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


Sample output:
2

Submission status: Accepted

Solution code:
from itertools import permutations
import heapq
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
D = [[] for _ in range(N)]
inf = float("inf")
for i in range(N):
    for j in range(N):
        if i == j:
            D[i].append(0)
        else:
            D[i].append(inf)

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


def WarshallFloyd(D):
    """
    >>> WarshallFloyd([[0, 1, 4], [1, 0, 1], [4, 1, 0]])
    [[0, 1, 2], [1, 0, 1], [2, 1, 0]]
    """
    for k in range(len(D)):
        for i in range(len(D)):
            for j in range(len(D)):
                D[i][j] = min(D[i][j], D[i][k] + D[k][j])
    return D


def _dijkstra(D, s, F):
    q = []
    heapq.heappush(q, (0, s))
    while len(q) != 0:
        cost, index = heapq.heappop(q)
        if F[s][index] < cost:
            continue
        for i in range(len(D)):
            if cost + D[index][i] < F[s][i]:
                F[s][i] = cost + D[index][i]
                heapq.heappush(q, (F[s][i], i))
    return F


def Dijkstra(D):
    F = [[inf] * len(D) for _ in range(len(D))]
    for i in range(len(D)):
        F[i][i] = 0
        F = _dijkstra(D, i, F)
    return F


#W = WarshallFloyd(D)
D = Dijkstra(D)
# print(W)
# print(D)
Min = inf
for e in permutations(r):
    s = 0
    for i in range(R - 1):
        s += D[e[i] - 1][e[i + 1] - 1]
    Min = min(s, Min)

print(Min)

Submission status: Accepted

Solution code:
from itertools import permutations
N,M,R=map(int,input().split())
r = [int(i) for i in input().split()]
inf=10**10
#[k][j][i]
dp=[[[inf]*N for i in range(N)]for i in range(N+1)]
for i in range(M):
    a,b,c=map(int,input().split())
    dp[0][a-1][b-1]=c
    dp[0][b-1][a-1]=c
for k in range(1,N+1):
    for j in range(N):
        for i in range(N):
            dp[k][j][i]=min(dp[k-1][j][i],dp[k-1][j][k-1]+dp[k-1][k-1][i])

ans =inf
for elem in permutations(r, R):
    dis=0
    for i in range(R-1):
        dis+=dp[N][elem[i+1]-1][elem[i]-1]
    ans=min(ans,dis)
print(ans)

Submission status: Accepted

Solution code:
#import numpy as np
import itertools
import time

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

ROAD=[None]*M

for i in range(M):
    ROAD[i]=list(map(int,input().split()))


#Dis=np.full((N+1,N+1),float("inf"))

Dis=[None]*(N+1)
for i in range(1,N+1):
    Dis[i]=[100000000]*(N+1)

for i in range(M):
    Dis[ROAD[i][0]][ROAD[i][1]]=ROAD[i][2]
    Dis[ROAD[i][1]][ROAD[i][0]]=ROAD[i][2]



#ワーシャル–フロイド法を使って最短距離Disを求める

for k in range(1,N+1):#k個までの町を使ってのDisが知れているときに
    for i in range(1,N+1):#町iと
        for j in range(i,N+1):#町jとの最短距離は、
            length=Dis[i][k]+Dis[j][k]
            if Dis[i][j]>length:
                Dis[i][j]=length
                Dis[j][i]=length


  
PERM=list(itertools.permutations(r))



ANS=float("inf")
for i in range(len(PERM)):
    DIST=0
    for k in range(1,R):
        DIST+=Dis[PERM[i][k]][PERM[i][k-1]]
        if DIST>ANS:
            break
    if ANS>DIST:
        ANS=DIST

print(int(ANS))

Submission status: Accepted

Solution code:
def warshallfloyd(branch): #branchの中身はbranch[頂点] = [隣接頂点、距離]#
	dist = [[10000000 for i in range(n)]for k in range(n)]
	for i in range(n):
		dist[i][i] = 0
		for k in range(len(branch[i+1])):
			dist[i][branch[i+1][k][0]-1] = branch[i+1][k][1]
	for i in range(n):
		for k in range(n):
			for e in range(n):
				newlength = dist[k][i] + dist[i][e]
				if newlength < dist[k][e]:
					dist[k][e] = newlength
	return dist

import itertools
n,m,r = map(int,input().split())
visit = list(map(int,input().split()))
branch = dict()
for i in range(1,n+1):
	branch[i] = []
for i in range(m):
	a,b,c = map(int,input().split())
	branch[a].append([b,c])
	branch[b].append([a,c])

distance = warshallfloyd(branch)

min = 1000000000
test = list(itertools.permutations(visit))
for i in range(len(test)):
	temp = 0
	for k in range(len(test[i])-1):
		temp += distance[test[i][k]-1][test[i][k+1]-1]
	if temp < min:
		min = temp
print(min)

Submission status: Accepted

Solution code:
from itertools import permutations

def main():
    N, M, R = map(int, input().split())
    r = map(int, input().split())
    inf = float('inf')
    d = [[inf] * 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 -= 1
        b -= 1
        if d[a][b] > c:
            d[a][b], d[b][a] = c, c

    for k in range(N):
        for i in range(N):
            for j in range(N):
                temp = d[i][k] + d[k][j]
                if d[i][j] > temp:
                    d[i][j] = temp

    ans = inf
    for i in permutations(r):
        temp = 0
        for j in range(len(i)-1):
            temp += d[i[j] - 1][i[j + 1] - 1]
            if temp > ans:
                break
        if ans > temp:
            ans = temp

    print(ans)


main()

Submission status: Accepted

Solution code:
def hoge():
  from itertools import permutations
  N, M, R = map(int, input().split())
  r = map(int, input().split())
  inf = float('inf')
  d = [[inf] * 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 -= 1
      b -= 1
      t = min(c, d[a][b])
      if d[a][b] > c:
          d[a][b], d[b][a] = t, t


  for k in range(N):
      for i in range(N):
          for j in range(N):
            t = d[i][k] + d[k][j]
            if d[i][j] > t:
              d[i][j] = t


  ans = inf
  for i in permutations(r):
      temp = 0
      for j in range(len(i)-1):
          temp += d[i[j]-1][i[j+1]-1]
          if temp > ans:
              break
      if ans > temp:
        ans = temp
      # ans = min(ans, temp)

  print(ans)
hoge()

Submission status: Accepted

Solution code:
from itertools import permutations

def input_list():
    return list(map(int, input().split()))

def main():
    n, m, r = input_list()
    rlist = input_list()
    rlist = [r-1 for r in rlist]
    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 = input_list()
        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):
                distance = d[i][k]+d[k][j]
                if d[i][j] > distance:
                    d[i][j] = distance

    ans = float('inf')
    for p in permutations(rlist):
        distance = 0
        for i in range(r-1):
            distance += d[p[i]][p[i+1]]

        if ans > distance:
            ans = distance

    print(ans)

main()

Submission status: Accepted

Solution code:
from itertools import permutations
import gc
def read(): return list(map(int, input().split()))
 
 
INF = 114514810
 
 
def wf(d):
    N = len(d[0])
    for k in range(N):
        for i in range(N):
            for j in range(N):
                D = d[i][k] + d[k][j]
                if d[i][j] > D:
                    d[i][j] = D
    return d
 
 
def calc_dist(p, d):
    dist = 0
    for i in range(len(p) - 1):
        if d[p[i]][p[i + 1]] >= INF:
            return INF
        dist += d[p[i]][p[i + 1]]
    return dist
 
 
def main():
    N, M, R = read()
    r = map(lambda x: x - 1, sorted(read()))
    d = [[INF for i in range(N)] for j in range(N)]
 
    for i in range(M):
        a, b, c, = read()
        a -= 1
        b -= 1
        d[a][b] = d[b][a] = c
 
    d = wf(d)
 
    min_dist = INF
    for p in list(permutations(r)):
        min_dist = min(min_dist, calc_dist(p, d))
 
    print(min_dist)
 
 
if __name__ == '__main__':
    gc.disable()
    main()

Submission status: Accepted

Solution code:
from itertools import permutations
def read(): return list(map(int, input().split()))
 
 
INF = 114514810
 
 
def wf(d):
    N = len(d[0])
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
    return d
 
 
def calc_dist(p, d):
    dist = 0
    for i in range(len(p) - 1):
        if d[p[i]][p[i + 1]] >= INF:
            return INF
        dist += d[p[i]][p[i + 1]]
    return dist
 
 
def main():
    N, M, R = read()
    r = map(lambda x: x - 1, sorted(read()))
    d = [[INF for i in range(N)] for j in range(N)]
 
    for i in range(M):
        a, b, c, = read()
        a -= 1
        b -= 1
        d[a][b] = d[b][a] = c
 
    d = wf(d)
 
    min_dist = INF
    for p in list(permutations(r)):
        min_dist = min(min_dist, calc_dist(p, d))
 
    print(min_dist)
 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import permutations
from heapq import heappop,heappush
def dijkstra(n,s,adj):
	dis = [float("inf") for i in range(n+1)]
	dis[s],q = 0,[[0,s]]
	while q:
		num2,num = heappop(q)
		for i,j in adj[num]:
			if dis[i]>num2+j:
				dis[i] = num2+j
				heappush(q,[dis[i],i])
	return dis
n,m,r = (int(i) for i in input().split())
rlist = [int(i) for i in input().split()]
x = [[int(i) for i in input().split()] for i in range(m)]
road,y,ans = [[] for i in range(n+1)],[[] for i in range(n+1)],float("inf")
for i,j,k in x:
	road[i].append([j,k])
	road[j].append([i,k])
for i in rlist: y[i] = dijkstra(n,i,road)
for i in permutations(rlist,r):
	num = 0
	for j in range(r-1): num+=y[i[j]][i[j+1]]
	ans = min(num,ans)
print(ans)

Submission status: Accepted

Solution code:
import heapq
import itertools

def solve():
    N, M, _ = list(map(int, input().split()))
    R = list(map(int, input().split()))
    R = map(lambda x: x-1, R)
    G = [[] for i in range(N)]

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


    def dijkstra(d):
        que = []

        tar = -1
        count = set()
        for i in range(len(d)):
            if d[i] == 1e+16:
                break
            if d[i] == 0:
                tar = i
            heapq.heappush(que, (d[i], i))
            count.add(i)

        checked = [False for i in range(N)]

        while len(que) != 0:
            dist, node = heapq.heappop(que)
            if checked[node]:
                continue
            count.add(node)
            if len(count) == N:
                break

            for (cost, to) in G[node]:
                if d[to] > d[node] + cost:
                    d[to] = d[node] + cost
                    heapq.heappush(que, (dist + cost, to))

            checked[node] = True

        return d


    ds = [[1e16 for i in range(N)] for j in range(N)]

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

    for i in range(N):
        ds[i] = dijkstra(ds[i])
        for j in range(N):
            ds[j][i] = ds[i][j]

    res = 1e16
    for r in list(itertools.permutations(R)):
        d = 0
        for i in range(len(r)-1):
            d += ds[r[i]][r[i+1]]
        res = min(res, d)

    return res

print(solve())

Submission status: Accepted

Solution code:
INF = 10**9

N, M, R = list(map(int, input().split()))
r = list(map(int, input().split()))
W = [[INF for _ in range(N+1)] for __ in range(N+1)]
for i in range(1, N+1):
    W[i][i] = 0

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

import heapq

for i in range(1, N+1):
    heap = []
    checked = [False for _ in range(N+1)]
    for j in range(1, i+1):
        heapq.heappush(heap, (W[i][j], j))
    while len(heap) > 0:
        wij, j = heapq.heappop(heap)
        if checked[j]:
            continue
        for k in range(i+1, N+1):
            wik = wij + W[j][k]
            if wik <= W[i][k]:
                W[i][k] = wik
                W[k][i] = wik
                heapq.heappush(heap, (wik, k))
        checked[j] = True

from itertools import permutations

ans = INF
for r_ in permutations(r):
    count = 0
    for i in range(R-1):
        x = W[r_[i]][r_[i+1]]
        if x >= INF:
            break
        count += x
        if count >= ans:
            break
    else:
        ans = count
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
ARSP = [[float('inf')] * (N+1) for i in range(N+1)]
for i in range(M):
    a, b, c = map(int, input().split())
    ARSP[a][b] = c
    ARSP[b][a] = c


def warshall_floyd(adj_array):
    for k in range(len(adj_array)):
        for i in range(len(adj_array)):
            for j in range(len(adj_array)):
                if adj_array[i][k] + adj_array[k][j] < adj_array[i][j]:
                    adj_array[i][j] = min(adj_array[i][j], adj_array[i][k] + adj_array[k][j])
    return adj_array


ARSP = warshall_floyd(ARSP)

# 訪れ方の全列挙(max 8! = 40320)
journey = list(permutations(r))

ans = float('inf')
for j in journey:
    cost = 0
    for i in range(1, R):
        if ARSP[j[i]][j[i-1]] == float('inf'):
            break
        cost += ARSP[j[i]][j[i-1]]
        if cost >= ans:
            break
    else:
        ans = cost

print(ans)

Submission status: Accepted

Solution code:
import itertools
from collections import defaultdict
from heapq import heappush, heappop

inf = float("inf")

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

vertices = [i for i in range(1, N+1)]
edge_costs = {i: defaultdict(int) for i in range(N+1)}

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

def dijkstra(s):
    dist = [inf for _ in range(N+1)]
    dist[s] = 0
    searched = [False for _ in range(N+1)]
    
    q = [] # heap
    heappush(q, (0, s))
    
    while len(q) != 0:
        d, v = heappop(q)
        # don't need to check when the stored vertex has been already searched, 
        # or the stored value is greater than provisional distance
        if searched[v] or d > dist[v]:
            continue
            
        for u, c in edge_costs[v].items():
            temp = d + c
            if temp < dist[u]:
                dist[u] = temp
                heappush(q, (dist[u], u))
        
        searched[v] = True
        
        if sum(searched) == N: # finish when all vertices have been searched
            break
    
    return [dist[t] for t in towns]

D = [dijkstra(t) for t in towns]

ans = min([sum([D[perm[i]][perm[i+1]] for i in range(R-1)]) for perm in itertools.permutations(range(R))])
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# ワーシャルフロイド+全探索

import numpy as np
import itertools

def main():
    N, M, R = map(int, input().split())
    rs = list(map(int, input().split()))
    inf = float('inf')
    cost = [[inf]*N for _ in range(N)]

    # グラフ作る
    for i in range(N):
        cost[i][i] = 0

    for _ in range(M):
        a, b, c = map(int, input().split())
        cost[a-1][b-1] = c
        cost[b-1][a-1] = c
    
    # ワーシャルフロイドで全頂点間距離算出
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if cost[i][k]+cost[k][j] < cost[i][j]:
                    cost[i][j] = cost[i][k] + cost[k][j]

    # 組み合わせ全探索
    ans = inf
    for route in itertools.permutations(rs):
        d = 0
        for i in range(R-1):
            d += cost[route[i]-1][route[i+1]-1]
            if d > ans:
                break
        ans = min(ans, d)
    
    print(int(ans))


if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8

from itertools import permutations
import Queue

N, M, R = map(int, raw_input().split())
r = [i - 1 for i in map(int, raw_input().split())]

G = [[] for _ in xrange(N)]

for i in range(M):
    A, B, C = map(int, raw_input().split())
    A -= 1; B -= 1;
    G[A].append((B, C))
    G[B].append((A, C))

# dijkstra Algorithm
def dijkstra(s):
    d = [float("inf") for _ in xrange(N)]
    que = Queue.PriorityQueue()
    d[s] = 0
    que.put([0, s])

    while not que.empty():
        p = que.get()
        v = p[1]
        if d[v] < p[0]:
            continue
        for i, j in G[v]:
            if d[i] > d[v] + j:
                d[i] = d[v] + j
                que.put([d[i], i])
    return d

table = {}

for i in r:
    table[i] = dijkstra(i)

ans = float('inf')

for i in permutations(r):
    ans = min(ans, sum([table[i[j]][i[j+1]] for j in xrange(R-1)]))

print ans

Submission status: Accepted

Solution code:
from itertools import permutations
from heapq import heappush, heappop
def inpl(): return tuple(map(int, input().split()))
N, M, R = inpl()
inf = float("inf")
G = {n: {} for n in range(N+1)}
Des = inpl()

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

def dijkstra(s):
    D = [inf for _ in range(N+1)]
    D[s] = 0
    HQ = [(0, s)]
    checked = [False for _ in range(N+1)]
    while HQ:
        c1, a = heappop(HQ)
        if D[a] < c1 or checked[a]: continue
        for b, c2 in G[a].items():
            if c1 + c2 < D[b]:
                D[b] = c1 + c2
                heappush(HQ, (D[b], b))
        checked[a] = True
    return [D[des] for des in Des]

C = []
for s in Des:
    C.append(dijkstra(s))

res = inf
for E in permutations(range(len(Des)), len(Des)):
    res = min(res, sum([C[E[i]][E[i+1]] for i in range(len(Des)-1)]))

print(res)

Submission status: Accepted

Solution code:
from itertools import permutations
from heapq import heappush, heappop
def inpl(): return tuple(map(int, input().split()))
N, M, R = inpl()
inf = float("inf")
G = {n: {} for n in range(N+1)}
Des = inpl()

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

def dijkstra(s):
    D = [inf for _ in range(N+1)]
    D[s] = 0
    HQ = [(0, s)]
    checked = [False for _ in range(N+1)]
    n = N + 1
    while HQ:
        c1, a = heappop(HQ)
        if D[a] < c1 or checked[a]: continue
        for b, c2 in G[a].items():
            if c1 + c2 < D[b]:
                D[b] = c1 + c2
                heappush(HQ, (D[b], b))
        checked[a] = True
        n -= 1
        if not n: break
    return [D[des] for des in Des]

C = []
for s in Des:
    C.append(dijkstra(s))

res = inf
for E in permutations(range(len(Des)), len(Des)):
    res = min(res, sum([C[E[i]][E[i+1]] for i in range(len(Des)-1)]))

print(res)

Submission status: Accepted

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

cost=[ [ float("inf") for i in range(N+1)] for i in range(N+1) ]
nl=[ [] for i in range(N+1) ]

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


for i in range(N+1): cost[i][i]=0


def Dij(start):

	#Initialize
	d=[float("inf") for i in range(N+1)]
	d[start]=0
	q=[]
	heapq.heappush(q,(0,start))
	
	while len(q)!=0:
		tmp=heapq.heappop(q)
		u=tmp[1]

		for v in nl[u]:
			alt=d[u]+cost[u][v]
			if d[v]>alt:
				d[v]=alt
				heapq.heappush(q,(alt,v))
	return d


l=list(itertools.permutations(r))

C={}
for i in r:
	C[i]=Dij(i)


ans=float("inf")


for i in l:
	dist=0
	for j in range(R):
		if j==0:
			prev=i[j]
			continue
		cur=i[j]
		dist+=C[prev][cur]
		prev=cur
	ans=min(ans,dist)

print ans

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from itertools import permutations, product
from heapq import heappush, heappop
def inpl(): return tuple(map(int, input().split()))
N, M, R = inpl()
inf = float("inf")
G = {n: {} for n in range(N+1)}
Des = inpl() 

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

def dijkstra(s):
    D = [inf for _ in range(N+1)]
    D[s] = 0
    HQ = [(0, s)]
    checked = [False for _ in range(N+1)]
    while HQ:
        pc, a = heappop(HQ)
        if D[a] < pc or checked[a]:
            continue
        for b, c in G[a].items():
            if pc + c < D[b]:
                D[b] = pc + c
                heappush(HQ, (D[b], b))

        checked[a] = True
    return [D[des] for des in Des]

C = []
for s in Des:
    C.append(dijkstra(s))

res = inf
for E in permutations(range(len(Des)), len(Des)):
    res = min(res, sum([C[E[i]][E[i+1]] for i in range(len(Des)-1)]))            
        
print(res)

Submission status: Accepted

Solution code:
import sys
#sys.setrecursionlimit(n)
import heapq
from collections import defaultdict, deque
import itertools

import itertools
from heapq import heappop, heappush
N, M, R = map(int, input().split())

r = [int(i) for i in input().split()]
mp = defaultdict(lambda:defaultdict(list))
for _ in range(M):
    a, b, c= map(int, input().split())
    mp[a][b] = c
    mp[b][a] = c

v = [[float('inf')] * (N + 1) for _ in [0] * (N + 1)]
def dijkstra(start):
    q = []
    global v
    heapq.heappush(q, (0, start))
    vv = v[start]
    vv[start] = 0
    while(q):
        vc, vs = heapq.heappop(q)
        for i in mp[vs]:
            vsc = mp[vs][i]
            cost = vv[i]
            newcost = vsc + vc
            if cost > newcost:
                vv[i] = newcost
                heapq.heappush(q, (newcost, i))

for i in r:
    dijkstra(i)

ans = float('inf')
for i in itertools.permutations(r):
    t_ans = 0
    for j in range(R - 1):
        t_ans += v[i[j]][i[j + 1]]
    if ans > t_ans:
        ans = t_ans
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import sys
import itertools

def read_data():
    try:
        LOCAL_FLAG
        import codecs
        import os

        lines = []
        file_path = os.path.join(os.path.dirname(__file__), 'data073.dat')
        with codecs.open(file_path, 'r', 'utf-8') as f:
            lines.append(f.readline().rstrip("\r\n"))
            N, M, R = list(map(int, lines[0].split()))
            for i in range(M+1):
                lines.append(f.readline().rstrip("\r\n"))


    except NameError:
        lines = []
        lines.append(input())
        N, M, R = list(map(int, lines[0].split()))
        for i in range(M+1):
            lines.append(input())

    return lines

def dis(D, town_list):
    total = 0
    for i in range(len(town_list)-1):
        total += D[town_list[i]][town_list[i+1]]
    return total


def Travel():

    raw_data = read_data()
    N, M, R = list(map(int, raw_data[0].split()))
    town_list = list(map(int, raw_data[1].split()))
    road_set = set([])

    MAX = 200000
    # D = np.zeros((N+1, N+1), dtype='int32')
    # D += MAX
    D = [[float('inf')]*(N+1) for _ in range(N+1)]


    for i in range(2, M+2):
        a, b, c = list(map(int, raw_data[i].split()))
        D[a][b] = c
        D[b][a] = c

    # for i in range(1, N+1):
    #     for j in range(1, N+1):
    #         dis_two_node = np.min(D[i] + D[j])
    #         if dis_two_node < D[i,j]:
    #             D[i,j] = dis_two_node
    #             D[j,i] = dis_two_node

    # for i in range(N+1):
    #     D[i][i] = 0

    for k in range(1, N+1):
        for i in range(1, N+1):
            for j in range(1, N+1):
                dis_two_node = D[i][k] + D[k][j]
                if dis_two_node < D[i][j]:
                    D[i][j] = dis_two_node
                    D[j][i] = dis_two_node

   
    min_dis = float('inf')
    for each in itertools.permutations(town_list):
        min_dis = min(dis(D, each), min_dis)

    print(min_dis)




Travel()

Submission status: Accepted

Solution code:
import itertools

def main():
    N, M, R = map(int, input().split())
    RR = tuple(map(int, input().split()))
    ABC = {tuple(map(int, input().split())) for _ in range(M)}

    dist = [[float('inf')] * (N + 1) for j in range(N + 1)]
    for a, b, c in ABC:
        dist[a][b] = dist[b][a] = c
        dist[a][a] = dist[b][b] = 0
    for k in range(1, N + 1):
        for i in range(1, N + 1):
            for j in range(1, N + 1):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    ans = float('inf')
    for r in itertools.permutations(RR):
        move = 0
        for i in range(R - 1):
            a = r[i]
            b = r[i+1]
            move += dist[a][b]
        ans = min(ans, move)

    print(ans)

main()

Submission status: Accepted

Solution code:
n, m, r = map(int, input().split())
*R, = map(int, input().split())
E = [[10**18]*n for i in range(n)]
for i in range(n):
    E[i][i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    E[a-1][b-1] = E[b-1][a-1] = c
for k in range(n):
    for i in range(n):
        for j in range(n):
            E[i][j] = min(E[i][j], E[i][k] + E[k][j])

memo = {}
ALL = 2**r-1
def dfs(state, pos):
    if (state, pos) in memo:
        return memo[state, pos]
    if state == ALL:
        return 0
    res = 10**18
    for i in range(r):
        if state & (1 << i) == 0:
            res = min(res, dfs(state | (1 << i), R[i]-1) + E[pos][R[i]-1])
    memo[state, pos] = res
    return res
print(min(dfs(0, i) for i in range(n)))

Submission status: Accepted

Solution code:
#!/usr/bin/python

import sys

p=[0]*10000;mp=[];inf=65530060;v=[0]*1000;t=[0]*1000
 
 
ans=100000000

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



s=sys.stdin.readline().replace("\n","")

p=map(int,s.split(" "))


def dsss(x,now):
	global ans,v,p,t,mp
	if x==r+1:
		ans=min(ans,now)
		return 
	else :
		for i in range(r):
			if v[p[i]]==0 :
				v[p[i]]=1
				t[x]=p[i]
				if x==1:
					dsss(x+1,now)
				else :
					dsss(x+1,now+mp[p[i]-1][t[x-1]-1])
				v[p[i]]=0
	return 
 
 
for i in range(n+5):
	mp.append(range(n+5))
 
 
for i in range(n+5):
    for j in range(n+5):
            mp[i][j]=inf


for i in range(m):
	a,b,c=map(lambda x: int(x),sys.stdin.readline().split(" ",3))
	a-=1;b-=1;
	mp[a][b]=min(mp[a][b],c)
	mp[b][a]=min(mp[b][a],c)


for i in xrange(n):
	for j in xrange(n):
		for k in xrange(n):
			if mp[j][i]+mp[i][k]<mp[j][k]:
			    mp[j][k]=mp[j][i]+mp[i][k]

dsss(1,0)
 
print ans

Submission status: Accepted

Solution code:
import itertools

def main() :
    N, M, R = map(int, input().split())
    r = [a-1 for a in list(map(int, input().split()))]
    d = [[float('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 i in range(N):
        d[i][i] = 0

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

    ans = float("inf")

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

    print(ans)
    
main()

Submission status: Accepted

Solution code:
from itertools import permutations
 
 
def closest_path_lens(idx___neigh_idxes__dists, idx1):
    INF = 100001 * 201 * 200
    nodes_nr = len(idx___neigh_idxes__dists)
    idx___visited = [False] * nodes_nr
    idx___dist = [INF] * nodes_nr
    idx___dist[idx1] = 0
    for _ in range(nodes_nr):
        curr_idx = -1
        curr_dist = INF
        for idx, dist in enumerate(idx___dist):
            if dist < curr_dist and not idx___visited[idx]:
                curr_idx = idx
                curr_dist = dist
        idx___visited[curr_idx] = True
        for neigh_idx, dist in idx___neigh_idxes__dists[curr_idx]:
            # print(curr_dist, dist)
            idx___dist[neigh_idx] = min(idx___dist[neigh_idx], curr_dist + dist)
    return idx___dist
 
 
towns_nr, roads_nr, towns_to_visit_nr = (int(x) for x in input().split())
towns_to_visit = [(int(x) - 1) for x in input().split()]
town_idx___neigh_idxes__dists = [set() for _ in range(towns_nr)]
for road_idx in range(roads_nr):
    idx1, idx2, dist = (int(x) for x in input().split())
    idx1 -= 1
    idx2 -= 1
    town_idx___neigh_idxes__dists[idx1].add((idx2, dist))
    town_idx___neigh_idxes__dists[idx2].add((idx1, dist))
ttv_idx___ttv_idx__dist = []
for ttv in towns_to_visit:
    town_idx___dist  = closest_path_lens(town_idx___neigh_idxes__dists, ttv)
    # print(town_idx___dist)
    ttv_idx___dist = [town_idx___dist[idx] for idx in towns_to_visit]
    # print(ttv_idx___dist)
    ttv_idx___ttv_idx__dist.append(ttv_idx___dist)
ans = 100001 * 201 * 200
for path in permutations(list(range(towns_to_visit_nr))):
    curr_ans = 0
    curr_idx = path[0]
    for ttv_idx in path:
        # print(curr_idx, ttv_idx)
        curr_ans += ttv_idx___ttv_idx__dist[curr_idx][ttv_idx]
        curr_idx = ttv_idx
    # print(curr_ans)
    # print('\n')
    ans = min(ans, curr_ans)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import product, groupby, permutations
from math import pi
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = 10 ** 10


def main():
    N, M, R = map(int, input().split())
    r_list = list(map(int, input().split()))
    dp = [[float("inf")] * (N + 1) for _ in range(N + 1)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        dp[A][B] = dp[B][A] = C

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

    for m in range(N + 1):
        for s in range(N + 1):
            for e in range(N + 1):
                dist = dp[s][m] + dp[m][e]
                if dist < dp[s][e]:
                    dp[s][e] = dist

    ans = float("inf")
    for p in permutations(r_list, len(r_list)):
        total = 0
        for i in range(len(p) - 1):
            total += dp[p[i]][p[i + 1]]
            if total >= ans:
                break
        else:
            if total < ans:
                ans = total
    print(ans)

if __name__ == '__main__':
    main()