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: Wrong Answer

Solution code:
from itertools import permutations

def main():
    N, M, R = map(int, input().split())
    r = map(int, input().split())
    inf = float('inf')
    d = [[inf] * N for i in range(N)]
    for i in range(N):
        d[i][i] = 0

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

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

    ans = inf
    for i in permutations(r):
        temp = 0
        for j in range(R - 1):
            temp += d[i[j] - 1][i[j + 1] - 1]
            if temp > ans:
                break
        ans = min(ans, temp)

    print(ans)


main()

Submission status: Wrong Answer

Solution code:
from itertools import permutations

def main():
    N, M, R = map(int, input().split())
    r = map(int, input().split())
    d = [[float('inf') 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, b, c = map(int, input().split())
        a -= 1
        b -= 1
        t = min(c, d[a][b])
        if d[a][b] > c:
            d[a][b], d[b][a] = t, t

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

    ans = float('inf')
    for i in permutations(r):
        temp = 0
        for j in range(R - 1):
            temp += d[i[j] - 1][i[j + 1] - 1]
            if temp > ans:
                break
        ans = min(ans, temp)

    print(ans)


main()

Submission status: Wrong Answer

Solution code:
def hoge():
  from itertools import permutations
  N, M, R = map(int, input().split())
  r = map(int, input().split())
  inf = float('inf')
  d = [[inf] * N for i in range(N)]

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

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


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


  ans = inf
  for i in permutations(r):
      temp = 0
      for j in range(len(i)-1):
          temp += d[i[j]-1][i[j+1]-1]
          if temp > ans:
              break
      if ans > temp:
        ans = temp
      # ans = min(ans, temp)

  print(ans)
hoge()

Submission status: Wrong Answer

Solution code:
from itertools import permutations
N, M, R = map(int, input().split())
r = map(int, input().split())
d = [[float('inf') for j in range(N)] for i in range(N)]
print(d)
for i in range(N):
    d[i][i] = 0

for i in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    t = min(c, d[a][b])
    # if d[a][b] > c:
    #     d[a][b], d[b][a] = t, t
    d[a][b], d[b][a] = t, t


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


ans = float('inf')
for i in permutations(r):
    temp = 0
    for j in range(len(i)-1):
        temp += d[i[j]-1][i[j+1]-1]
        if temp > ans:
            break
    ans = min(ans, temp)

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

N,M,R = map(int,input().split())
r = list(map(int,input().split()))
g = [[] for _ in range(N+1)]

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

def DFS(v):
        d = [-1]*(N+1)
        d[v] = 0
        q = [v]

        while q:
                u = q.pop()
                for i in g[u]:
                        if d[i[0]] == -1 or d[i[0]] > (d[u] + i[1]):
                                d[i[0]] = d[u] + i[1]
                                [q.append(j[0]) for j in g[i[0]]]

        return d

d = [[] for _ in range(N+1)]

for i in r:
        d[i] = DFS(i)

ans = -1
for i in list(itertools.permutations(r)):
        a = 0
        for j in range(len(i)-1):
                a += d[i[j]][i[j+1]]
        if ans == -1 or ans > a:
                ans = a

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
import itertools

def solve():
    N, M, _ = list(map(int, input().split()))
    R = list(map(int, input().split()))
    R = map(lambda x: x-1, R)
    G = [[] for i in range(N)]

    for i in range(M):
        A, B, C = list(map(int, input().split()))
        A -= 1
        B -= 1
        G[A].append([C, B])
        G[B].append([C, A])


    def dijkstra(d):
        que = []

        for i in range(len(d)):
            if d[i] == -1:
                break
            heapq.heappush(que, (d[i], i))

        while len(que) != 0:
            dist, node = heapq.heappop(que)
            for (cost, to) in G[node]:
                if d[to] == -1 or d[to] > d[node] + cost:
                    d[to] = d[node] + cost
                    heapq.heappush(que, (dist + cost, to))

        return d


    ds = [[-1 for i in range(N)] for j in range(N)]

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

    for i in range(N):
        ds[i] = dijkstra(ds[i])
        for j in range(N):
            ds[j][i] = ds[i][j]

    res = 100000*200
    for r in list(itertools.permutations(R)):
        d = 0
        for i in range(len(r)-1):
            d += ds[r[i]][r[i+1]]
        res = min(res, d)

    return res

print(solve())

Submission status: Wrong Answer

Solution code:
import heapq
import itertools

def solve():
    N, M, _ = list(map(int, input().split()))
    R = list(map(int, input().split()))
    R = map(lambda x: x-1, R)
    G = [[] for i in range(N)]

    for i in range(M):
        A, B, C = list(map(int, input().split()))
        A -= 1
        B -= 1
        G[A].append([C, B])
        G[B].append([C, A])


    def dijkstra(d):
        que = []
        visited = [False] * len(d)

        for i in range(len(d)):
            if d[i] != -1:
                heapq.heappush(que, (d[i], i))

        while len(que) != 0:
            dist, node = heapq.heappop(que)
            if visited[node]:
                continue
            visited[node] = True
            d[node] = dist

            for (cost, to) in G[node]:
                if d[to] == -1 or d[to] > dist + cost:
                    heapq.heappush(que, (dist + cost, to))

        return d


    ds = [[-1 for i in range(N)] for j in range(N)]

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

    for i in range(N):
        ds[i] = dijkstra(ds[i])
        for j in range(i):
            ds[j][i] = ds[i][j]


    res = 100000*200
    for r in list(itertools.permutations(R)):
        d = 0
        for i in range(len(r)-1):
            d += ds[r[i]][r[i+1]]
        res = min(res, d)

    return res

print(solve())

Submission status: Wrong Answer

Solution code:
INF = 10**9

N, M, R = list(map(int, input().split()))
r = list(map(int, input().split()))
W = [[INF for _ in range(N+1)] for __ in range(N+1)]

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

import heapq

for i in range(1, N+1):
    heap = []
    checked = [False for _ in range(N+1)]
    heapq.heappush(heap, (0, i))
    while len(heap) > 0:
        w1, j = heapq.heappop(heap)
        if checked[j]:
            continue
        for k in range(i, N+1):
            w = w1 + W[j][k]
            if w < W[i][k]:
                W[i][k] = w
                W[k][i] = w
                heapq.heappush(heap, (w, k))

from itertools import permutations

ans = INF
for r_ in permutations(r):
    count = 0
    for i in range(R-1):
        x = W[r_[i]][r_[i+1]]
        if x >= INF:
            break
        count += x
        if count >= ans:
            break
    else:
        ans = count
print(ans)

Submission status: Wrong Answer

Solution code:
INF = 10**9

N, M, R = list(map(int, input().split()))
r = list(map(int, input().split()))
W = [[INF for _ in range(N+1)] for __ in range(N+1)]

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

import heapq


for i in range(1, N+1):
    heap = []
    for j in range(i+1, N+1):
        if W[i][j] < INF:
            heapq.heappush(heap, (W[i][j], j))
    while len(heap) > 0:
        w, j = heapq.heappop(heap)
        for k in range(i+1, N+1):
            if w + W[j][k] < W[i][k]:
                W[i][k] = w + W[j][k]
                W[k][i] = W[i][k]
                heapq.heappush(heap, (W[i][k], k))

from itertools import permutations

ans = INF
for r_ in permutations(r):
    count = 0
    for i in range(R-1):
        x = W[r_[i]][r_[i+1]]
        if x >= INF:
            break
        count += x
        if count >= ans:
            break
    else:
        ans = count
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
d = [[]] * (N + 1)
for i in range(N + 1):
    d[i] = [float('inf')] * (N + 1)
    d[i][i] = 0
for i in range(M):
    a, b, c = map(int, input().split())
    if d[a][b] > c:
        d[a][b] = d[b][a] = c

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

r2 = list(itertools.permutations(r))
minDis = float('inf')
for i in range(len(r2)):
    dis = 0
    for j in range(R-1):
        dis += d[r2[i][j]][r2[i][j+1]]
    minDis = min(minDis, dis)
print(minDis)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from itertools import permutations, product
def inpl(): return tuple(map(int, input().split()))
N, M, R = inpl()
inf = float("inf")
G = [[inf for _ in range(N+1)] for _ in range(N+1)]
D = inpl() # destination

for _ in range(M):
    a, b, c = inpl()
    G[a][b] = c
    G[b][a] = c

for n in range(N+1):
    G[n][n] = 0

for i ,j in product(range(1, N+1), repeat=2):
    for k in range(j, N+1):
        G[j][k] = min(G[j][k], G[j][i] + G[i][k])

res = inf
for C in permutations(D, len(D)):
    res = min(res, sum([G[C[i]][C[i+1]] for i in range(len(D)-1)]))

print(res)

Submission status: Wrong Answer

Solution code:
def Warshall_Floyd(edges,N):
  for k in range(N):
    for i in range(N):
      for j in range(N):
        edges[i][j]=min(edges[i][j],edges[i][k]+edges[k][j])
  return edges

import itertools
N, M, R = map(int,input().split())
r = list(map(int,input().split()))
A=[[float("inf") for i in range(N)] for j in range(N)]
for m in range(M):
  a, b, c = map(int,input().split())
  A[a-1][b-1] = c
  A[b-1][a-1] = c
ans = float("inf")
for road in list(itertools.permutations(r)):
  length = 0
  for i in range(R-1):
    length += A[road[i]-1][road[i+1]-1]
  ans = min(ans, length)
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python

import itertools

def make_shortest_path_matrix(adjacent_matrix):
    for k in range(len(adjacent_matrix)):
        for i in range(len(adjacent_matrix)):
            for j in range(len(adjacent_matrix)):
                if adjacent_matrix[i][j] > adjacent_matrix[i][k] + adjacent_matrix[k][j]:
                    adjacent_matrix[i][j] = adjacent_matrix[i][k] + adjacent_matrix[k][j]
    return adjacent_matrix


def make_perm(R_list):
    return list(itertools.permutations(R_list, len(R_list)))

def main():
    N, M, R = map(int, input().split(" "))
    R_list = list(map(int, input().split(" ")))
    
    INF = 999999
    adjacent_matrix = [[INF for _ in range(N)] for _ in range(N)]

    for _ in range(M):
        source, target, dist = map(int, input().split(" "))
        source -= 1
        target -= 1
        adjacent_matrix[source][target] = adjacent_matrix[target][source] = dist

    shortest_path_matrix = make_shortest_path_matrix(adjacent_matrix)
    R_list_perm = make_perm(R_list)

    shortest_path_dist = INF
    for path in R_list_perm:
        tmp_path_dist = 0
        for i in range(len(path) - 1):
            source = path[i] - 1
            target = path[i + 1] - 1
            tmp_path_dist += shortest_path_matrix[source][target]
        if shortest_path_dist > tmp_path_dist:
            shortest_path_dist = tmp_path_dist

    # print(R_list_perm)
    # print(shortest_path_matrix)
    print(shortest_path_dist)


        

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
import itertools

def read_data():
    try:
        LOCAL_FLAG
        import codecs
        import os

        lines = []
        file_path = os.path.join(os.path.dirname(__file__), 'data073.dat')
        with codecs.open(file_path, 'r', 'utf-8') as f:
            lines.append(f.readline().rstrip("\r\n"))
            N, M, R = list(map(int, lines[0].split()))
            for i in range(M+1):
                lines.append(f.readline().rstrip("\r\n"))


    except NameError:
        lines = []
        lines.append(input())
        N, M, R = list(map(int, lines[0].split()))
        for i in range(M+1):
            lines.append(input())

    return lines

def dis(D, town_list):
    total = 0
    for i in range(len(town_list)-1):
        total += D[town_list[i]][town_list[i+1]]
    return total


def Travel():

    raw_data = read_data()
    N, M, R = list(map(int, raw_data[0].split()))
    town_list = list(map(int, raw_data[1].split()))
    road_set = set([])

    MAX = 200000
    # D = np.zeros((N+1, N+1), dtype='int32')
    # D += MAX
    D = [[float('inf')]*(N+1) for _ in range(N+1)]


    for i in range(2, M+2):
        a, b, c = list(map(int, raw_data[i].split()))
        D[a][b] = c
        D[b][a] = c

    # for i in range(1, N+1):
    #     for j in range(1, N+1):
    #         dis_two_node = np.min(D[i] + D[j])
    #         if dis_two_node < D[i,j]:
    #             D[i,j] = dis_two_node
    #             D[j,i] = dis_two_node

    # for i in range(N+1):
    #     D[i][i] = 0

    for k in range(1, N+1):
        for i in range(1, N+1):
            if(i == k):
                continue
            for j in range(1, N+1):
                dis_two_node = D[i][k] + D[k][j]
                if dis_two_node < D[i][j]:
                    D[i][j] = dis_two_node
                    D[j][i] = dis_two_node

    # print(D)


    min_dis = MAX*8
    for each in itertools.permutations(town_list):
        min_dis = min(dis(D, each), min_dis)

    print(min_dis)




Travel()

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
import itertools

def read_data():
    try:
        LOCAL_FLAG
        import codecs
        import os

        lines = []
        file_path = os.path.join(os.path.dirname(__file__), 'data073.dat')
        with codecs.open(file_path, 'r', 'utf-8') as f:
            lines.append(f.readline().rstrip("\r\n"))
            N, M, R = list(map(int, lines[0].split()))
            for i in range(M+1):
                lines.append(f.readline().rstrip("\r\n"))


    except NameError:
        lines = []
        lines.append(input())
        N, M, R = list(map(int, lines[0].split()))
        for i in range(M+1):
            lines.append(input())

    return lines

def dis(D, town_list):
    total = 0
    for i in range(len(town_list)-1):
        total += D[town_list[i]][town_list[i+1]]
    return total


def Travel():

    raw_data = read_data()
    N, M, R = list(map(int, raw_data[0].split()))
    town_list = list(map(int, raw_data[1].split()))
    road_set = set([])

    MAX = 200000
    # D = np.zeros((N+1, N+1), dtype='int32')
    # D += MAX
    D = [[float('inf')]*(N+1) for _ in range(N+1)]


    for i in range(2, M+2):
        a, b, c = list(map(int, raw_data[i].split()))
        D[a][b] = c
        D[b][a] = c

    # for i in range(1, N+1):
    #     for j in range(1, N+1):
    #         dis_two_node = np.min(D[i] + D[j])
    #         if dis_two_node < D[i,j]:
    #             D[i,j] = dis_two_node
    #             D[j,i] = dis_two_node

    # for i in range(N+1):
    #     D[i][i] = 0

    for k in range(1, N+1):
        for i in range(1, N+1):
            if(i == k):
                continue
            for j in range(i+1, N+1):
                dis_two_node = D[i][k] + D[k][j]
                if dis_two_node < D[i][j]:
                    D[i][j] = dis_two_node
                    D[j][i] = dis_two_node

    # print(D)


    min_dis = MAX*8
    for each in itertools.permutations(town_list):
        min_dis = min(dis(D, each), min_dis)

    print(min_dis)




Travel()

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
import itertools

def read_data():
    try:
        LOCAL_FLAG
        import codecs
        import os

        lines = []
        file_path = os.path.join(os.path.dirname(__file__), 'data073.dat')
        with codecs.open(file_path, 'r', 'utf-8') as f:
            lines.append(f.readline().rstrip("\r\n"))
            N, M, R = list(map(int, lines[0].split()))
            for i in range(M+1):
                lines.append(f.readline().rstrip("\r\n"))

    except NameError:
        lines = []
        lines.append(input())
        N, M, R = list(map(int, lines[0].split()))
        for i in range(M+1):
            lines.append(input())

    return lines

def dis(D, town_list):
    total = 0
    for i in range(len(town_list)-1):
        total += D[town_list[i]][town_list[i+1]]
    return total


def Travel():

    raw_data = read_data()
    N, M, R = list(map(int, raw_data[0].split()))
    town_list = list(map(int, raw_data[1].split()))
    road_set = set([])

    MAX = 200000
    D = np.zeros((N+1, N+1), dtype='int32')
    D += MAX

    for i in range(2, M+2):
        a, b, c = list(map(int, raw_data[i].split()))
        D[a][b] = c
        D[b][a] = c

    for i in range(1, N+1):
        for j in range(1, N+1):
            if(i == j):
                continue
            dis_two_node = np.min(D[i] + D[j])
            if dis_two_node < D[i,j]:
                D[i,j] = dis_two_node
                D[j,i] = dis_two_node
                

    # print(D)


    min_dis = MAX*8
    for each in itertools.permutations(town_list):
        min_dis = min(dis(D, each), min_dis)

    print(min_dis)




Travel()

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
import itertools

def read_data():
    try:
        LOCAL_FLAG
        import codecs
        import os

        lines = []
        file_path = os.path.join(os.path.dirname(__file__), 'data073.dat')
        with codecs.open(file_path, 'r', 'utf-8') as f:
            lines.append(f.readline().rstrip("\r\n"))
            N, M, R = list(map(int, lines[0].split()))
            for i in range(M+1):
                lines.append(f.readline().rstrip("\r\n"))

    except NameError:
        lines = []
        lines.append(input())
        N, M, R = list(map(int, lines[0].split()))
        for i in range(M+1):
            lines.append(input())

    return lines

def dis(D, town_list):
    total = 0
    for i in range(len(town_list)-1):
        total += D[town_list[i]][town_list[i+1]]
    return total


def Travel():

    raw_data = read_data()
    N, M, R = list(map(int, raw_data[0].split()))
    town_list = list(map(int, raw_data[1].split()))
    road_set = set([])

    MAX = 200000
    D = np.zeros((N+1, N+1), dtype='int32')
    D += MAX

    for i in range(2, M+2):
        a, b, c = list(map(int, raw_data[i].split()))
        D[a][b] = c
        D[b][a] = c

    for i in range(1, N+1):
        for j in range(1, N+1):
            if(i == j):
                continue
            dis_two_node = np.min(D[i] + D[j])
            if dis_two_node < D[i,j]:
                D[i,j] = dis_two_node
                

    # print(D)


    min_dis = MAX
    for each in itertools.permutations(town_list):
        min_dis = min(dis(D, each), min_dis)

    print(min_dis)




Travel()

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
import itertools

def read_data():
    try:
        LOCAL_FLAG
        import codecs
        import os

        lines = []
        file_path = os.path.join(os.path.dirname(__file__), 'data073.dat')
        with codecs.open(file_path, 'r', 'utf-8') as f:
            lines.append(f.readline().rstrip("\r\n"))
            N, M, R = list(map(int, lines[0].split()))
            for i in range(M+1):
                lines.append(f.readline().rstrip("\r\n"))

    except NameError:
        lines = []
        lines.append(input())
        N, M, R = list(map(int, lines[0].split()))
        for i in range(M+1):
            lines.append(input())

    return lines

def dis(D, town_list):
    total = 0
    for i in range(len(town_list)-1):
        total += D[town_list[i]][town_list[i+1]]
    return total


def Travel():

    raw_data = read_data()
    N, M, R = list(map(int, raw_data[0].split()))
    town_list = list(map(int, raw_data[1].split()))
    road_set = set([])

    MAX = 200000
    D = np.zeros((N+1, N+1), dtype='int32')
    D += MAX

    for i in range(2, M+2):
        a, b, c = list(map(int, raw_data[i].split()))
        D[a][b] = c
        D[b][a] = c

    for i in range(1, N+1):
        for j in range(1, N+1):
            if(i == j):
                continue
            dis_two_node = np.min(D[i] + D[j])
            if dis_two_node < D[i,j]:
                D[i,j] = dis_two_node
                D[j,i] = dis_two_node

    # print(D)


    min_dis = MAX
    for each in itertools.permutations(town_list):
        min_dis = min(dis(D, each), min_dis)

    print(min_dis)




Travel()

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
import itertools

def read_data():
    try:
        LOCAL_FLAG
        import codecs
        import os

        lines = []
        file_path = os.path.join(os.path.dirname(__file__), 'data073.dat')
        with codecs.open(file_path, 'r', 'utf-8') as f:
            lines.append(f.readline().rstrip("\r\n"))
            N, M, R = list(map(int, lines[0].split()))
            for i in range(M+1):
                lines.append(f.readline().rstrip("\r\n"))

    except NameError:
        lines = []
        lines.append(input())
        N, M, R = list(map(int, lines[0].split()))
        for i in range(M+1):
            lines.append(input())

    return lines

def dis(D, town_list):
    total = 0
    for i in range(len(town_list)-1):
        total += D[town_list[i]][town_list[i+1]]
    return total


def Travel():

    raw_data = read_data()
    N, M, R = list(map(int, raw_data[0].split()))
    town_list = list(map(int, raw_data[1].split()))
    road_set = set([])

    MAX = 200000
    D = np.zeros((N+1, N+1), dtype='int32')
    D += MAX

    for i in range(2, M+2):
        a, b, c = list(map(int, raw_data[i].split()))
        D[a][b] = c
        D[b][a] = c

    for i in range(1, N):
        for j in range(1, N+1):
            if(i == j):
                continue
            dis_two_node = np.min(D[i] + D[j])
            if dis_two_node < D[i,j]:
                D[i,j] = dis_two_node
                D[j,i] = dis_two_node

    # print(D)


    min_dis = MAX
    for each in itertools.permutations(town_list):
        min_dis = min(dis(D, each), min_dis)

    print(min_dis)




Travel()

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
import math

def read_data():
    try:
        LOCAL_FLAG
        import codecs
        import os

        lines = []
        file_path = os.path.join(os.path.dirname(__file__), 'data073.dat')
        with codecs.open(file_path, 'r', 'utf-8') as f:
            lines.append(f.readline().rstrip("\r\n"))
            N, M, R = list(map(int, lines[0].split()))
            for i in range(M+1):
                lines.append(f.readline().rstrip("\r\n"))

    except NameError:
        lines = []
        lines.append(input())
        N, M, R = list(map(int, lines[0].split()))
        for i in range(M+1):
            lines.append(input())

    return lines

def dis(D, town_list):
    total = 0
    for i in range(len(town_list)-1):
        total += D[town_list[i]][town_list[i+1]]
    return total


def Travel():

    raw_data = read_data()
    N, M, R = list(map(int, raw_data[0].split()))
    town_list = list(map(int, raw_data[1].split()))
    road_set = set([])

    MAX = 200000
    D = np.zeros((N+1, N+1), dtype='int32')
    D += MAX

    for i in range(2, M+2):
        a, b, c = list(map(int, raw_data[i].split()))
        D[a][b] = c
        D[b][a] = c

    # print(raw_data)
    # print(N, M, R)
    # print(town_list)
    # print(D)
    M = np.copy(D)

    for i in range(1, N):
        for j in range(i+1, N+1):
            dis_two_node = np.min(D[i] + D[j])
            if dis_two_node < D[i,j]:
                M[i,j] = dis_two_node
                M[j,i] = dis_two_node
            else:
                M[i,j] = D[i,j]
                M[j,i] = D[i,j]

    # print(D)
    # print(M)


    import itertools
    min_dis = MAX
    for each in itertools.permutations(town_list):
        min_dis = min(dis(M, each), min_dis)

    print(min_dis)




Travel()

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
import math

def read_data():
    try:
        LOCAL_FLAG
        import codecs
        import os

        lines = []
        file_path = os.path.join(os.path.dirname(__file__), 'data073.dat')
        with codecs.open(file_path, 'r', 'utf-8') as f:
            lines.append(f.readline().rstrip("\r\n"))
            N, M, R = list(map(int, lines[0].split()))
            for i in range(M+1):
                lines.append(f.readline().rstrip("\r\n"))

    except NameError:
        lines = []
        lines.append(input())
        N, M, R = list(map(int, lines[0].split()))
        for i in range(M+1):
            lines.append(input())

    return lines

def dis(D, town_list):
    total = 0
    for i in range(len(town_list)-1):
        total += D[town_list[i]][town_list[i+1]]
    return total


def Travel():

    raw_data = read_data()
    N, M, R = list(map(int, raw_data[0].split()))
    town_list = list(map(int, raw_data[1].split()))
    road_set = set([])

    MAX = 200000
    D = np.zeros((N+1, N+1), dtype='int32')
    D += MAX

    for i in range(2, M+2):
        a, b, c = list(map(int, raw_data[i].split()))
        D[a][b] = c
        D[b][a] = c
        road_set.add(a)
        road_set.add(b)

    # print(raw_data)
    # print(N, M, R)
    # print(town_list)
    # print(D)
    # print(road_set)
    M = np.copy(D)

    for i in range(1, N):
        for j in range(i+1, N+1):
            dis_two_node = np.min(D[i] + D[j])
            if dis_two_node < D[i,j]:
                M[i,j] = dis_two_node
                M[j,i] = dis_two_node
            else:
                M[i,j] = D[i,j]
                M[j,i] = D[i,j]

    # print(D)
    # print(M)


    import itertools
    min_dis = MAX
    for each in itertools.permutations(town_list):
        if(dis(M, each) < min_dis):
            min_dis = dis(D, each)

    print(min_dis)




Travel()

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys

def read_data():
    try:
        LOCAL_FLAG
        import codecs
        import os

        lines = []
        file_path = os.path.join(os.path.dirname(__file__), 'data073.dat')
        with codecs.open(file_path, 'r', 'utf-8') as f:
            lines.append(f.readline().rstrip("\r\n"))
            N, M, R = list(map(int, lines[0].split()))
            for i in range(M+1):
                lines.append(f.readline().rstrip("\r\n"))

    except NameError:
        lines = []
        lines.append(input())
        N, M, R = list(map(int, lines[0].split()))
        for i in range(M+1):
            lines.append(input())

    return lines

def dis(D, town_list):
    total = 0
    for i in range(len(town_list)-1):
        total += D[town_list[i]][town_list[i+1]]
    return total


def Travel():

    raw_data = read_data()
    N, M, R = list(map(int, raw_data[0].split()))
    town_list = list(map(int, raw_data[1].split()))

    MAX = 200000
    D = np.zeros((N+1, N+1), dtype='int32')
    D += MAX

    for i in range(2, M+2):
        a, b, c = list(map(int, raw_data[i].split()))
        D[a][b] = c
        D[b][a] = c

    # print(raw_data)
    # print(N, M, R)
    # print(town_list)
    # print(D)

    for k in range(2):
        for i in range(1, N):
            for j in range(i+1, N+1):
                dis_two_node = np.min(D[i] + D[j])
                if dis_two_node < D[i,j]:
                    D[i,j] = dis_two_node
                    D[j,i] = dis_two_node



    import itertools
    min_dis = MAX
    for each in itertools.permutations(town_list):
        if(dis(D, each) < min_dis):
            min_dis = dis(D, each)

    print(min_dis)




Travel()

Submission status: Wrong Answer

Solution code:
import itertools
N,M,R=map(int,input().split())
r = [ int(i)-1 for i in input().split()]
rs = [[1001001001]*N for _ in range(N)]

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

for i in range(N-1):
    for j, d1 in enumerate(rs[i][i+1:], start=i+1):
        d2 = min([rs[i][k]+rs[j][k] for k in range(N)])
        if d1 >= d2:
            rs[i][j] = rs[j][i] = d2

ans = 1001001001
for i in itertools.permutations(r):
    s = 0
    for j in range(R-1):
        s += rs[i[j]][i[j+1]]
    ans = min(ans,s)

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
import numpy as np
N,M,R=map(int,input().split())
R = [ int(i)-1 for i in input().split()]
inf = 1001001001
rs = [np.array([inf]*N) for _ in range(N)]

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

for i in range(N-1):
    for j, d1 in enumerate(rs[i][i+1:], start=i+1):
        d2 = np.min(rs[i]+rs[j])
        if d1 >= d2:
            rs[i][j] = rs[j][i] = d2

p = list(itertools.permutations(range(N)));
ans = 1001001001
for i in p:
    s = 0
    for j in range(N-1):
        s += rs[i[j]][i[j+1]]
    ans = min(ans,s)

print(ans)