Submission #2531316

---

Source Code Expand

import itertools

N,M,R = map(int,input().split())
r = list(map(int,input().split()))
g = [[] for _ in range(N+1)]

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

def DFS(v):
        d = [-1]*(N+1)
        d[v] = 0
        q = [v]

        while q:
                u = q.pop()
                for i in g[u]:
                        if d[i[0]] == -1 or d[i[0]] > (d[u] + i[1]):
                                d[i[0]] = d[u] + i[1]
                                [q.append(j[0]) for j in g[i[0]]]

        return d

d = [[] for _ in range(N+1)]

for i in r:
        d[i] = DFS(i)

ans = -1
for i in list(itertools.permutations(r)):
        a = 0
        for j in range(len(i)-1):
                a += d[i[j]][i[j+1]]
        if ans == -1 or ans > a:
                ans = a

print(ans)

Submission Info

Judge Result