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

Solution (Python):

from heapq import heapify, heappop, heappush
from itertools import permutations


def dijkstra(G: "Array[Array[int]]", size: int, start: int) -> list:
    dist = [1 << 30] * size
    unchecked = size - 1  
    queue = [(0, start)]
    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:
            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 = 1 << 60
    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()

Solution (Python):

from heapq import heapify, heappop, heappush
from itertools import permutations


def dijkstra(G: "Array[Array[int]]", size: int, start: int) -> list:
    dist = [1 << 60] * size
    unchecked = size - 1  
    queue = [(0, start)]
    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:
            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 = 1 << 60
    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()

Solution (Python):

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
    unchecked = size - 1  
    queue = [(0, start)]
    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:
            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()

Solution (Python):

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 next_cost, u 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, 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()

Solution (Python):

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

Solution (Python):

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

Solution (Python):

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

Solution (Python):

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

Solution (Python):

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

Solution (Python):

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

Solution (Python):

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

Solution (Python):

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

Solution (Python):
import itertools

n,m,r=map(int,input().split())
r=list(map(int,input().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



d = [[float("inf") for i in range(n)] for i in range(n)] 

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


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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):

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


edge = np.zeros((N+1, N+1)) 
for _ in range(M):
    A, B, C = map(int, input().split())
    edge[A, B] = C


dist = shortest_path(edge, directed=False).astype(int)


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)

Solution (Python):
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()]


edge = np.zeros((N+1, N+1))
for _ in range(M):
  A, B, C = map(int, input().split())
  edge[A, B] = C


dist = shortest_path(edge, directed=False).astype(int)


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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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))

Solution (Python):
def dfs(count,last,distance):
    if (count == r):
        if (ans[0] > distance ):ans[0] = distance
        return
    for i in range(r):
        if seen[i]:continue
        seen[i] = True
        if last == -1:dfs(count+1,i,0)
        else:dfs(count+1,i,distance+dp[R[last]-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):
            if dp[i][j] > dp[i][k] + dp[k][j]:
                dp[i][j] = dp[i][k] + dp[k][j]
ans = [float("Inf")]
seen = [False]*r
dfs(0,-1,0)
print(*ans)

Solution (Python):
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))

Solution (Python):
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)

Solution (Python):

import sys
from itertools import permutations

def solve(N: int, M: int, R: int, r: "List[int]", A: "List[int]", B: "List[int]", C: "List[int]"):

    '''
    Warshall-Floyd
    input:  c[|V|][|V|]
            input example to from cost
            (c[i][i] == 0)
    Output: Minimun cost of all paths in the inputed graph 
    '''
    V = N
    INF = 1<<32
    d = [[INF] * (N+1) for i in range(N+1)]

    for i in range(M):
        d[A[i]][B[i]] = C[i]
        d[B[i]][A[i]] = C[i]

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


    ans = INF
    
    for i in permutations(r):
        ta = 0
        for x in range(R-1):
            ta += d[i[x]][i[x+1]]
        
        if(ta < ans):
            ans = ta

    print(ans)

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    R = int(next(tokens))  
    r = [int(next(tokens)) for _ in range(R)]  
    A = [int()] * (M)  
    B = [int()] * (M)  
    C = [int()] * (M)  
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    solve(N, M, R, r, A, B, C)

if __name__ == '__main__':
    main()

Solution (Python):
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)

ans=10**9
for i in itertools.permutations(r):

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

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string



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


input=sys.stdin.readline
show_flg=False


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

Solution (Python):

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




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)

Solution (Python):
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())

Solution (Python):
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)

Solution (Python):
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())