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: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;
#define inf 1<<29

int n,m,r;
int d[201][201];
int a,b,c;
int res;

void warshall_floyd(int n) {
    //for (int i=0;i<n;i++) for (int j=0;j<n;j++) for (int k=0;k<n;k++) d[j][k]=min(d[j][k], d[j][i]+d[i][k]);
    for (int i=0;i<n;i++) for (int j=0;j<n;j++) for (int k=0;k<i+1;k++) d[j][k]=min(d[j][k], d[j][i]+d[i][k]);
}

int main(){
    scanf("%d %d %d",&n,&m,&r);
    vector<int> w(r);
    for (int i=0;i<r;i++) scanf("%d",&w[i]);
    sort(w.begin(),w.end());
    for (int i=0;i<201;i++) for (int j=0;j<201;j++) d[i][j]=inf;
    for (int i=0;i<m;i++) {
        scanf("%d %d %d",&a,&b,&c);
        d[a][b]=c;
        d[b][a]=c;
    }
    warshall_floyd(n+1);
    int ans=inf;
    do {
        int p,chk=0;
        for (int i=0;i<r;i++) {
            if (i==0) {
                p=w[i];
            } else {
                chk+=d[w[i]][p];
                p=w[i];
            }
        }
        ans=min(ans,chk);
    } while (next_permutation(w.begin(),w.end()));
    printf("%d\n",ans);
    return 0;
}

Submission status: Runtime Error

Solution code:
# ABC073 D - joisino's travel
import itertools
N,M,R=map(int, input().split())
r=list(map(int, input().split()))
inf=float("inf")
mat=[[inf]*N for _ in range(N)]
dist=[inf]*N
visited=[False]*N
for i in range(M):
    a,b,c=map(int,input().split())
    mat[a-1][b-1]=c
    mat[b-1][a-1]=c

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

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

for rr in itertools.permutations(r,R):
    t_sum=0
    for j in range(1,R):
        t_sum+=mat[rr[j-1]][rr[j]]
    ans=min(ans,t_sum)
print(int(ans))

Submission status: Runtime Error

Solution code:
# ABC073 D - joisino's travel
import itertools
N,M,R=map(int, input().split())
r=list(map(int, input().split()))
inf=float("inf")
mat=[[inf]*N for _ in range(N)]
dist=[inf]*N
visited=[False]*N
for i in range(M):
    a,b,c=map(int,input().split())
    mat[a-1][b-1]=mat[b-1][a-1]=c

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

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

for rr in itertools.permutations(r,R):
    t_sum=0
    for j in range(1,R):
        t_sum+=mat[rr[j-1]][rr[j]]
    ans=min(ans,t_sum)
print(int(ans))

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import floyd_warshall

def warshal_floyd(weights,N):
    d=[[weights[(i,j)] for i in range(N)] for j in range(N)]
    for i in range(N):
        d[i][i]=0
    for i in range(N):
        for j in range(N):
            for k in range(N):
                d[i][j]=min(d[i][j],d[i][k]+d[k][j])
    return d

def make_iteration(R,cities):
    S=[[c] for c in cities]
    iteration=[]
    while len(S)>0:
        v=S.pop()
        if len(v)!=len(set(v)):
            continue
        if len(v)==R:
            iteration.append(v)
        else:
            for c in cities:
                S.append(v+[c])
    return iteration

if __name__ == '__main__':
    N,M,R=list(map(int,input().split()))
    cities=list(map(int,input().split()))
    weights={(i,j):10**7 for i in range(N) for j in range(N)}
    #graph=[[10*7 for i in range(N)] for j in range(N)]
    for i in range(M):
        a,b,c=list(map(int,input().split()))
        a-=1
        b-=1
        weights[(a,b)]=min(weights[(a,b)],c)
        weights[(b,a)]=min(weights[(b,a)],c)
    d=warshal_floyd(weights,N)
    #d=floyd_warshall(weights)

    iteration=make_iteration(R,cities)
    mini_count=1e12
    for i in iteration:
        count=0
        for r in range(R-1):
            count+=d[i[r]-1][i[r+1]-1]
        mini_count=min(mini_count,count)
    print(mini_count)

Submission status: Runtime Error

Solution code:
import sys
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix
from itertools import permutations
read = sys.stdin.read
readline = sys.stdin.readline

N, M, R = map(int, readline().split())
r = list(map(int, readline().split()))
ABC = map(int, read().split())
A, B, C = map(list, zip(*zip(ABC, ABC, ABC)))

for i in range(N + 1):
    A.append(i)
    B.append(i)
    C.append(0)

csr = csr_matrix((C, (A, B)), (N + 1, N + 1))
distance = shortest_path(csr, directed=False)

answer = 10 ** 9
for tour in permutations(r):
    tmp = 0
    for i, j in zip(tour, tour[1:]):
        tmp += distance[i][j]

    if tmp < answer:
        answer = tmp

print(int(answer))

Submission status: Runtime Error

Solution code:
import sys
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix
from itertools import permutations
read = sys.stdin.read
readline = sys.stdin.readline

N, M, R = map(int, readline().split())
r = list(map(int, readline().split()))
ABC = map(int, read().split())
A, B, C = map(list, zip(*zip(ABC, ABC, ABC)))
A.append(0)
B.append(0)
C.append(0)

csr = csr_matrix((C, (A, B)), (N + 1, N + 1))
distance = shortest_path(csr, directed=False)

answer = 10 ** 9
for tour in permutations(r):
    tmp = 0
    for i, j in zip(tour, tour[1:]):
        tmp += distance[i][j]

    if tmp < answer:
        answer = tmp

print(int(answer))

Submission status: Runtime Error

Solution code:
import sys
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import coo_matrix
from itertools import permutations
read = sys.stdin.read
readline = sys.stdin.readline

N, M, R = map(int, readline().split())
r = list(map(int, readline().split()))
ABC = map(int, read().split())

INF = float('inf')

ABC = zip(ABC, ABC, ABC)
A, B, C = zip(*ABC)

csr = coo_matrix((C, (A, B)), (N + 1, N + 1))
distance = shortest_path(csr, directed=False)

answer = 10 ** 9
for tour in permutations(r):
    tmp = 0
    for i, j in zip(tour, tour[1:]):
        tmp += distance[i][j]

    if tmp < answer:
        answer = tmp

print(int(answer))

Submission status: Runtime Error

Solution code:
# ABC073D - joisino's travel
from heapq import heappop, heappush
from itertools import permutations
from typing import List, Tuple

INF = 1 << 30


def dijkstra(source: int, edges: List[Tuple[int, int]]) -> List[int]:
    """
    Compute the distance of the shortest path from V_source to each vertex.

    Args:
        source: V_source
        edges: Edges info
    Returns:
        dist: A list of distance from V_source
    """
    edges_count = len(edges)
    dist = [INF] * edges_count
    dist[source] = 0
    undetermined = edges_count - 1  # V_0 is determined in 1-idx graph
    queue = [(0, source)]
    while queue:
        cost, v = heappop(queue)
        if cost > dist[v]:
            continue
        for next_cost, u in edges[v]:
            if cost + next_cost < dist[u]:
                dist[u] = cost + next_cost
                heappush(queue, (dist[u], u))
        undetermined -= 1
        if not undetermined:
            break
    return dist  # There may be no path from V_source to some vertices.


def main():
    N, M, R, *RABC = map(int, open(0).read().split())
    visit, ABC = RABC[:R], RABC[R:]
    edges = [[] for _ in range(N + 1)]
    for v, u, cost in zip(*[iter(ABC)] * 3):
        edges[v].append((cost, u)), edges[u].append((cost, v))
    dist = {v: dijkstra(v, edges) for v in visit}
    ans = 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()

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import dijkstra,floyd_warshall
from scipy.sparse import csr_matrix
from  itertools import permutations

N,M,R=map(int,input().split())
r=[int(x)-1 for x in input().split()]
A=[]
B=[]
C=[]
for i in range(M):
    x,y,z=map(int,input().split())
    A.append(x-1)
    B.append(y-1)
    C.append(z)

d=csr_matrix((C,(A,B)),shape=(N,N))
tr=floyd_warshall(d)
ans=float('inf')

for tmp in permutations(r):
    cnt=0
    for i in range(len(r)-1):
        cnt+=tr[tmp[i]][tmp[i+1]]
    ans=min(ans,cnt)

print(int(ans))

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import dijkstra,floyd_warshall
from scipy.sparse import csr_matrix
from  itertools import permutations

N,M,R=map(int,input().split())
r=[int(x)-1 for x in input().split()]
A=[]
B=[]
C=[]
for i in range(M):
    x,y,z=map(int,input().split())
    A.append(x-1)
    B.append(y-1)
    C.append(z)

d=csr_matrix((C,(A,B)),shape=(N,N))
tr=floyd_warshall(d)

ans=float('inf')
for tmp in permutations(r):
    cnt=0
    for i in range(len(tmp)-1):
        cnt+=tr[tmp[i]][tmp[i+1]]
    ans=min(ans,cnt)

print(int(ans))

Submission status: Runtime Error

Solution code:
import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
ss = set(r)
d = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
  a, b, c = map(int, input().split())
  d[a][b] = c
  d[b][a] = c
res = float("inf")
for s in range(1, N + 1):
  dp = [[float("inf")] * (pow(2, R)) for _ in range(N + 1)]
  if s in r:
    dp[s][1 << bl(r, s)] = 0
  else: continue
  for i in range(1, N + 1):
    for j in range(pow(2, R)):
      for k in range(1, N + 1):
        x = bl(r, k)
        if j & (1 << x):
          continue
        #print(j, k, j + (1 << x))
        if k in ss:
          dp[k][j + (1 << x)] = min(dp[k][j + (1 << x)], dp[i][j] + d[i][k])
        else: dp[k][j] = min(dp[k][j], dp[i][j] + d[i][k])
  for i in range(1, N + 1):
    res = min(res, dp[i][-1])
print(res)

Submission status: Runtime Error

Solution code:
from collections import permutations
n,m,r=map(int,input().split())
rr=list(map(int,input().split()))
inf=10000000000
g=[[inf for i in range(n)] for j in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    g[a-1][b-1]=c
    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])


ans=10**10
for i in permutations(range(0,n),n):
    kai=0
    for j in range(n-1):
        kai+=g[rr[i[j]]][rr[i[j+1]]]
    ans=min(ans,kai)
print(ans)

Submission status: Runtime Error

Solution code:
ソースコード 

Copy
Copy
from scipy.sparse import *
from itertools import *
 
n,m,r = [int(x) for x in input().split()]
R = [int(i)-1 for i in input().split()]
route_list = [[0]*n for i in range(n)]
ans = 10**9
for j in range(m):
  a,b,c = map(int,input().split())
  route_list[a-1][b-1] = c
  route_list[b-1][a-1] = c
 
Co = csgraph.floyd_warshall(csr_matrix(route_list))
 
for v in permutations(R):
  temp = 0
  for i in range(1,r):
    temp += Co[v[i-1]][v[i]]
  ans = min(ans,temp)
print(int(ans))

Submission status: Runtime Error

Solution code:
ソースコード 

Copy
Copy
from scipy.sparse import *
from itertools import *
 
n,m,r = [int(x) for x in input().split()]
R = [int(i)-1 for i in input().split()]
route_list = [[10**8]*n for i in range(n)]
ans = 10**9
for j in range(m):
  a,b,c = map(int,input().split())
  route_list[a-1][b-1] = c
  route_list[b-1][a-1] = c
 
Co = csgraph.floyd_warshall(csr_matrix(route_list))
 
for v in permutations(R):
  temp = 0
  for i in range(1,r):
    temp += Co[v[i-1]][v[i]]
  ans = min(ans,temp)
print(int(ans))

Submission status: Runtime Error

Solution code:
import numpy
import sys
import itertools
input = sys.stdin.readline
inf = 200000000
n, m, r = map(int, input().split())
rs = list(map(int, input().split()))
n1 = n + 1
d = numpy.full((n1 * n1), inf)
for i in range(n1):
    d[i, i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    d[a * n1 + b] = d[b, + a] = c
for k, i, j in itertools.product(range(1, n1), repeat=3):
    d[i, j] = d[j, i] = min(
        d[i, j],
        d[i, k] + d[k, j])
s = inf
for q in itertools.permutations(range(r)):
    t = 0
    for i in range(r-1):
        t += d[rs[q[i]], rs[q[i+1]]]
    if s > t:
        s = t
print(s)

Submission status: Runtime Error

Solution code:
import math
from itertools import permutations
import numpy as np
#from scipy.sparse import*

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    n=len(d[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])
    return d

N,M,R=[int(x) for x in input().split()]
r=[int(x)-1 for x in input().split()]

#route_list=[[10*9]*N for i in range(N)]
route_list = np.full((N,N)10*8,dtype=np.int)


for i in range(M):
    a,b,c=[int(x) for x in input().split()]
    route_list[a-1][b-1]=c
    route_list[b-1][a-1]=c

wa_list=warshall_floyd(route_list)
ans=10**9

for perm in permutations(r):
    #print(perm)
    cur = sum(wa_list[v][u] for v, u in zip(perm, perm[1:]))
    ans = min(ans, cur)

print(ans)

Submission status: Runtime Error

Solution code:
import math
from itertools import permutations
import numpy as np
#from scipy.sparse import*

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    n=len(d[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])
    return d

N,M,R=[int(x) for x in input().split()]
r=[int(x)-1 for x in input().split()]

#route_list=[[10*9]*N for i in range(N)]
route_list = np.full(10*8,(N,N),dtype=np.int)


for i in range(M):
    a,b,c=[int(x) for x in input().split()]
    route_list[a-1][b-1]=c
    route_list[b-1][a-1]=c

wa_list=warshall_floyd(route_list)
ans=10**9

for perm in permutations(r):
    #print(perm)
    cur = sum(wa_list[v][u] for v, u in zip(perm, perm[1:]))
    ans = min(ans, cur)

print(ans)

Submission status: Runtime Error

Solution code:
from scipy.sparse import*
from itertools import*
n,m,r = map(int,input().split())
R = [int(i)-1 for i in input().split()]
cost = [[0]*n for i in range(n)]
ans = 10**9
for j in range(m):
  a,b,c = map(int,input().split())
  cost[a-1][b-1] = c
  cost[b-1][a-1] = c

Co = csgraph.shortest_path(csr_matrix(cost))

for v in permutations(R):
  temp = 0
  for i in range(1,r):
    temp += Co[v[i-1]][v[i]]
  ans = min(ans,temp)
print(int(ans))

Submission status: Runtime Error

Solution code:
import itertools

def warshall_floyd(d):
  len_d = len(d)
  for k in range(len_d):
    for i in range(len_d):
      for j in range(len_d):
        if d[i][j] < d[i][k] + d[k][j]:
          d[i][j] = d[i][k] + d[k][j]
  return d

def main():
  n, m, r = map(int, input().split())
  list_r = list(map(int, input().split()))
  list_cand = list(itertools.permutations(list_r))

  dist = [[float("inf") if i != j else 0 for j in range(n)] for i in range(n)]
  for i in range(m):
    a, b, c = map(int, input().split())
    dist[a-1][b-1] = c
    dist[b-1][a-1] = c
  min_dist = warshall_floyd(dist)

  result = 10**100
  for one_cand in list_cand:
    temp = 0
    for i in range(r-1)
      temp += min_dist[one_cand[i]-1][one_cand[i+1]-1]
    if temp < result:
      result = temp
  print(result)

if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:
import itertools
n,m,R = map(int,input().split())
r = list(map(int,input().split()))
cost = [[-1]*n for i in range(n)]
for i in range(m):
    a,b,c = map(int,input().split())
    cost[a-1][b-1] = c
    cost[b-1][a-1] = c

for k in range(n):
    for i in range(n):
        for j in range(n):
            if cost[i][k] == -1 or cost[k][j] == -1:
                continue
            if cost[i][j] == -1:
                cost = cost[i][k]+cost[k][j]
            else:
                cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j])

ans = -1
for p in itertools.permutations(r):
    c = 0
    for i in range(R-1):
        c += cost[p[i]-1][p[i+1]-1]
    if ans == -1:
        ans = c
    else:
        ans = min(c, ans)
print(ans)

Submission status: Runtime Error

Solution code:
import itertools
n,m,R = map(int,input().split())
r = list(map(int,input().split()))
cost = {}
for i in range(m):
  a,b,c = map(int,input().split())
  cost[(a,b)] = c

ans = 1000000
for p in itertools.permutations(r):
  c = 0
  for i in range(len(r)-1):
    c += cost[(p[i], p[i+1])]
  ans = min(c, ans)
print(ans)

Submission status: Runtime Error

Solution code:
 itertools,heapq
INFTY = 10**8
N,M,R = map(int,input().split())
R = list(map(int,input().split()))
G = {}
for _ in range(M):
    A,B,C = map(int,input().split())
    if A not in G:
        G[A] = []
    G[A].append((B,C))
    if B not in G:
        G[B] = []
    G[B].append((A,C))
D = [[INFTY for j in range(N+1)] for i in range(N+1)]
for i in range(1,N+1):
    hist = [0 for _ in range(N+1)]
    heap = [(0,i)]
    while heap:
        cur = heapq.heappop(heap)
        if hist[cur[1]]==0:
            hist[cur[1]] = 1
            for x in G[cur[1]]:
                if hist[x[0]]==0:
                    if D[i][x[0]]>cur[0]+x[1]:
                        D[i][x[0]] = cur[0]+x[1]
                        heapq.heappush(heap,(D[i][x[0]],x[0]))
dmin = INFTY
for r in itertools.permutations(R,len(R)):
    d = 0
    for i in range(1,len(r)):
        d += D[r[i]][r[i-1]]
    dmin = min(dmin,d)
print(dmin)

Submission status: Runtime Error

Solution code:
# ABC073D - joisino's travel (210ms)
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  # vertex_0 won't appear in 1-idx graph
    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()

Submission status: Runtime Error

Solution code:
# ABC073D - joisino's travel
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
    searched = [0] * size
    dist[start], searched[start] = 0, 1
    queue = G[start]
    heapify(queue)
    while queue:
        v, cost = heappop(queue)
        if searched[v] or cost > dist[v]:
            continue
        dist[v] = cost
        searched[v] = 1
        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 = [None] + [dijkstra(G, N + 1, i) for i in range(1, N + 1)]
    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()

Submission status: Runtime Error

Solution code:
# ABC073D - joisino's travel
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
    searched = [0] * size
    dist[start], searched[start] = 0, 1
    queue = G[start]
    heapify(queue)
    while queue:
        v, cost = heappop(queue)
        if searched[v]:
            continue
        dist[v] = cost
        searched[v] = 1
        for u, next_cost in G[v]:
            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 = [None] + [dijkstra(G, N + 1, i) for i in range(1, N + 1)]
    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()

Submission status: Runtime Error

Solution code:
from itertools import*;from scipy.sparse.csgraph import*
N,M,R=map(int,input().split());r=map(int,input().split())
G=[[9e9]*N for _ in[0]*N]
for _ in[0]*M:A,B,C=map(int,input().split());G[A-1][B-1]=G[B-1][A-1]=C
D=dijkstra(G)
print(int(min(sum(D[i-1,j-1]for i,j in zip(t,t[1:]))for t in permutations(r))))

Submission status: Runtime Error

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

def main():
        import itertools

    def warshall_floyd(D, n):
        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])


    N, M, R = map(int, input().split())
    r = list(map(int, input().split()))
    D = [[float('inf')]*N for _ in range(N)]
    for i in range(N):
        D[i][i] = 0
    for _ in range(M):
        a, b, c = map(int, input().split())
        D[a-1][b-1] = c
        D[b-1][a-1] = c

    warshall_floyd(D, N)

    ans = float('inf')
    for P in itertools.permutations(r):
        cost = 0
        for i in range(R-1):
            cost += D[P[i]-1][P[i+1]-1]
        ans = min(ans, cost)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#A
def A():
    s = S()
    if "9" in s:
        print("Yes")
    else:
        print("No")
    return

#B
def B():
    n = II()
    ans = 0
    for _ in range(n):
        l, r = LI()
        ans += r - l + 1
    print(ans)
    return

#C
def C():
    n = II()
    A = {}
    for _ in range(n):
        k = II()
        if not k in A:
            A[k] = 1
        else:
            A[k] += 1
    ans = 0
    for item in A.values():
        ans += item % 2
    print(ans)
    return

#D
def D():
    n, m, r = LI()
    r = LI()
    edg = [[0 if i == k else inf for k in range(n)] for i in range(n)]
    for _ in range(m):
        a, b, c = LI_()
        edg[a][b] = c + 1
        edg[b][a] = c + 1
    for k in range(n):
        for a in range(n):
            for b in range(n):
                edg[a][b] = min(edg[a][b], edg[a][k] + edg[k][b])
    ans = 0
    for i in range(r - 1):
        ans += edg[r[i] - 1][r[i + 1] - 1]
    print(ans)

    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#A
def A():
    s = S()
    if "9" in s:
        print("Yes")
    else:
        print("No")
    return

#B
def B():
    n = II()
    ans = 0
    for _ in range(n):
        l, r = LI()
        ans += r - l + 1
    print(ans)
    return

#C
def C():
    n = II()
    A = {}
    for _ in range(n):
        k = II()
        if not k in A:
            A[k] = 1
        else:
            A[k] += 1
    ans = 0
    for item in A.values():
        ans += item % 2
    print(ans)
    return

#D
def D():
    n, m, r = LI()
    r = LI()
    edg = [[0 if i == k else inf for k in range(n)] for i in range(n)]
    for _ in range(m):
        a, b, c = LI_()
        edg[a][b] = c + 1
        edg[b][a] = c + 1
    for k in range(n):
        for a in range(n):
            for b in range(n):
                edg[a][b] = min(edg[a][b], edg[a][k] + edg[k][b])
    ans = 0
    for i in range(r - 1):
        ans += edg[r[i]-1][r[i + 1]-1]
    print(ans)

    return

#Solve
if __name__ == '__main__':
    B()

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#A
def A():
    s = S()
    if "9" in s:
        print("Yes")
    else:
        print("No")
    return

#B
def B():
    n = II()
    ans = 0
    for _ in range(n):
        l, r = LI()
        ans += r - l + 1
    print(ans)
    return

#C
def C():
    n = II()
    A = {}
    for _ in range(n):
        k = II()
        if not k in A:
            A[k] = 1
        else:
            A[k] += 1
    ans = 0
    for item in A.values():
        ans += item % 2
    print(ans)
    return

#D
def D():
    n, m, r = LI()
    r = LI()
    edg = [[0 if i == k else inf for k in range(n)] for i in range(n)]
    for _ in range(m):
        a, b, c = LI_()
        edg[a][b] = c + 1
        edg[b][a] = c + 1
    for k in range(n):
        for a in range(n):
            for b in range(n):
                edg[a][b] = min(edg[a][b], edg[a][k] + edg[k][b])
    ans = 0
    for i in range(r - 1):
        ans += edg[r[i]][r[i + 1]]
    print(ans)

    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Runtime Error

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

inf = int(1e9+7)
costs = [[inf if i != j else 0 for j in range(N+1)]for i in range(M+1)]

for a, b, c in ABC:
  if costs[a][b] > c:
    costs[a][b] = costs[b][a] = c

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

from itertools import permutations

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

Submission status: Runtime Error

Solution code:
--F1  No73.py        Bot (90,0)     (Py Outl FlyC WS Undo-Tree AC) 8:51PM 1.27 -------------
        # d[i][i] < 0 なら、グラフは負のサイクルを持つ
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    self.d[i][j] = min(self.d[i][j],
                                       self.d[i][k] + self.d[k][j])
        hasNegativeCycle = False
        for i in range(self.N):
            if self.d[i][i] < 0:
                hasNegativeCycle = True
                break
        for i in range(self.N):
            self.d[i][i] = 0
        return hasNegativeCycle, self.d


N, M, R = map(int, input().split())
r = list(map(int, input().split()))
A = [0] * M
B = [0] * M
C = [0] * M
for i in range(M):
    A[i], B[i], C[i] = map(int, input().split())

graph = WarshallFloyd(N)
for a, b, c in zip(A, B, C):
    graph.add(a - 1, b - 1, c)

hasNegativeCycle, d = graph.WarshallFloyd_search()

ans = float("inf")
for temp in list(permutations(r)):
    cand = 0
    for i in range(R - 1):
        fr = temp[i] - 1
        to = temp[i + 1] - 1
        cand += d[fr][to]
    ans = min(ans, cand)
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
import itertools
from scipy.sparse.csgraph import floyd_warshall as wf
import sys


MAX = 1e9


def main():
    n, m, r = map(int, input().split())
    r = list(map(int, input().split()))
    link = [[MAX if j != i else 0 for j in range(n+1)] for i in range(n+1)]
    for i in range(m):
        a, b, c = map(int, input().split())
        link[a][b] = c
        link[b][a] = c
    link = wf(link)
    ans = MAX
    for per in list(itertools.permutations(r)):
        tmp = 0
        for i in range(r-1):
            tmp += link[per[i]][pre[i+1]]
        ans = min(ans, tmp)
    print(int(ans))


if __name__ == "__main__":
    main()