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
 
 
def warshallFloyd(V, dp):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                # dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
                new_dist = dp[i][k] + dp[k][j]
                if dp[i][j] > new_dist:
                    dp[i][j] = new_dist
 
 
def main():
    N, M, R = [int(x) for x in input().split()]
    destinations = [int(x) for x in input().split()]
    dp = [[float('inf')]*(N+1) for _ in range(N+1)]
    for i in range(N+1):
        dp[i][i] = 0
    for _ in range(M):
        f, t, d = [int(x) for x in input().split()]
        dp[f][t] = dp[t][f] = d
 
    warshallFloyd(N+1, dp)
 
    minimum_cost = float('inf')
    for route in permutations(destinations, len(destinations)):
        cost = 0
        while len(route) > 1:
            f, t = route[0], route[1]
            cost += dp[f][t]
            if cost > minimum_cost:
                break
            route = route[1:]
        if cost < minimum_cost:
            minimum_cost = cost
    print(minimum_cost)
 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

N,M,R=map(int,input().split())
r=list(map(int,input().split()))
for i in range(R): r[i] -= 1

g = [ [1001001001] * N for _ in range(N) ]
for i in range(N):
  g[i][i] = 0

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

def md(beg):
  d = [1001001001] * N
  done = [False] * N
  d[beg] = 0
  while True:
    cur = 1001001001
    pos = -1
    for i in range(N):
      if not done[i] and cur > d[i]:
        cur = d[i]
        pos = i
    if pos == -1:
      break
    done[pos] = True
    for i in range(N):
      d[i] = min(d[i], d[pos] + g[pos][i])
  return d

for i in range(R):
  g[r[i]] = md(r[i])

ans = 1001001001
for p in itertools.permutations(r):
  cur = 0
  for i in range(1, R):
    cur += g[p[i-1]][p[i]]
  ans = min(ans, cur)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc073/tasks/abc073_d
"""
from itertools import permutations


def warshallFloyd(V, dp):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                # dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
                new_dist = dp[i][k] + dp[k][j]
                if dp[i][j] > new_dist:
                    dp[i][j] = new_dist


def main():
    N, M, R = [int(x) for x in input().split()]
    destinations = [int(x) for x in input().split()]
    dp = [[float('inf')]*(N+1) for _ in range(N+1)]
    for i in range(N+1):
        dp[i][i] = 0
    for _ in range(M):
        f, t, d = [int(x) for x in input().split()]
        dp[f][t] = dp[t][f] = d

    warshallFloyd(N+1, dp)

    minimum_cost = float('inf')
    for route in permutations(destinations, len(destinations)):
        cost = 0
        while len(route) > 1:
            f, t = route[0], route[1]
            cost += dp[f][t]
            if cost > minimum_cost:
                break
            route = route[1:]
        if cost < minimum_cost:
            minimum_cost = cost
    print(minimum_cost)


if __name__ == '__main__':
    main()

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()
    road = input_list()
    road = [x-1 for x in road]
    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()
        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) :
                dist = d[i][k]+d[k][j]
                if d[i][j] > dist :
                    d[i][j] = dist

    ans = float('inf')
    for p in permutations(road) :
        dist = 0
        for i in range(r-1) :
            dist += d[p[i]][p[i+1]]
        if ans > dist :
            ans = dist

    print(ans)

main()

Submission status: Accepted

Solution code:
import scipy.sparse as S
import itertools as i
m=lambda:map(int,input().split())
N,M,_=m()
R=m()
G=S.dok_matrix((N,N))
G.update((lambda x:((next(x)-1,next(x)-1),next(x)))(m())for _ in range(M))
G=S.csgraph.floyd_warshall(G.tocsr(),directed=0)
print(int(min(sum(G[a-1,b-1]for a,b in zip(p[1:],p))for p in i.permutations(R))))

Submission status: Accepted

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

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

import numpy as np
from scipy.sparse.csgraph import floyd_warshall

G = np.zeros((N,N))

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

floyd_warshall(G, directed=False, overwrite=True)

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

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

Submission status: Accepted

Solution code:
import itertools
import sys

def main():
    N, M, R = map(int, sys.stdin.readline().split())
 
    r = [i - 1 for i in map(int, sys.stdin.readline().split())]
 
    d = [[float('inf')]*N for _ in range(N)]
 
    for _ in range(M):
        a, b, c = map(int,sys.stdin.readline().split())
        d[a-1][b-1] = c
        d[b-1][a-1] = c
 
    for a in range(N):
        d[a][a] = 0
 
    res = float('inf')
 
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if d[i][k]+d[k][j] < d[i][j]:
                    d[i][j] = d[i][k]+d[k][j]
 
    for perm in itertools.permutations(r):
        a = 0
        for i in range(len(perm)-1):
            a += d[perm[i]][perm[i+1]]
        res = min(a, res)
 
    print(res)
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
import sys
 
def readline():
    return sys.stdin.readline()
 
def read_int_list():
    return list(map(int, readline().split()))
 
def read_int():
    return int(readline())
 
def main():
    N, M, R = read_int_list()
 
    r = [a-1 for a in read_int_list()]
 
    d = [[float('inf')]*N for _ in range(N)]
 
    for _ in range(M):
        a, b, c = read_int_list()
        d[a-1][b-1] = c
        d[b-1][a-1] = c
 
    for a in range(N):
        d[a][a] = 0
 
    res = float('inf')
 
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if d[i][k]+d[k][j] < d[i][j]:
                    d[i][j] = d[i][k]+d[k][j]
 
    for perm in itertools.permutations(r):
        a = 0
        for i in range(len(perm)-1):
            a += d[perm[i]][perm[i+1]]
        res = min(a, res)
 
    print(res)
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
import sys
 
def readline():
    return sys.stdin.readline()
 
def read_int_list():
    return list(map(int, readline().split()))
 
def read_int():
    return int(readline())
 
def main():
    N, M, R = read_int_list()
 
    r = [a-1 for a in read_int_list()]
 
    d = [[float('inf')]*N for _ in range(N)]
 
    for _ in range(M):
        a, b, c = read_int_list()
        d[a-1][b-1] = c
        d[b-1][a-1] = c
 
    for a in range(N):
        d[a][a] = 0
 
    res = float('inf')
 
    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] = min(d[i][j], dd)
 
    for perm in itertools.permutations(r):
        a = 0
        for i in range(len(perm)-1):
            a += d[perm[i]][perm[i+1]]
        res = min(a, res)
 
    print(res)
 
if __name__ == '__main__':
    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:
import itertools
import sys

def readline():
    return sys.stdin.readline()

def read_int_list():
    return list(map(int, readline().split()))

def read_int():
    return int(readline())

def main():
    N, M, R = read_int_list()

    r = [a-1 for a in read_int_list()]

    d = [[float('inf')]*N for _ in range(N)]

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

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

    res = float('inf')

    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] = min(d[i][j], dd)

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

    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
import sys

def readline():
    return sys.stdin.readline()

def read_int_list():
    return list(map(int, readline().split()))

def read_int():
    return int(readline())

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

    inf = float("inf")
    d = [[inf] * (N + 1) for _ in range(N + 1)]
    for n in range(1, N + 1):
        d[n][n] = 0

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

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

    min_cost = inf
    for p in itertools.permutations(r):
        cost = 0
        for i in range(len(p) - 1):
            src, dst = p[i:i + 2]
            cost += d[src][dst]
        min_cost = min(min_cost, cost)

    print(min_cost)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m,R=[int(x) for x in input().split()]
r=[int(x) -1 for x in input().split()]
d=[[float("inf") for _ in [0]*n] for _ in [0]*n]
for i in range(n):
    d[i][i]=0
for i in [0]*m:
    a,b,c=[int(x) for x in input().split()]
    d[a-1][b-1]=d[b-1][a-1]=c
from itertools import product,permutations
for i,j,k in product(range(n),range(n),range(n)):
    if d[i][j] >d[i][k]+d[k][j]:
        d[i][j]=d[i][k]+d[k][j]
for i,j,k in product(range(n),range(n),range(n)):
    if d[i][j] >d[i][k]+d[k][j]:
        d[i][j]=d[i][k]+d[k][j]
def Long(args):
    ans=0
    for i in range(len(args)-1):
        ans+=d[args[i+1]][args[i]]
    return ans
print(min(Long(i) for i in permutations(r)))

Submission status: Accepted

Solution code:
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

from heapq import *
def dijkstra(g, start):
    n = len(g)
    ds = [1e18] * n
    ds[start] = 0
    h = []
    heappush(h, (0, start))
    while len(h) > 0:
        d, cur = heappop(h)
        if d != ds[cur]: continue
        for e, ew in g[cur]:
            if d + ew < ds[e]:
                ds[e] = d + ew
                heappush(h, (ds[e], e))
    return ds

def dijkstra_dense(g, start):
    n = len(g)
    ds = [1e18] * n
    ds[start] = 0

    done = [0] * n
    while True:
        lmin = 1e19
        arg = -1
        for i in range(n):
            if not done[i] and ds[i] < lmin:
                lmin = ds[i]
                arg = i
        if arg == -1: break
        done[arg] = 1
        for i in range(n):
            ds[i] = min(ds[i], lmin + g[arg][i])
    return ds


dss = [None] * n
for r in rs:
    dss[r] = dijkstra_dense(g, r)

from itertools import *

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

Submission status: Accepted

Solution code:
import sys
from itertools import permutations
 
def read_int_list():
    return list(map(int, input().split()))
 
 
def main():
    def floyd_warshall():
        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
 
    n, m, r = read_int_list()
    v = read_int_list()
    v = [x - 1 for x in v]
    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 = read_int_list()
        a -= 1
        b -= 1
        d[a][b] = c
        d[b][a] = c
    floyd_warshall()
    res = float('inf')
    for p in permutations(v):
        s = 0
        for i in range(r - 1):
            s += d[p[i]][p[i + 1]]
        if s < res:
            res = s
    print(res)
 
 
main()

Submission status: Accepted

Solution code:
import itertools
n,m,R=map(int,input().split())
r=list(map(int,input().split()))
g=[[100000*200+1]*n for i in range(n)]
for _ in range(m):
    a,b,c=map(int,input().split())
    g[a-1][b-1]=g[b-1][a-1]=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])
print(min(
    sum(g[s[i-1]-1][s[i]-1] for i in range(1,R))
    for s in itertools.permutations(r)))

Submission status: Accepted

Solution code:
from scipy.sparse import*;f=lambda*z:map(int,raw_input().split());N,M,R=f();r=f();a,b,c=zip(*map(f,[0]*M));a=csgraph.dijkstra(csr_matrix((c,(a,b)),[N+1]*2),0,r);print int(min(sum(a[e[i]][r[e[i+1]]]for i in range(R-1))for e in __import__('itertools').permutations(range(R))))

Submission status: Accepted

Solution code:
#coding=UTF-8

def search(jun):
    global ans
    global R
    global r
    global rCost
    tmpans=0
    if len(jun)==R:
        mae=jun[0]
        for idx in range(1,R,1):
            ba=jun[idx]
            tmpans += rCost[mae][r[ba]]
            mae=ba

        if ans==None or tmpans<ans:
            ans=tmpans
    else:
        for me in range(0,R,1):
            if not (me in jun):
                search(jun+[me])


mozir=input()
hyo=mozir.split(' ')
N=int(hyo[0])
M=int(hyo[1])
R=int(hyo[2])

mozir=input()
hyo=mozir.split(' ')
r=[(int(mono) -1 ) for mono in hyo]

michi=[]
for idx in range(0,N,1):
    michi.append([])

for idx in range(0,M,1):
    mozir=input()
    hyo=mozir.split(' ')
    A=int(hyo[0])-1
    B=int(hyo[1])-1
    C=int(hyo[2])
    michi[A].append((B,C))
    michi[B].append((A,C))


rCost=[]
for idr in range(0,R,1):
    Cost=[None]*N
    Cost[r[idr]]=0
    miru=[r[idr]]
    while miru:
        nextmiru=[]
        for toshi in miru:
            preCost=Cost[toshi]
            for (saki,sakiCost) in michi[toshi]:
                tmpCost=preCost+sakiCost
                if Cost[saki]==None or tmpCost < Cost[saki]:
                    Cost[saki]=tmpCost
                    nextmiru.append(saki)

        miru=list(set(nextmiru))
    rCost.append(Cost)

#for ko in rCost:
#    print(ko)

ans=None
search([])
print(ans)

Submission status: Accepted

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]

[N,M,R]=i2()
r=i2()
f=float("inf")
d=[[f for j in range(N)]for i in range(N)]
for i in range(N):d[i][i]=0
for i in range(M):
    a=i2()
    d[a[0]-1][a[1]-1]=a[2]
    d[a[1]-1][a[0]-1]=a[2]
for i in range(N):
    for j in range(N):
        for k in range(N):
            d[j][k]=min(d[j][k],d[j][i]+d[i][k])
c=float("inf")

import itertools
for i in list(itertools.permutations(r)):
    ddd=0
    for j in range(len(i)-1):
       ddd+=d[i[j]-1][i[j+1]-1]
    c=min(c,ddd)

print(c)

Submission status: Accepted

Solution code:
from itertools import permutations
 
def floyd_warshall():
            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])
 
            
N, M, R = list(map(int, input().split()))
r = (int(i)-1 for i in input().split())
res = float('inf')
dist = [[float("inf")] * N for i in range(N)]
for i in range(N):
        dist[i][i] = 0
for i in range(M):
    a, b, c = list(map(int, input().split()))
    a -= 1
    b -= 1
    dist[a][b] = dist[b][a] = c
 
floyd_warshall()
for p in permutations(r):
        s = 0
        for i in range(R - 1):
            s += dist[p[i]][p[i + 1]]
        if s < res:
            res = s
print(res)

Submission status: Accepted

Solution code:
from scipy.sparse import*
(N,M,R),r,*t=[map(int,i.split())for i in __import__("sys").stdin]
a,b,c=zip(*t)
l=csgraph.dijkstra(csr_matrix((c,(a,b)),[N+1]*2),0)
print(min(sum(int(l[i][j])for i,j in zip(a[:-1],a[1:]))for a in __import__("itertools").permutations(r)))

Submission status: Accepted

Solution code:
from itertools import permutations


def main():
    """
    とおり方
    2 <= N <= 200
    2 <= R <= min(8, N)
    より、
    最大でも 2 <= R <= 8
    8! = 40320

    道路
    1 <= M <= N * (N-1) / 2
    より、
    最大でも 100 * 199 = 19900

    調べ方
    rに現れない町を経由する可能性がある
    ある町Aからある町Bまでの最短距離を求める
    ABCの町を訪れるならば、
    A→B→C、
    B→C→A
    C→A→B
    の３パターン（組合せ）がある
    もちろん他の町を経由するかもしれない
        A→(D)→B→(E)→C
    """
    N, M, R = map(int, input().split())
    r = map(int, input().split())

    inf = float("inf")
    d = [[inf] * (N + 1) for _ in range(N + 1)]
    for n in range(1, N + 1):
        d[n][n] = 0

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

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

    min_cost = inf
    for p in permutations(r):
        cost = 0
        for i in range(len(p) - 1):
            src, dst = p[i:i + 2]
            cost += d[src][dst]
        min_cost = min(min_cost, cost)

    print(min_cost)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import permutations

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

 
def main():
    def floyd_warshall():
        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
 
    n, m, r = read_int_list()
    v = read_int_list()
    v = [x - 1 for x in v]
    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 = read_int_list()
        a -= 1
        b -= 1
        d[a][b] = c
        d[b][a] = c
    floyd_warshall()
    res = float('inf')
    for p in permutations(v):
        s = 0
        for i in range(r - 1):
            s += d[p[i]][p[i + 1]]
        if s < res:
            res = s
    print(res)
 
 
main()

Submission status: Accepted

Solution code:
from itertools import permutations

def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, m, r = read_line(int, int, int)

rs = [int(r) for r in input().split()]

costs = {}
for i in range(n + 1):
    costs[i] = {}
    for j in range(n + 1):
        costs[i][j] = float('inf')

for _ in range(m):
    a, b, c = read_line(int, int, int)

    costs[a][b] = costs[b][a] = c

for k in range(n + 1):
    for i in range(n + 1):
        for j in range(n + 1):
            c = costs[i][k] + costs[k][j]
            if costs[i][j] > c:
                costs[i][j] = c

def cost(selected):
    c = 0
    for i in range(len(selected) - 1):
        a = selected[i]
        b = selected[i + 1]
        c += costs[a][b]
    return c

smallest = float('inf')

for p in permutations(rs):
    c = cost(p)
    if smallest > c:
        smallest = c

print(smallest)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import permutations
import heapq

INF = float('inf')
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
memo = [[INF for _ in range(N)] for _ in range(N)]

Adj_list = defaultdict(set)

for i in range(M):
    a, b, c = map(int, input().split())
    if memo[a-1][b-1]:
        memo[a-1][b-1] = min(memo[a-1][b-1], c)
        
    Adj_list[a-1].add((b-1, memo[a-1][b-1]))
    Adj_list[b-1].add((a-1, memo[a-1][b-1]))


def dijkstra(x, vertex):
    d = [INF] * x
    d[vertex] = 0
    hq = [(0, vertex)]
    
    while hq:
        u = heapq.heappop(hq)[1]
        for (v, c) in Adj_list[u]:
            if d[v] > d[u] + c:
                d[v] = d[u] + c
                heapq.heappush(hq, (d[u]+c, v))

    return d

ans = INF
t_dis = 0

table = {}
for i in r:
    table[i-1] = dijkstra(N, i-1)

for each in permutations(r):
    t_dis = 0
    for i in range(R-1):
        t_dis += table[each[i]-1][each[i+1]-1]
    #print(each, t_dis)
    ans = min(ans, t_dis)

print(ans)

Submission status: Accepted

Solution code:
import copy
import sys
import numpy as np
import heapq

from math import *
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

class node_cost:
    def __init__(self, point, cost):
        self.point = point
        self.cost = cost

    def __lt__(self, other):
        return self.cost < other.cost

class Dijkstra:
    def __init__(self):
        self.table = {}

    def execute(self, adj_list, start):
        confirm_set = set()
        cost_dict = {}
        cost_dict[start] = 0
        #heapq.heapify

        n = node_cost(start, 0)
        node_list = [n]
        while len(node_list) > 0:
            n = heapq.heappop(node_list)
            if n.point in confirm_set:
                continue;
            confirm_set.add(n.point)
            self.table[(start, n.point)] = n.cost
            #self.table[(n.point, start)] = n.cost
            for v in adj_list[n.point]:
                if v[0] not in confirm_set:
                    if v[0] not in cost_dict:
                        cost_dict[v[0]] = n.cost + v[1]
                        heapq.heappush(node_list, node_cost(v[0], cost_dict[v[0]]))
                    else:
                        if n.cost + v[1] < cost_dict[v[0]]:
                            cost_dict[v[0]] = n.cost + v[1]
                            heapq.heappush(node_list, node_cost(v[0], cost_dict[v[0]]))

class DFS:
    def __init__(self, visitable_list, cost_table):
        self.visitable_list = visitable_list
        self.cost_table = cost_table
        self.done_list = set([])
        self.min_cost = sys.maxint

    def execute(self, now_cost, now_v):
        if len(self.done_list) == len(self.visitable_list):
            if now_cost < self.min_cost:
                self.min_cost = now_cost
            return

        for v in self.visitable_list:
            if v not in self.done_list:
                self.done_list.add(v)
                if now_v == 0:
                    self.execute(0, v)
                else:
                    self.execute(now_cost + self.cost_table[(now_v, v)], v)
                self.done_list.remove(v)




def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M, R] = [int(input_raw[0]), int(input_raw[1]), int(input_raw[2])]
    input_raw = read_func()
    input_str = input_raw.strip().split()
    visit_list = []
    for i in range(R):
        visit_list.append(int(input_str[i]))

    adj_list = {}
    for i in range(M):
        input_raw = read_func().strip().split()
        [A, B, C] = [int(input_raw[0]), int(input_raw[1]), int(input_raw[2])]
        if A not in adj_list:
            adj_list[A] = []
        if B not in adj_list:
            adj_list[B] = []
        adj_list[A].append((B, C))
        adj_list[B].append((A, C))


    D = Dijkstra()
    for v in visit_list:
        D.execute(adj_list, v)
    #print D.table

    dfs = DFS(visit_list, D.table)
    dfs.execute(0, 0)
    print dfs.min_cost

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import permutations


# sys.stdin = open('d1.in')


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


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


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

    n, m, r = read_int_list()
    v = read_int_list()
    v = [x - 1 for x in v]
    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 = read_int_list()
        a -= 1
        b -= 1
        d[a][b] = c
        d[b][a] = c
    floyd_warshall()
    res = float('inf')
    for p in permutations(v):
        s = 0
        for i in range(r - 1):
            s += d[p[i]][p[i + 1]]
        if s < res:
            res = s
    print(res)


main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
import itertools
from collections import defaultdict


def dijkstra(roads, st, ed, n):
    length = [float("inf") if i != st else 0 for i in range(n + 1)]
    q = set(range(n + 1))
    while len(q) != 0:
        a, ml = min([(i, x) for i, x in enumerate(length) if i in q], key=lambda x: x[1])
        q.remove(a)
        for b, l in roads[a].items():
            if length[b] > l + ml:
                length[b] = l + ml
    return length[ed]


def main():
    n, m, r = [int(i) for i in sys.stdin.readline().rstrip().split(" ")]
    target = set([int(i) for i in sys.stdin.readline().rstrip().split(" ")])
    roads = defaultdict(lambda: defaultdict(lambda: 100001))
    for line in sys.stdin:
        a, b, l = map(int, line.rstrip().split(" "))
        if roads[a][b] <= l:
            continue
        else:
            roads[a][b] = l
            roads[b][a] = l

    m_roads = defaultdict(lambda: defaultdict(lambda: 100001))
    for a, b in itertools.combinations(target, 2):
        l = dijkstra(roads, a, b, n)
        m_roads[a][b] = l
        m_roads[b][a] = l

    ans = float("inf")
    for seq in itertools.permutations(target):
        l = 0
        for i in range(len(seq) - 1):
            a = seq[i]
            b = seq[i + 1]
            l += m_roads[a][b]
        ans = min(ans, l)

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from scipy.sparse import*;f=lambda*z:map(int,raw_input().split());N,M,R=f();r=f();a,b,c=list(zip(*map(f,[0]*M)));a=csgraph.dijkstra(csr_matrix((c,(a,b)),[N+1]*2),0,r);print int(min(sum(a[e[i]][r[e[i+1]]]for i in range(R-1))for e in __import__('itertools').permutations(range(R))))

Submission status: Accepted

Solution code:
import itertools

inf = 10 ** 12

n, m, r = map(int, input().split())
n += 1
rl = [int(i) for i in input().split()]
d = [[inf for _ in[0]*n] for _ in[0]*n]

for _ in[0]*m:
    f, t, c = map(int, input().split())
    d[f][t], d[t][f] = c, c

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

ans = inf
for arr in itertools.permutations(rl):
    ans = min(ans, sum([d[arr[i]][arr[i+1]] for i in range(0, r-1)]))
print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse import*
N,M,R=map(int,raw_input().split())
r=[int(e) for e in raw_input().split()]
a,b,c=zip(*(map(int,raw_input().split())for _ in range(M)))
a=csgraph.dijkstra(csr_matrix((c,(a,b)),[N+1]*2),0,r)
print int(min(sum(a[e[i]][r[e[i+1]]]for i in range(R-1))for e in __import__('itertools').permutations(range(R))))

Submission status: Accepted

Solution code:
N,M,R = map(int,input().split())
r = list(map(int,input().split()))
from itertools import permutations
from scipy.sparse.csgraph import dijkstra
t = [[float('inf') for i in range(N)] for j in range(N)]

for i in range(M):
    a,b,c = map(int, input().split())
    t[a-1][b-1] = t[b-1][a-1] = c
t=dijkstra(t).astype(int)
def c(l):
    ret = 0
    for i in range(R-1):
        ret += t[l[i]-1][l[i+1]-1]
    return ret

print(min([c(i) for i in permutations(r)]))

Submission status: Accepted

Solution code:
import itertools

inf = 10 ** 12

n, m, r = map(int, input().split())
n += 1
rl = [int(i) for i in input().split()]
d = [[inf for _ in[0]*n] for _ in[0]*n]

for _ in[0]*m:
    f, t, c = map(int, input().split())
    d[f][t] = c
    d[t][f] = c

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

ans = inf
for arr in itertools.permutations(rl):
    t = 0
    for i in range(0, r-1):
        t += d[arr[i]][arr[i+1]]
    ans = min(ans, t)
print(ans)