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


import itertools
import sys

def main(argv):
    line = sys.stdin.readline()
    while line:
        N, M, R = map(lambda x: int(x), line.split(" ", 3))
        r  = map(lambda x: int(x) - 1, sys.stdin.readline().split(" "))
        weights = [[0 for i in xrange(N)] for j in xrange(N)]
        for i in xrange(M):
            a, b, c = map(lambda x: int(x), sys.stdin.readline().split(" ", 3))
            weights[a - 1][b - 1] = c
            weights[b - 1][a - 1] = c

        for k in xrange(N):
            for i in xrange(N):
                for j in xrange(N):
                    if j > i:
                        if weights[i][k] > 0 and weights[k][j] > 0:
                            length = weights[i][k] + weights[k][j]
                            if weights[i][j] == 0 or weights[i][j] > length:
                                weights[i][j] = length
                                weights[j][i] = length

        min_length = -1
        for p in itertools.permutations(r):
            length = 0
            previous = p[0]
            for i in p[1:]:
                length += weights[previous][i]
                previous = i
            if min_length == -1:
                min_length = length
            elif min_length > length:
                min_length = length
        print min_length

        line = sys.stdin.readline()

if __name__ == "__main__":
    main(sys.argv)

Solution (Python):

from itertools import permutations
from collections import deque

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




G = dict()
for i in range(N):
    G[i+1] = dict()
for _ in range(M):
    A, B, C = map(int, input().split())
    G[A][B] = C
    G[B][A] = C


dist_list = [[0]*R for _ in range(R)]

for i in range(R):
    
    que = deque([r_list[i]])
    d_list_i = [M*100000+1]*(N+1)
    d_list_i[r_list[i]] = 0
    while len(que) > 0:
        s = que.popleft()
        for t in G[s].keys():
            if d_list_i[s] + G[s][t] < d_list_i[t]:
                d_list_i[t] = d_list_i[s] + G[s][t]
                que.append(t)
            else:
                pass
        
    for j in range(R):
        dist_list[i][j] = d_list_i[r_list[j]]
    

perms = list(permutations(range(R)))

res = (M*100000+1)*R
for p in perms:
    res_ = 0
    for i in range(R-1):
        res_ += dist_list[p[i]][p[i+1]]
    res = min(res, res_)
    


print(res)

Solution (Python):
N, M, R = map(int, raw_input().split(' '))
rs = map(int, raw_input().split(' '))

edge = {}
for m in xrange(M):
  a, b, c = map(int, raw_input().split(' '))
  if a not in edge: edge[a] = {}
  if b not in edge: edge[b] = {}
  edge[a][b] = edge[b][a] = c

dist = {}
for r in rs:
  if r not in dist: dist[r] = {}
  dist[r][r] = 0
  fixed = {}
  while True:
    min_idx = None
    min_dist = float('inf')
    for i, d in dist[r].iteritems():
      if i not in fixed and d < min_dist:
        min_idx = i
        min_dist = d
    if min_idx is None: break
    fixed[min_idx] = True
    current = min_idx

    for i, d in edge[current].iteritems():
      if i in fixed: continue
      total = min_dist + d
      dist[r][i] = min(total, dist[r].get(i, float('inf')))

def process(now, rs, R, arrived):
  if len(arrived) == R:
    return 0
  min_dist = float('inf')
  for r in rs:
    if r in arrived: continue
    min_dist = min(min_dist, process(r, rs, R, arrived+[r]) + dist[now][r])
  return min_dist

print min(process(r, rs, R, [r]) for r in rs)

Solution (Python):

import heapq
import math

def permutations(iterable, r=None):
    
    
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = list(range(n))
    cycles = list(range(n, n-r, -1))
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

tmp = input()
N, M, R = [int(a) for a in tmp.split()]
tmp = input()
mokutekis = [int(a) for a in tmp.split()]
Rs = []
for i in range(M):
    tmp = input()
    Rs.append([int(a) for a in tmp.split()])

roots = {}
for a, b, dist in Rs:
    roots[(a, b)], roots[(b, a)] = dist, dist

minimums = {}
for i in range(1, N+1):
    minimums[(i, i)] = 0
for m in mokutekis:
    tmp_mins = {}
    merged = [False for i in range(N+1)]
    merged[m] = True
    merged_num = 1
    now = m
    while merged_num < N:
        minimum = [None, None]
        for i in range(1, N+1):
            if merged[i]:
                continue
            if (now, i) not in roots:
                new_dist = 100000*200+1
            else:
                new_dist = minimums[(m, now)] + roots[(now, i)]
            if (m, i) not in tmp_mins or tmp_mins[(m, i)] > new_dist:
                tmp_mins[(m, i)] = new_dist
                tmp_mins[(i, m)] = new_dist
            if minimum[0] is None or minimum[1] > tmp_mins[(m, i)]:
                minimum = i, tmp_mins[(m, i)]
        minimums[(m, minimum[0])], minimums[(minimum[0], m)] = minimum[1], minimum[1]
        now = minimum[0]
        merged[now] = True
        merged_num += 1

d_min = None
for perm in permutations(range(len(mokutekis))):
    perm = list(perm)
    d = 0
    d_max = None
    for p1, p2 in zip(perm, perm[1:]+[perm[0]]):
        m1, m2 = mokutekis[p1], mokutekis[p2]
        now_d = minimums[(m1, m2)]
        if d_max is None or d_max < now_d:
            d_max = now_d
        d += now_d
    d -= now_d
    if d_min is None or d_min > d:
        d_min = d
print(d_min)

Solution (Python):
from heapq import heappop, heappush
from itertools import permutations


def solve(links, rs):
    r = len(rs)
    dists = [[-1] * r for _ in range(r)]
    r_dict = {ri: i for i, ri in enumerate(rs)}
    for ri in rs:
        dists_r = dists[r_dict[ri]]
        visited = set()
        queue = [(0, ri)]
        r_cnt = 0
        while queue:
            cost, node = heappop(queue)
            if node in visited:
                continue
            if node in r_dict:
                dists_r[r_dict[node]] = cost
                r_cnt += 1
                if r_cnt == r:
                    break
            visited.add(node)
            for c, a in links[node]:
                if a not in visited:
                    heappush(queue, (cost + c, a))
    ans = 1e9
    for p in permutations(range(r)):
        tmp = sum(dists[r1][r2] for r1, r2 in zip(p, p[1:]))
        ans = min(ans, tmp)
    return ans


n, m, r = map(int, input().split())
rs = [i - 1 for i in map(int, input().split())]
links = [set() for _ in range(n)]
for a, b, c in (map(int, input().split()) for _ in range(m)):
    a -= 1
    b -= 1
    links[a].add((c, b))
    links[b].add((c, a))

print(solve(links, rs))

Solution (Python):
N,M,NR = map(int,input().split())

R = list(map(lambda x: int(x) - 1 ,input().split()))

import scipy.sparse as ss
import numpy as np

G = ss.dok_matrix((N,N), dtype=np.uint32)

def it():
  for _ in range(M):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    yield ((a,b),c)
    yield ((b,a),c)

G.update(it())

D = ss.csgraph.floyd_warshall(G.tocsr(), directed=False)

def it2():
  from itertools import permutations
  for p in permutations(R):
    pp = iter(p)
    next(pp)
    yield sum(D[a,b] for a,b in zip(p,pp))

print(int(min(it2())))

Solution (Python):
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n,m,r=na()
rs = na()
for i in range(r):
    rs[i] -= 1

g = [[99999999999]*n for _ in range(n)]
for i in range(n):
    g[i][i] = 0
for i in range(m):
    a, b, c = na()
    a -= 1
    b -= 1
    g[a][b] = g[b][a] = c

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

from itertools import *

ans = 9999999999999999999
for ord in permutations(rs):
    w = 0
    for i in range(1, r):
        w += g[ord[i-1]][ord[i]]
    ans = min(ans, w)
print(ans)

Solution (Python):
import itertools
n,m,r = map(int, input().split())
req = list(map(lambda x:int(x)-1, input().split()))
dist = [[float('inf') 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
    dist[a][b] = c
    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])

min_dist = float('inf')
for p in itertools.permutations(req):
    total_dist = 0
    for i in range(r-1):
        total_dist += dist[p[i]][p[i+1]]
    min_dist = min(min_dist, total_dist)
print(min_dist)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n,m,R = LI()
    t = LI()
    e = collections.defaultdict(list)
    for _ in range(m):
        a,b,c = LI()
        e[a].append((b,c))
        e[b].append((a,c))

    
    def search(s):
        d = collections.defaultdict(lambda: inf)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return d
    td = {}
    for i in t:
        td[i] = search(i)

    r = inf
    for ta in itertools.permutations(t):
        tr = 0
        for i in range(1,R):
            tr += td[ta[i-1]][ta[i]]
        if tr < r:
            r = tr

    return r

print(main())

Solution (Python):
from itertools import permutations

def main():
    n, m, r = map(int, input().strip().split())
    rs = list(map(int, input().strip().split()))
    dist = [[10 ** 10 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for _ in range(m):
        a, b, c = map(int, input().strip().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])
    ans = 10 ** 10
    for trs in permutations(rs):
        tans = 0
        for i in range(len(trs) - 1):
            tans += dist[trs[i]-1][trs[i+1]-1]
        ans = min(ans, tans)
    print(ans)

if __name__ == '__main__':
    main()