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: Time Limit Exceeded

Solution code:
def hoge():
  from itertools import permutations
  N, M, R = map(int, input().split())
  r = map(int, input().split())
  r = [x - 1 for x in r]
  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 k in range(N):
      for i in range(N):
          for j in range(N):
              t = d[i][k] + d[k][j]
              d[i][j] = min(d[i][j], t)


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

  print(ans)
hoge()

Submission status: Time Limit Exceeded

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 k in range(N):
      for i in range(N):
          for j in range(N):
              t = d[i][k] + d[k][j]
              d[i][j] = min(d[i][j], t)


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

  print(ans)
hoge()

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations


def input_list():
    return map(int, input().split())


def main():
    N, M, R = input_list()
    r = input_list()
    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 = input_list()
        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):
                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(R - 1):
            temp += d[i[j] - 1][i[j + 1] - 1]
            if temp > ans:
                break
        ans = min(ans, temp)

    print(ans)


main()

Submission status: Time Limit Exceeded

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 k in range(N):
      for i in range(N):
          for j in range(N):
              t = d[i][k] + d[k][j]
              d[i][j] = min(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
      ans = min(ans, temp)

  print(ans)
hoge()

Submission status: Time Limit Exceeded

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):
                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(R - 1):
            temp += d[i[j] - 1][i[j + 1] - 1]
            if temp > ans:
                break
        ans = min(ans, temp)

    print(ans)


main()

Submission status: Time Limit Exceeded

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 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 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)
hoge()

Submission status: Time Limit Exceeded

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)]
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(R-1):
        temp += d[i[j]-1][i[j+1]-1]
        if temp > ans:
            break
    ans = min(ans, temp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
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 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 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: Time Limit Exceeded

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


  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
      ans = min(ans, temp)

  print(ans)
hoge()

Submission status: Time Limit Exceeded

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)]
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: Time Limit Exceeded

Solution code:
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):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])


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
    ans = min(ans, temp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N, M, R = map(int, input().split())
r = map(int, input().split())
inf = float('inf')
d = [[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):
            if d[i][j] > d[i][k] + d[k][j]:            
                d[i][j] = d[i][k] + d[k][j]

ans = inf
for i in list(itertools.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: Time Limit Exceeded

Solution code:
import itertools

N, M, R = map(int, input().split())
r = map(int, input().split())
inf = float('inf')
d = [[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):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

ans = inf
for i in list(itertools.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: Time Limit Exceeded

Solution code:
import itertools

N, M, R = map(int, input().split())
r = map(int, input().split())
inf = float('inf')
d = [[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):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

ans = inf
for i in list(itertools.permutations(r)):
    temp = 0
    flag = False
    for j in i:
        if flag:
            temp += d[prev][j - 1]
        else:
            flag = True
        prev = j - 1
    ans = min(ans, temp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N, M, R = map(int, input().split())
r = map(int, input().split())
d = [[float('inf') for j in range(N+1)] for i in range(N+1)]

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

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

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

ans = float('inf')
for i in list(itertools.permutations(r)):
    temp = 0
    flag = False
    for j in i:
        if flag:
            temp += d[prev][j]
        else:
            flag = True
        prev = j
    ans = min(ans, temp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

ans = float('inf')
for i in list(itertools.permutations(r)):
    temp = 0
    flag = False
    for j in i:
        if flag:
            temp += d[prev][j - 1]
        else:
            flag = True
        prev = j - 1
    ans = min(ans, temp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N, M, R = map(int, input().split())
r = map(int, input().split())
d = [[0 for j in range(N)] for i in range(N)]

for i in range(N):
    for j in range(N):
        if i == j:
            d[i][j] = 0
        else:
            d[i][j] = float('inf')

for i in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    if d[a][b] > c:
        d[a][b], d[b][a] = c, 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])

ans = float('inf')
for i in list(itertools.permutations(r)):
    temp = 0
    flag = False
    for j in i:
        if flag:
            temp += d[prev][j - 1]
        else:
            flag = True
        prev = j - 1
    ans = min(ans, temp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

infinit = 100000*300

distance = [[infinit]*N for _ in range(N)]

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

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

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


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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import queue

MAX = 999999999

def someone_ans():
    N, M, R = map(int, input().split())
    r = list(map(int, input().split()))
    graph = [[MAX for _ in range(N+1)] for _ in range(N+1)]
    for i in range(M):
        a, b, c = map(int, input().split())
        graph[a][b] = c
        graph[b][a] = c

    def dijkstra(d, index):
        q = queue.PriorityQueue()
        checked = []
        q.put((0, index))
        while not q.empty():
            # qの中の最小値だす
            cost, i = q.get()
            if i in checked: continue
            if cost == MAX: continue
            checked.append(i)
            d[index][i] = cost
            for j,v in enumerate(graph[i]):
                if v == MAX: continue
                if (j in checked) == False:
                    q.put((cost + graph[i][j], j))

        return d[index]
    ds = [[MAX for _ in range(N+1)] for _ in range(N+1)]

    # 自分から自分までの距離は0
    for i in range(1,N+1):
        ds[i][i] = 0

    for i in range(1,N+1):
        # 各地点からその他の地点までの最短距離を求める
        ds[i] = dijkstra(ds, i)
        for k in range(1,N+1):
            # k->iまでの距離はi->kと一緒
            ds[k][i] = ds[i][k]

    ans = MAX
    for l in itertools.permutations(r):
        cost = 0
        for i in range(1,R):
            cost += ds[l[i-1]][l[i]]
        ans = min(cost, ans)
    return ans

print(someone_ans())

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

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

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):
  for j in range(N):
    for k in range(N):
      if d[j][i]+d[i][k] < d[j][k]:
        d[j][k]=d[j][i]+d[i][k]

ans=INF
for root in permutations(r):
  cnt=0
  for i in range(R-1):
    cnt+=d[root[i]-1][root[i+1]-1]
    if cnt>ans:
      break
  ans=min(ans,cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

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

INF=10**20
d=[[INF for x in range(N)] for y 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):
  for j in range(N):
    for k in range(N):
      if d[j][i]+d[i][k] < d[j][k]:
        d[j][k]=d[j][i]+d[i][k]

ans=INF
for root in permutations(r):
  cnt=0
  for i in range(len(root)-1):
    cnt+=d[root[i]-1][root[i+1]-1]
    if cnt>ans:
      break
  ans=min(ans,cnt)
print(ans)

Submission status: Time Limit Exceeded

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 = []

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

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

        return d


    ds = [[1e16 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 = 1e16
    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: Time Limit Exceeded

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] > d[node] + cost:
                    d[to] = d[node] + cost
                    heapq.heappush(que, (dist + cost, to))

        return d


    ds = [[1e16 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 = 1e16
    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: Time Limit Exceeded

Solution code:
from collections import defaultdict
from itertools import permutations

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

INF=10**20
d=[[INF for x in range(N)] for y 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

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

ans=INF
warshall_floyd(N)
for root in permutations(r):
  cnt=0
  for i in range(len(root)-1):
    cnt+=d[root[i]-1][root[i+1]-1]
    if cnt>ans:
      break
  ans=min(ans,cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from itertools import permutations

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

INF=10**20
d=[[INF for x in range(N)] for y 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

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

ans=INF
warshall_floyd(N)
for root in permutations(r):
  cnt=0
  for i in range(len(root)-1):
    cnt+=d[root[i]-1][root[i+1]-1]
  ans=min(ans,cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools


MAX = 999999999
def m():
    N, M, R = map(int, input().split())
    r = list(map(int, input().split()))
    graph = [[MAX for _ in range(N+1)] for _ in range(N+1)]
    for i in range(M):
        a, b, c = map(int, input().split())
        graph[a][b] = c
        graph[b][a] = c

    def solve(d):
        for k in range(1,N+1):
            for j in range(1,N+1):
                for n in range(1,N+1):
                    d[j][n] = min(d[j][n], d[j][k] + d[k][n])
        return d

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

    e = solve(graph)
    ans = MAX
    for l in itertools.permutations(r):
        cost = 0
        for i in range(1,R):
            cost += e[l[i-1]][l[i]]
        ans = min(cost, ans)
    return ans
print(m())

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
N,M,R = map(int,input().split())
r = list(map(int,input().split()))
Ans = 10**10
A = [[10**10 for _ in range(N)] for _ in range(N)]
for _ in range(M):
    a,b,c = map(int,input().split())
    A[a-1][b-1] = c
    A[b-1][a-1] = c
for k in range(N):
    for i in range(N):
        for j in range(N):
            A[i][j] = min(A[i][j], A[i][k]+A[k][j])
P = list(permutations(r))
for p in P:
    d = 0
    for i in range(R-1):
        d += A[p[i]-1][p[i+1]-1]
    Ans = min(Ans,d)
print(Ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools

def get_next_int():
    return int(float(input()))


def get_next_ints(delim=" "):
    return tuple([int(float(x)) for x in input().split(delim)])


def get_next_str():
    return input()


def get_next_strs(delim=" "):
    return tuple(input().split(delim))


def get_next_by_types(*value_types, delim=" "):
    return tuple([t(x) for t, x in zip(value_types, input().split(delim))])


class Travel():
    """docstring for Travel"""
    def __init__(self):
        self.N, self.M, self.R = get_next_ints()
        self.towns = get_next_ints()
        self.road = np.asarray([[float("inf")] * (self.N + 1) for j in range(self.N + 1)])
        for i in range(self.M):
            a, b, c = get_next_ints()
            self.road[b][a] = self.road[a][b] = c

    def warshall_floyd(self):
        for k in range(self.N+1):
            for i in range(self.N+1):
                for j in range(self.N+1):
                    self.road[i][j] = min(self.road[i][j], self.road[i][k] + self.road[k][j])
        pass

    def permutation(self):
        min_value = float('inf')
        for perm in itertools.permutations(self.towns):
            cost = 0
            for i in range(1, len(perm)):
                cost += self.road[perm[i-1]][perm[i]]
            min_value = int(min(min_value, cost))
        return min_value

    def solve(self):
        self.warshall_floyd()
        min_cost = self.permutation()
        return min_cost

if __name__ == '__main__':
    t = Travel()
    print(t.solve())

Submission status: Time Limit Exceeded

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 i in range(1, N+1):
    W[i][i] = 0

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:
        wij, j = heapq.heappop(heap)
        if checked[j]:
            continue
        for k in range(1, N+1):
            wik = wij + W[j][k]
            if wik <= W[i][k]:
                W[i][k] = wik
                heapq.heappush(heap, (wik, k))
        checked[j] = True

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: Time Limit Exceeded

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):
    x = list(map(int, input().split()))
    A, B, C = x
    W[A][B] = C
    W[B][A] = C


for k in range(1, N+1):
     for j in range(1, N+1):
         if k == j:
             continue
         for i in range(j+1, N+1):
             W[i][j] = min(W[i][j], W[i][k]+W[k][j])
             W[j][i] = W[i][j]

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: Time Limit Exceeded

Solution code:
INF = 10**9

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

for i in range(1, N+1):

     W[i][i] = 0

for x in X:
     A, B, C = x
     W[A][B] = C
     W[B][A] = C

for k in range(1, N+1):
     for j in range(1, N+1):
         if W[k][j] >= INF:
             continue
         for i in range(j, N+1):
             W[i][j] = min(W[i][j], W[i][k]+W[k][j])
             W[j][i] = W[i][j]

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: Time Limit Exceeded

Solution code:
INF = 10**9

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

for i in range(1, N+1):
     W[i][i] = 0

for x in X:
     A, B, C = x
     W[A][B] = C
     W[B][A] = C

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

from itertools import permutations

ans = INF
for r_ in permutations(r):
    count = 0
    for i in range(R-1):
        count += W[r_[i]][r_[i+1]]
    ans = min(ans, count)
print(ans)

Submission status: Time Limit Exceeded

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

for _ in range(M):
    s, t, d = inpl()
    G[s][t] = d
    G[t][s] = d

for v in range(N):
    G[v][v] = 0 

def WarshallFloyd(G):
    V = len(G)
    for k in range(V):
        for i in range(V):
            if G[i][k] == INF:
                continue
            for j in range(V):
                G[i][j] = min(G[i][j], G[i][k] + G[k][j])
    return G

G = WarshallFloyd(G)

res = INF
for r in permutations(R, len(R)):
    tmp = 0
    for i in range(len(R)-1):
        tmp += G[r[i]][r[i+1]]
    res = min(res, tmp)
 
print(res)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

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


def warshall_floyd(adj_array):
    for k in range(len(adj_array)):
        for i in range(len(adj_array)):
            for j in range(len(adj_array)):
                adj_array[i][j] = min(adj_array[i][j], adj_array[i][k] + adj_array[k][j])
    return adj_array


ARSP = warshall_floyd(ARSP)

# 訪れ方の全列挙(max 8! = 40320)
journey = list(permutations(r))

ans = float('inf')
for j in journey:
    cost = 0
    for i in range(1, len(j)):
        if ARSP[j[i]][j[i-1]] == float('inf'):
            break
        cost += ARSP[j[i]][j[i-1]]
        if cost >= ans:
            break
    else:
        ans = cost

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# ワーシャルフロイド+全探索

import numpy as np
import itertools

def main():
    N, M, R = map(int, input().split())
    rs = map(int, input().split())
    inf = float('inf')
    cost = [[inf]*N for _ in range(N)]

    # グラフ作る
    for i in range(N):
        cost[i][i] = 0

    for _ 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):
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])

    # 組み合わせ全探索
    ans = inf
    for route in itertools.permutations(rs):
        d = 0
        for i in range(R-1):
            d += cost[route[i]-1][route[i+1]-1]
            if d > ans:
                break
        ans = min(ans, d)
    
    print(int(ans))


if __name__=='__main__':
    main()