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:
import heapq
from collections import defaultdict
import itertools

N, M, R = list(map(int, input().split()))
Rlist = list(map(int, input().split()))
RX = []

graph = defaultdict(list)

for i in range(M):
	a, b, w = list(map(int, input().split()))
	graph[a - 1].append([b - 1, w])
	graph[b - 1].append([a - 1, w])


for i in range(R):
	dist_node = [float("inf") for j in range(N)]
	dist_node[Rlist[i] - 1] = 0
	Q = []
	heapq.heappush(Q, (dist_node[Rlist[i] - 1], Rlist[i] - 1))

	while Q:
		dis, v = heapq.heappop(Q)
		if dist_node[v] < dis:
			continue
		for u, w in graph[v]:
			alt = dis + w
			if dist_node[u] > alt:
				dist_node[u] = alt
				heapq.heappush(Q, (alt, u))
	RX.append([dist_node[Rlist[k] - 1] for k in range(R)])
	
ans = float("inf")
nl = [i for i in range(R)]
pl = list(itertools.permutations(nl, R))
for i in pl:
	xx = 0
	for j in range(R - 1):
		xx += RX[i[j]][i[j + 1]]

	if xx < ans: 
		ans = xx

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from scipy.sparse.csgraph import floyd_warshall
import itertools

from pprint import pprint as pp
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
ABC = [list(map(int, input().split())) for _ in range(M)]

graph = [[float('inf') for _ in range(N)] for _ in range(N)]
for i in range(M):
    x, y, c = ABC[i]
    x -= 1
    y -= 1
    graph[x][y] = c
    graph[y][x] = c

dist = floyd_warshall(graph, directed=False)

ans = []
for rlist in itertools.permutations(r, len(r)):
    tmp = 0
    for r,n in zip(rlist,rlist[1:]):
        tmp += dist[r-1,n-1]
    ans.append(tmp)

print(int(min(ans)))

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall
from itertools import permutations
n,m,r=map(int, input().split())
s=[[10**9]*n for i in range(n)]
t=list(map(int, input().split()))
for i in range(m):
    a,b,c=map(int, input().split())
    s[a-1][b-1]=c
    s[b-1][a-1]=c

s=floyd_warshall(s)   
ans=float('inf')
for i in permutations(t):
    an=0
    for j in range(r-1):
        an+=s[i[j]-1][i[j+1]-1]
    ans=min(ans,an)
print(int(ans))

Submission status: Accepted

Solution code:
n,m,r=map(int, input().split())
s=[[10**9]*n for i in range(n)]
t=list(map(int, input().split()))
for i in range(m):
    a,b,c=map(int, input().split())
    s[a-1][b-1]=c
    s[b-1][a-1]=c
 
for k in range(n):
    for i in range(n):
        for j in range(n):
            s[i][j]=min(s[i][j],s[i][k]+s[k][j])
ans=float('inf')
from itertools import permutations
for i in permutations(t):
    an=0
    for j in range(r-1):
        an+=s[i[j]-1][i[j+1]-1]
    ans=min(ans,an)
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
import math
import itertools

input = sys.stdin.readline

def make_Graph(N, edges):#頂点の名前はi - 1で受け付ける
    graph = {}
    for i in range(N):
        graph[i] = {}
        for j in range(N):
            graph[i][j] = 0
    for edge in edges:
        a, b, c = edge
        graph[a][b] = c
        graph[b][a] = c
    return graph

def Dijkstra(graph, start):
    N = len(graph)
    d = {}
    prev = {}
    for i in range(N):
        prev[i] = None
        if i == start:
            d[i] = 0
        else:
            d[i] = float('inf')
    Q = []
    heapq.heappush(Q, (0, start))
    while Q:
        d_u, u = heapq.heappop(Q)
        if d[u] < d_u:#ダブりを回避
            continue
        for i in range(N):
            if graph[u][i]:
                temp = d_u + graph[u][i]
                if d[i] > temp:
                    d[i] = temp
                    prev[i] = u
                    heapq.heappush(Q, (d[i], i))
    return (d, prev)

def saitan(start, goal, d, prev):
    temp = goal
    res = [goal]
    while True:
        res.append(prev[temp])
        if prev[temp] == start:
            break
        else:
            temp = prev[temp]
    return res

N,M,rr = (int(i) for i in input().split())
R = [int(i)-1 for i in input().split()]
edges = []
for i in range(M):
    a,b,c = (int(i) for i in input().split())
    edges.append((a-1, b-1, c))

graph = make_Graph(N, edges)

r_edges = []
for r1 in R:
    d, prev = Dijkstra(graph, r1)
    for r2 in R:
        (a,b,c) = r1, r2, d[r2]
        r_edges.append((a,b,c))

r_graph = make_Graph(N, r_edges)

reslis = []
for LL in list(itertools.permutations(R)):
    res = 0
    for i in range(len(LL)-1):
        a, b = (LL[i], LL[i + 1])
        res += r_graph[a][b]
    reslis.append(res)

reslis.sort()
res = reslis[0]
print(res)

Submission status: Accepted

Solution code:
import sys,itertools as o,scipy.sparse as s;_,r,*t=[map(int,i.split())for i in sys.stdin];a,b,c=zip(*t);l=s.csgraph.dijkstra(s.csr_matrix((c,(a,b)),[201]*2),0);print(min(sum(int(l[i][j])for i,j in zip(a,a[1:]))for a in o.permutations(r)))

Submission status: Accepted

Solution code:
import itertools
N,M,R = map(int,input().split())
r = list(map(int,input().split()))
INF = float('inf')
d = [[INF for i in range(N)] for i in range(N)]
for i 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):
            d[i][j] = min(d[i][j],d[i][k]+d[k][j])
ans = INF
for l in list(itertools.permutations(r)):
    tmp = 0
    for i in range(R-1):
        tmp += d[l[i]-1][l[i+1]-1]
    ans = min(tmp,ans)
print(ans)

Submission status: Accepted

Solution code:
import itertools
N,M,R=map(int,input().split())
towns=[int(i) for i in input().split()]
path=[[10**20]*N for i in range(N)]
for i in range(N):
  path[i][i]=0
for i in range(M):
  a,b,c=map(int,input().split())
  path[a-1][b-1]=c
  path[b-1][a-1]=c

for k in range(N):
  for i in range(N):
    for j in range(i):
      path[i][j]=min(path[i][j],path[i][k]+path[k][j])
      path[j][i]=path[i][j]   
Roots=list(itertools.permutations(towns))
ans=10**20
s=0
for r in Roots:
  for n in range(R-1):
    s+=path[r[n]-1][r[n+1]-1]
  ans=min(ans,s)
  s=0
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

n,m,r = map(int,input().split())
R = list(map(int,input().split()))
inf = 10**9

edges=[[inf for i in range(n+1)] for i in range(n+1)]

for i in range(m):
  a,b,c = map(int,input().split())
  edges[a][b] = c
  edges[b][a] = c


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


ans = inf
for i in permutations(R):
  tmp = 0
  for j in range(r-1):
    tmp += edges[i[j]][i[j+1]]
  ans = min(tmp, ans)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

#dojkstra
import itertools
import queue
G=[]
#infの値に注意
inf=3*10**15
V, E, R=map(int,input().strip().split(' '))
rlis=list(map(int,input().strip().split(' ')))

cost=[[inf]*V for i in range(V)]
for i in range(E):
    fr, to, co=map(int,input().strip().split(' '))
    cost[fr-1][to-1]=co
    cost[to-1][fr-1]=co
def dijkstra(s):
    d=[inf]*V
    used=[False]*V
    d[s]=0
    while True:
        v=-1
        for u in range(V):
            if used[u]==False and(v==-1 or d[u]<d[v]):
                v=u
        if v==-1:
            break
        used[v]=True
        for u in range(V):
            d[u]=min(d[u],d[v]+cost[v][u])
    return d

dist=[None] * V
for i in rlis:
    dist[i-1]=dijkstra(i-1)

ans=inf
for rperm in itertools.permutations(rlis):
    a_tmp=0
    for j in range(R-1):
        a_tmp+=dist[rperm[j]-1][rperm[j+1]-1]
    ans=min(ans,a_tmp)

print(ans)

Submission status: Accepted

Solution code:
N,M,R = map(int,input().split())
r = list(map(int,input().split()))
ABC = []
for i in range(M):
    ABC.append(list(map(int,input().split())))

V = [ i for i in range(1,N+1)]
E =[[100000000 for j in range(N+1)] for i in range(N+1)]
for i in range(N+1):
    E[i][i] = 0

for i in range(M):
    E[ABC[i][0]][ABC[i][1]] = ABC[i][2]
    E[ABC[i][1]][ABC[i][0]] = ABC[i][2]


def warshall_floyd(V,E):
    d = E
    for k in V:
        for i in V:
            for j in V:
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]

    return d

W = warshall_floyd(V,E)

import itertools
ans = 10000000000000
for val in list(itertools.permutations(r,len(r))):
    tmp = 0
    for i in range(len(val) - 1):
        tmp += W[val[i]][val[i+1]]
    if ans > tmp:
        ans = tmp
print(ans)

Submission status: Accepted

Solution code:
import sys, heapq, itertools
input = sys.stdin.readline
inf = float('inf')
N, M, R = map(int, input().split())
r = list(map(lambda x: int(x)-1, input().split()))

sec = [[inf] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j:
            sec[i][j] == 0
for abc in [list(map(int, input().split())) for _ in range(M)]: 
    sec[abc[0]-1][abc[1]-1] = abc[2]
    sec[abc[1]-1][abc[0]-1] = abc[2]
def marsh():
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if sec[i][j] > sec[i][k] + sec[k][j]:
                    sec[i][j] = sec[i][k] + sec[k][j]
marsh()
cost = inf
for perm in itertools.permutations(r):
    temp = 0
    for i in range(R-1):
        temp += sec[perm[i]][perm[i+1]]
    if temp < cost:
        cost = temp

print(cost)

Submission status: Accepted

Solution code:
def wf(N, cost):
    for k in range(N):
        for i in range(N):
            c_ik = cost[i][k]
            for j, (c_kj, c_ij) in enumerate(zip(cost[k], cost[i])):
                temp = c_ik + c_kj
                if temp < c_ij:
                    cost[i][j] = temp

import sys
import itertools
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
cost = [[float("inf")] * N for _ in range(N)]

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

for _ in range(M):
    A, B, C = map(int, sys.stdin.readline().split())
    cost[A - 1][B - 1] = C
    cost[B - 1][A - 1] = C

wf(N, cost)

ans = float('inf')
for place in itertools.permutations(r):
    temp_cost = 0
    current_place = place[0]
    for next_place in place[1:]:
        temp_cost += cost[current_place - 1][next_place - 1]
        current_place = next_place

    if temp_cost < ans:
        ans = temp_cost

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

def wfa(N):
    for i in range(N + 1):
        for j in range(N + 1):
            w_ji = way[j][i]
            for k, (w_ik, w_jk) in enumerate(zip(way[i], way[j])):
                if k == 0:
                    continue
                tmp = w_ji + w_ik
                if w_jk > tmp:
                    way[j][k] = tmp


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

way = [[float("inf") if i != j else 0 for i in range(N + 1)] for j in range(N + 1)]
for m in range(M):
    a, b, c = map(int, input().split())
    way[a][b] = c
    way[b][a] = c

wfa(N)

ans = float("inf")
for path in permutations(r):
    time = 0
    for i in range(len(path) - 1):
        time += way[path[i]][path[i + 1]]
    ans = min(ans, time)
print(ans)

Submission status: Accepted

Solution code:
def wf(N, cost):
    for k in range(N):
        for i in range(N):
            c_ik = cost[i][k]
            for j, (c_kj, c_ij) in enumerate(zip(cost[k], cost[i])):
                temp = c_ik + c_kj
                if temp < c_ij:
                    cost[i][j] = temp

import sys
import itertools
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
cost = [[float("inf")] * N for _ in range(N)]
for _ in range(M):
    A, B, C = map(int, sys.stdin.readline().split())
    cost[A - 1][B - 1] = C
    cost[B - 1][A - 1] = C

wf(N, cost)

ans = float('inf')
for place in itertools.permutations(r):
    temp_cost = 0
    current_place = place[0]
    for next_place in place[1:]:
        temp_cost += cost[current_place - 1][next_place - 1]
        current_place = next_place

    if temp_cost < ans:
        ans = temp_cost

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

n, m, R = map(int, input().split())
r = list(map(int, input().split()))

INF = 10 ** 9

d = [[INF for _ in range(n)] for _ in range(n)]
p = [[] for _ in range(n)]

for i in range(n):
    d[i][i] = 0

for i in range(R):
    r[i] -= 1

for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = c
    p[a].append(b)
    p[b].append(a)

#for q in d: print(q)

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

ans = INF
for x in permutations(r):
    temp = 0
    for i in range(R-1):
        temp += d[x[i]][x[i+1]]
    ans = min(temp, ans)

print(ans)

Submission status: Accepted

Solution code:
import heapq
INF=10**15
class weighted_graph():
    Vertex= 1
    AdjList=[dict() for i in range(Vertex)]
    Edge=[]
    directed=False
    def __init__(self,size,directed=False):
        self.directed=directed
        self.Vertex=size
        self.AdjList=[dict() for i in range(self.Vertex)]
    def add_edge(self,start,finish,weight):
        self.AdjList[start][finish]=weight
        self.Edge.append((start,finish,weight))
        if not(self.directed):
            self.AdjList[finish][start]=weight
    def dijkstra(self, st):
        dist=[INF for i in range(N)]
        dist[st]=0
        q=[]
        heapq.heappush(q,(0,st))
        while (len(q)!=0):
            prc,src=heapq.heappop(q)
            if dist[src]<prc:
                continue
            for dest in self.AdjList[src]:
                cost=self.AdjList[src][dest]
                if dist[dest]>dist[src]+cost:
                    dist[dest]=dist[src]+cost
                    heapq.heappush(q,(dist[dest],dest))                
        return dist
    def Warshall_Floyd(self):
        d=[[INF for i in range(self.Vertex)] for i in range(self.Vertex)]
        for seq in self.Edge:
            d[seq[0]][seq[1]]=seq[2]
            if not(self.directed):
                d[seq[1]][seq[0]]=seq[2]
        for k in range(self.Vertex):
            for i in range(self.Vertex):
                for j in range(self.Vertex):
                    if d[i][j]>d[i][k]+d[k][j]:
                        d[i][j]=d[i][k]+d[k][j]
        return d
import itertools
N,M,R=map(int,input().split())
r=[int(i)-1 for i in input().split()]
G=weighted_graph(N,directed=False)
for i in range(M):
    a,b,c=map(int,input().split())
    G.add_edge(a-1,b-1,c)
dist=G.Warshall_Floyd()
S=itertools.permutations(r,R)
ans=INF
for seq in S:
    tmp=0
    for i in range(R-1):
        tmp+=dist[seq[i]][seq[i+1]]
    ans=min(tmp,ans)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
N, M, R = map(int, input().split())
r = list(map(lambda x: int(x) - 1, input().split()))
G = [[float('inf')] * N for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    G[a][b] = c
    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])

# 街の訪れ方を全探索
ans = float('inf')
for perm in permutations(r):
    tmp = 0
    for i in range(R - 1):
        tmp += G[perm[i]][perm[i + 1]]
    ans = min(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
def inpl(): return [int(i) for i in input().split()]
import heapq
from itertools import permutations

N, M, R = inpl()
r = inpl()
for i in range(R):
    r[i] -= 1
inf = float('inf')
Q = [[inf] * N for _ in range(N)]
path = [[0] * N for _ in range(N)]

for i in range(M):
    A,B,C = inpl()
    path[A-1][B-1] = path[B-1][A-1] = C

for i in r:
    decided = [False for _ in range(N)]
    H = []
    ctr = 0
    Q[i][i] = 0
    heapq.heappush(H,(0,i))
    while ctr != N:
        while True:
            k = heapq.heappop(H)
            k = k[1]
            if not decided[k]:
                decided[k] = True
                ctr += 1
                break
        for j in range(N):
            if path[k][j] == 0:
                continue
            if decided[j]:
                continue
            Q[i][j] = min(Q[i][k] + path[k][j], Q[i][j])
            heapq.heappush(H,(Q[i][j],j))

Ans = inf
for i in permutations(r):
    ans = 0
    for j in range(R-1):
        ans += Q[i[j]][i[j+1]]
    Ans = min(Ans,ans) 
        
print(Ans)

Submission status: Accepted

Solution code:
from itertools import permutations
from scipy.sparse.csgraph import floyd_warshall as ws

def search(r,dist,ans):
    sum_=0
    for i in range(1,len(r)):
        sum_+=dist[r[i-1]][r[i]]
    return sum_

N,M,R=list(map(int,input().split()))
r=list(map(int,input().split()))
r=[x-1 for x in r]
dist=[[float('inf') for _ in range(N)] for _ in range(N)]
for i in range(M):
    A,B,C=list(map(int,input().split()))
    dist[A-1][B-1]=C
    dist[B-1][A-1]=C
for i in range(N):
    dist[i][i]=0
dist=ws(dist)

ans=float('inf')

ans=float('inf')
r=permutations(r)
for x in r:
    ans=min(ans,search(x,dist,0))
print(int(ans))

Submission status: Accepted

Solution code:
n,m,r=map(int,input().split())
r=list(map(int,input().split()))
r=[t-1 for t in r]
abc=[list(map(int,input().split())) for _ in range(m)]
d=[[2**30 for _ in range(n)] for _ in range(n)]
for t in abc:
    d[t[0]-1][t[1]-1]=t[2]
    d[t[1]-1][t[0]-1]=t[2]
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])
from itertools import permutations
res=[]
for t in permutations(r):
    ans=0
    for i in range(1,len(r)):
        ans+=d[t[i-1]][t[i]]
    res.append(ans)
print(min(res))

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall as fw
import numpy as np
N,M,R = map(int,input().split())
r = list(map(int,input().split()))
edge = [[np.inf for i in range(N+1)] for i in range(N+1)]
for i in range(M):
    A,B,C = map(int,input().split())
    edge[A][B] = C
    edge[B][A] = C
cost = fw(edge)
cd = {}
for r_ in r:
    cd[r_] = {}
for r_ in r:
    for r__ in r:
        cd[r_][r__] = cost[r_][r__]
import itertools
ans = np.inf
for rp in itertools.permutations(r):
    c = 0
    for i in range(R-1):
        c += cd[rp[i]][rp[i+1]]
    if c < ans:
        ans = c
print(int(ans))

Submission status: Accepted

Solution code:
import itertools
import heapq
N, M, R = map(int, input().split())
Visit = [int(i) for i in input().split()]
for i in range(R):
    Visit[i] -= 1
P = [[] for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    P[a-1].append((c, b-1))
    P[b-1].append((c, a-1))

def Dijk(i):
    Fin = [False for i in range(N)]
    Cost = [float("inf") for i in range(N)]
    Cost[i] = 0
    Q = [(0, i)]
    heapq.heapify(Q)
    while Q:
        cost, node = heapq.heappop(Q)
        if Fin[node] == False:
            Fin[node] = True
            for next in P[node]:
                if Fin[next[1]] == False:
                    if next[0] + cost < Cost[next[1]]:
                        Cost[next[1]] = next[0] + cost
                        heapq.heappush(Q, (Cost[next[1]], next[1]))
    return Cost

E = []
for i in range(N):
    E.append(Dijk(i))

ans = float("inf")
for Order in itertools.permutations(Visit):
    temp = 0
    for i in range(R-1):
        temp += E[Order[i]][Order[i+1]]
    if temp < ans:
        ans = temp
print(ans)

Submission status: Accepted

Solution code:
import itertools

N, M, R = [int(i) for i in input().split()]
rr = [int(i) for i in input().split()]

d = [[1 << 60 for j in range(N)] for i 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]

ans = 1 << 60
for plan in itertools.permutations(rr):
    cnt = 0
    for i in range(R - 1):
        cnt += d[plan[i] - 1][plan[i + 1] - 1]
    ans = min(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
from scipy.sparse import csgraph, csr_matrix
N, M, R = map(int, input().split())
r = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(M)]
a, b, c = zip(*edges)
graph = csgraph.dijkstra(csr_matrix((c, (a, b)), shape=(N + 1, N + 1)),
                         directed=False)
ans = 10 ** 18
for p in permutations(r):
    ans = min(ans, sum(int(graph[i][j]) for i, j in zip(p, p[1:])))
print(ans)

Submission status: Accepted

Solution code:
def ABC073D():
    N, M, R = map(int, input().split())
    r = list(map(int, input().split()))
    ABC = [list(map(int, input().split())) for i in range(M)]
    root = [[1000000000 for i in range(N)] for j in range(N)]
    for i, j, k in ABC:
        root[i - 1][j - 1] = k
        root[j - 1][i - 1] = k

    import itertools
    def kumiawase(list_name):  # list_name(リスト)のすべての並び替え
        return itertools.permutations(list_name)


    from scipy.sparse import csgraph
    root = csgraph.floyd_warshall(root)

    a = kumiawase(r)
    ans = float("inf")
    for i in a:
        key = 0
        for j in range(len(i) - 1):
            key += root[i[j] - 1][i[j + 1] - 1]
        if ans > key:
            ans = int(key)
    #print(root)
    print(ans)
ABC073D()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Oct  7 22:06:12 2018
ABC073D
@author: maezawa
"""
import itertools as itr
import sys
input = sys.stdin.readline

def wf(graph):
    """ Warshall-Floyd Algorithm """
    for k in range(len(adjmatrix)):
        for i in range(len(adjmatrix)):
            for j in range(len(adjmatrix[i])):
                if adjmatrix[i][j] > adjmatrix[i][k] + adjmatrix[k][j]:
                    adjmatrix[i][j] = adjmatrix[i][k] + adjmatrix[k][j]
                    adjmatrix[j][i] = adjmatrix[i][k] + adjmatrix[k][j]				
    #return graph

n, m, r = list(map(int, input().split()))
rarray = list(map(int, input().split()))
adjmatrix = [[float("inf")]*n for _ in range(n)]
#for i in range(n):
#    adjmatrix[i][i] = 0

for i in range(m):
    a, b, c = list(map(int, input().split()))
    adjmatrix[a-1][b-1] = c
    adjmatrix[b-1][a-1] = c

#print(abc)

#costmatrix = wf(adjmatrix)
wf(adjmatrix)
        
#print(*adjmatrix, sep='\n')
    
# search for ri to rj
mincnt = float("inf")
for route in itr.permutations(rarray):
    cnt = 0
    for i in range(len(route)-1):
        cnt += adjmatrix[route[i]-1][route[i+1]-1]
    if cnt < mincnt:
        mincnt = cnt

print(mincnt)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Oct  7 22:06:12 2018
ABC073D
@author: maezawa
"""
import itertools as itr
import sys
input = sys.stdin.readline

def wf(graph):
    """ Warshall-Floyd Algorithm """
    for k in range(len(adjmatrix)):
        for i in range(len(adjmatrix)):
            for j in range(len(adjmatrix[i])):
                if adjmatrix[i][j] > adjmatrix[i][k] + adjmatrix[k][j]:
                    adjmatrix[i][j] = adjmatrix[i][k] + adjmatrix[k][j]
                    adjmatrix[j][i] = adjmatrix[i][k] + adjmatrix[k][j]				
    return graph

n, m, r = list(map(int, input().split()))
rarray = list(map(int, input().split()))
adjmatrix = [[float("inf")]*n for _ in range(n)]
#for i in range(n):
#    adjmatrix[i][i] = 0

for i in range(m):
    a, b, c = list(map(int, input().split()))
    adjmatrix[a-1][b-1] = c
    adjmatrix[b-1][a-1] = c

#print(abc)

costmatrix = wf(adjmatrix)
        
#print(*adjmatrix, sep='\n')
    
# search for ri to rj
mincnt = float("inf")
for route in itr.permutations(rarray):
    cnt = 0
    for i in range(len(route)-1):
        cnt += costmatrix[route[i]-1][route[i+1]-1]
    if cnt < mincnt:
        mincnt = cnt

print(mincnt)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Oct  8 10:17:39 2018

@author: maezawa
"""

from itertools import permutations

#フロイド・ワーシャル
def warshall_floyd(glath):
	
	for k in range(len(glath)):
		for i in range(len(glath)):
			for j in range(len(glath[i])):
				if glath[i][j] > glath[i][k] + glath[k][j]:
                                   glath[i][j] = glath[i][k] + glath[k][j]
                                   glath[j][i] = glath[i][k] + glath[k][j]				
	return glath

N, M ,R= [int(x) for x in str(input()).split()]  #グラフの大きさ 
r=[int(x) for x in str(input()).split()]
graph=[[float("inf")]*N for i in range(N)]


for i in range(M):
	a,b,c=[int(x) for x in str(input()).split()]
	#if a in r and b in r:
	graph[a-1][b-1]=c
	graph[b-1][a-1]=c

#all_cost=warshall_floyd(select_graph)
all_cost=warshall_floyd(graph)


max_count=float("inf")
for i in permutations(r):
        cost=0
        for j in range(len(i)-1):                
                cost+= all_cost[i[j]-1][i[j+1]-1]       
        max_count=min(max_count,cost)

print(max_count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Oct  8 10:17:39 2018

@author: maezawa
"""

import math
from itertools import permutations

#フロイド・ワーシャル
def warshall_floyd(glath):
	
	for k in range(len(glath)):
		for i in range(len(glath)):
			for j in range(len(glath[i])):
				if glath[i][j] > glath[i][k] + glath[k][j]:
                                   glath[i][j] = glath[i][k] + glath[k][j]
                                   glath[j][i] = glath[i][k] + glath[k][j]				
	return glath

N, M ,R= [int(x) for x in str(input()).split()]  #グラフの大きさ 
r=[int(x) for x in str(input()).split()]
graph=[[float("inf")]*N for i in range(N)]


for i in range(M):
	a,b,c=[int(x) for x in str(input()).split()]
	#if a in r and b in r:
	graph[a-1][b-1]=c
	graph[b-1][a-1]=c

#all_cost=warshall_floyd(select_graph)
all_cost=warshall_floyd(graph)


max_count=float("inf")
for i in permutations(r):
        cost=0
        for j in range(len(i)-1):                
                cost+= all_cost[i[j]-1][i[j+1]-1]       
        max_count=min(max_count,cost)

print(max_count)

Submission status: Accepted

Solution code:
from itertools import permutations

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

INF = float('inf')
graph = [[INF for i in range(N)] for j in range(N)]
for i in range(M):
    A, B, C = map(int, input().split())
    graph[A-1][B-1] = C
    graph[B-1][A-1] = C

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

for k in range(N):
    for i in range(N):
        for j in range(N):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

ans = 10**9
for p in permutations(r, len(r)):
    dist = 0
    flag = 0
    for i in range(len(r) - 1):
        if graph[p[i]-1][p[i+1]-1] == INF:
            flag = 1
            continue
        dist += graph[p[i]-1][p[i+1]-1]
    if flag == 0:
        ans = min(ans, dist)

print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import permutations
from heapq import heappush, heappop

def dijkstra(graph:list, node:int, start:int) -> list:
    # 未探索のノードは距離INF
    INF = float("inf")
    dist = [INF]*node
    
    # 始点ノードの距離を0とし、dfsのためのpriority queを作成
    dist[start] = 0
    heap = [(0,start)]
    searched = [False for _ in range(node)]
    
    # 未探索のノードをpriority queueに入れる
    while heap:
        cost, cur_node = heappop(heap)
        
        if searched[cur_node] or cost > dist[cur_node]:
            continue
        
        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heappush(heap, (dist[nex_node], nex_node))
    
        searched[cur_node] = True
        
        if sum(searched) == node:
            break
    
    return dist

n,m,r = li()
r = list(li_())
graph = [[] for _ in range(n)]
for _ in range(m):
    a,b,c = li()
    a -= 1
    b -= 1
    graph[a].append((c,b))
    graph[b].append((c,a))
    
dists = []
for i in range(n):
    dists.append(dijkstra(graph, n, i))

ans = 2**64-1
for route in permutations(r):
    temp = 0
    for i in range(len(route)-1):
        temp += dists[route[i]][route[i+1]]
        
    ans = min(ans,temp)
    
print(ans)