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:
import copy

inf = 10 ** 9
n, m, R = [int(i) for i in input().split()]
r = [int(i) - 1 for i in input().split()]
dis = [[inf for _ in range(n)] for _ in range(n)]
for i in range(m):
    a, b, c = [int(i) for i in input().split()]
    dis[a - 1][b - 1] = c
    dis[b - 1][a - 1] = c

# 全ての頂点間の最短距離を算出、
for k in range(len(dis)):
    for i in range(len(dis)):
        for j in range(len(dis)):
            if dis[i][j] > dis[i][k] + dis[k][j]:
                dis[i][j] = dis[i][k] + dis[k][j]

def depth(visited, prev, last):
    if last == 0:
        # print("visited:{} prev:{}, last:{}".format(
            # visited, r[prev], last))
        return 0
    add = inf
    for i in range(len(visited)):
        if not visited[i]:
            _visited = copy.deepcopy(visited)
            _visited[i] = True
            add = min(add, dis[r[prev]][r[i]] + depth(_visited, i, last - 1))
            # print("add:{}".format(add))
    return add

_min = inf
for i in range(len(r)):
    # iをスタートとする
    visited = [False for _ in range(len(r))]
    visited[i] = True
    _min = min(_min, depth(visited, i, len(r) - 1))
print(_min)

"""
print("2 vs "+func(3, 3, [0, 1, 2], [[0, 1, 4], [1, 0, 1], [4, 1, 0]]))
print("4 vs "+func(3, 3, [0, 2], [[0, 2, 6], [2, 0, 2], [6, 2, 0]]))
print("3 vs "+func(4, 6, [1, 2, 3], [[0, 4, 6, 1], [4, 0, 3, 2], [6, 3, 0, 1], [1, 2, 1, 0]]))
# print("print(func({}, {}, {}, {}))".format(n, m, r, adj))
"""

Submission status: Time Limit Exceeded

Solution code:
import copy

def func(n, m, r, adj):
    inf = 10 ** 9
    dis = adj
    for i in range(len(adj)):
        for j in range(len(adj)):
            if i != j and dis[i][j] == 0:
                dis[i][j] = inf

    # 全ての頂点間の最短距離を算出、
    for k in range(len(dis)):
        for i in range(len(dis)):
            for j in range(len(dis)):
                if dis[i][j] > dis[i][k] + dis[k][j]:
                    dis[i][j] = dis[i][k] + dis[k][j]

    def depth(visited, prev, last):
        if last == 0:
            # print("visited:{} prev:{}, last:{}".format(
                # visited, r[prev], last))
            return 0
        add = inf
        for i in range(len(visited)):
            if not visited[i]:
                _visited = copy.deepcopy(visited)
                _visited[i] = True
                add = min(add, dis[r[prev]][r[i]] + depth(_visited, i, last - 1))
                # print("add:{}".format(add))
        return add

    _min = inf
    for i in range(len(r)):
        # iをスタートとする
        visited = [False for _ in range(len(r))]
        visited[i] = True
        _min = min(_min, depth(visited, i, len(r) - 1))
    return str(_min)

n, m, R = [int(i) for i in input().split()]
r = [int(i) - 1 for i in input().split()]
adj = [[0 for _ in range(n)] for _ in range(n)]
for i in range(m):
    a, b, c = [int(i) for i in input().split()]
    adj[a - 1][b - 1] = c
    adj[b - 1][a - 1] = c
print(func(n, m, r, adj))
"""
print("2 vs "+func(3, 3, [0, 1, 2], [[0, 1, 4], [1, 0, 1], [4, 1, 0]]))
print("4 vs "+func(3, 3, [0, 2], [[0, 2, 6], [2, 0, 2], [6, 2, 0]]))
print("3 vs "+func(4, 6, [1, 2, 3], [[0, 4, 6, 1], [4, 0, 3, 2], [6, 3, 0, 1], [1, 2, 1, 0]]))
# print("print(func({}, {}, {}, {}))".format(n, m, r, adj))
"""

Submission status: Time Limit Exceeded

Solution code:
import copy

class warshallFloyd:
    def __init__(self, adj):
        # math.infはpython3.5以降のみ使用可能
        self.inf = 10 ** 9
        self.dis = copy.deepcopy(adj)
        for i in range(len(adj)):
            for j in range(len(adj)):
                if i != j and adj[i][j] == 0:
                    self.dis[i][j] = self.inf

    # 全ての頂点間の最短距離を算出、
    def search(self):
        for k in range(len(self.dis)):
            for i in range(len(self.dis)):
                for j in range(len(self.dis)):
                    if self.dis[i][j] > self.dis[i][k] + self.dis[k][j]:
                        self.dis[i][j] = self.dis[i][k] + self.dis[k][j]
        return self.dis


def func(n, m, r, adj):
    war = warshallFloyd(adj)
    dis = war.search()

    def depth(visited, prev, last):
        if last == 0:
            # print("visited:{} prev:{}, last:{}".format(
                # visited, r[prev], last))
            return 0
        add = war.inf
        for i in range(len(visited)):
            if not visited[i]:
                _visited = copy.deepcopy(visited)
                _visited[i] = True
                add = min(add, dis[r[prev]][r[i]] + depth(_visited, i, last - 1))
                # print("add:{}".format(add))
        return add

    _min = war.inf
    for i in range(len(r)):
        # iをスタートとする
        visited = [False for _ in range(len(r))]
        visited[i] = True
        _min = min(_min, depth(visited, i, len(r) - 1))
    return str(_min)

n, m, R = [int(i) for i in input().split()]
r = [int(i) - 1 for i in input().split()]
adj = [[0 for _ in range(n)] for _ in range(n)]
for i in range(m):
    a, b, c = [int(i) for i in input().split()]
    adj[a - 1][b - 1] = c
    adj[b - 1][a - 1] = c
print(func(n, m, r, adj))
"""
print("2 vs "+func(3, 3, [0, 1, 2], [[0, 1, 4], [1, 0, 1], [4, 1, 0]]))
print("4 vs "+func(3, 3, [0, 2], [[0, 2, 6], [2, 0, 2], [6, 2, 0]]))
print("3 vs "+func(4, 6, [1, 2, 3], [[0, 4, 6, 1], [4, 0, 3, 2], [6, 3, 0, 1], [1, 2, 1, 0]]))
# print("print(func({}, {}, {}, {}))".format(n, m, r, adj))
"""

Submission status: Time Limit Exceeded

Solution code:
import copy

class warshallFloyd:
    def __init__(self, adj):
        # math.infはpython3.5以降のみ使用可能
        self.inf = 10 ** 9
        self.dis = copy.deepcopy(adj)
        for i in range(len(adj)):
            for j in range(len(adj)):
                if i != j and adj[i][j] == 0:
                    self.dis[i][j] = self.inf

    # 全ての頂点間の最短距離を算出、
    def search(self):
        for k in range(len(self.dis)):
            for i in range(len(self.dis)):
                for j in range(len(self.dis)):
                    if self.dis[i][j] > self.dis[i][k] + self.dis[k][j]:
                        self.dis[i][j] = self.dis[i][k] + self.dis[k][j]
        return self.dis


def func(n, m, r, adj):
    war = warshallFloyd(adj)
    dis = war.search()

    def depth(visited, prev, last):
        if last == 0:
            # print("visited:{} prev:{}, last:{}".format(
                # visited, r[prev], last))
            return 0
        add = war.inf
        for i in range(len(visited)):
            if not visited[i]:
                _visited = copy.deepcopy(visited)
                _visited[i] = True
                add = min(add, dis[r[prev]][r[i]] + depth(_visited, i, last - 1))
                # print("add:{}".format(add))
        return add

    _min = 10 ** 10
    for i in range(len(r)):
        # iをスタートとする
        visited = [False for _ in range(len(r))]
        visited[i] = True
        _min = min(_min, depth(visited, i, len(r) - 1))
    return str(_min)

n, m, R = [int(i) for i in input().split()]
r = [int(i) - 1 for i in input().split()]
adj = [[0 for _ in range(n)] for _ in range(n)]
for i in range(m):
    a, b, c = [int(i) for i in input().split()]
    adj[a - 1][b - 1] = c
    adj[b - 1][a - 1] = c
print(func(n, m, r, adj))
"""
print("2 vs "+func(3, 3, [0, 1, 2], [[0, 1, 4], [1, 0, 1], [4, 1, 0]]))
print("4 vs "+func(3, 3, [0, 2], [[0, 2, 6], [2, 0, 2], [6, 2, 0]]))
print("3 vs "+func(4, 6, [1, 2, 3], [[0, 4, 6, 1], [4, 0, 3, 2], [6, 3, 0, 1], [1, 2, 1, 0]]))
# print("print(func({}, {}, {}, {}))".format(n, m, r, adj))
"""

Submission status: Time Limit Exceeded

Solution code:
import copy
class warshallFloyd:
    def __init__(self, adj):
        # math.infはpython3.5以降のみ使用可能
        self.inf = 10 ** 9
        self.dis = copy.deepcopy(adj)
        for i in range(len(adj)):
            for j in range(len(adj)):
                if i != j and adj[i][j] == 0:
                    self.dis[i][j] = self.inf

    # 全ての頂点間の最短距離を算出、
    def search(self):
        for k in range(len(self.dis)):
            for i in range(len(self.dis)):
                for j in range(len(self.dis)):
                    if self.dis[i][j] > self.dis[i][k] + self.dis[k][j]:
                        self.dis[i][j] = self.dis[i][k] + self.dis[k][j]
        return self.dis


def func(n, m, r, adj):
    war = warshallFloyd(adj)
    dis = war.search()

    def depth(visited, prev, last):
        if last == 0:
            # print("visited:{} prev:{}, last:{}".format(
                # visited, r[prev], last))
            return 0
        add = 10 ** 10
        for i in range(len(visited)):
            if not visited[i]:
                _visited = copy.deepcopy(visited)
                _visited[i] = True
                add = min(add, dis[r[prev]][r[i]] + depth(_visited, i, last - 1))
                # print("add:{}".format(add))
        return add

    _min = 10 ** 10
    for i in range(len(r)):
        # iをスタートとする
        visited = [False for _ in range(len(r))]
        visited[i] = True
        _min = min(_min, depth(visited, i, len(r) - 1))
    return str(_min)

n, m, R = [int(i) for i in input().split()]
r = [int(i) - 1 for i in input().split()]
adj = [[0 for _ in range(n)] for _ in range(n)]
for i in range(m):
    a, b, c = [int(i) for i in input().split()]
    adj[a - 1][b - 1] = c
    adj[b - 1][a - 1] = c
print(func(n, m, r, adj))
"""
print("2 vs "+func(3, 3, [0, 1, 2], [[0, 1, 4], [1, 0, 1], [4, 1, 0]]))
print("4 vs "+func(3, 3, [0, 2], [[0, 2, 6], [2, 0, 2], [6, 2, 0]]))
print("3 vs "+func(4, 6, [1, 2, 3], [[0, 4, 6, 1], [4, 0, 3, 2], [6, 3, 0, 1], [1, 2, 1, 0]]))
# print("print(func({}, {}, {}, {}))".format(n, m, r, adj))
"""

Submission status: Time Limit Exceeded

Solution code:
import heapq
import copy


class dijkstra:
    def __init__(self, adj):
        self.adj = adj
        self.visited = [-1 for i in range(len(adj))]
        self.heap = []

    def allSearch(self, _start):
        # スタート地点を設定
        heapq.heappush(self.heap, [0, _start])
        # ダイクストラ法でスタート地点からの距離を算出
        while 1:
            if len(self.heap) == 0:
                break
            start = heapq.heappop(self.heap)
            # 同じノードへ複数候補がある場合がある、一度訪れたノードへの候補は削除する
            if self.visited[start[1]] != -1:
                continue
            # 確定した距離をvisitテーブルに保持
            self.visited[start[1]] = start[0]
            for i in range(len(self.adj)):
                if self.visited[i] == -1 and self.adj[start[1]][i] != 0:
                    heapq.heappush(self.heap, [self.adj[start[1]][i] + self.visited[start[1]], i])
        # print("start:{} score:{}".format(_start, max(self.visited)))
        return self.visited


def func(n, m, r, adj):
    dis = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(len(adj)):
        # iをスタートとする場合のダイクストラ
        dij = dijkstra(adj=adj)
        dis[i] = dij.allSearch(i)
    # for i in range(len(adj)):
        # print(dis[i])

    def depth(visited, prev, last):
        if last == 0:
            # print("visited:{} prev:{}, last:{}".format(
                # visited, r[prev], last))
            return 0
        add = 10 ** 10
        for i in range(len(visited)):
            if not visited[i]:
                _visited = copy.deepcopy(visited)
                _visited[i] = True
                add = min(add, dis[r[prev]][r[i]] + depth(_visited, i, last - 1))
                # print("add:{}".format(add))
        return add

    _min = 10 ** 10
    for i in range(len(r)):
        # iをスタートとする
        visited = [False for _ in range(len(r))]
        visited[i] = True
        _min = min(_min, depth(visited, i, len(r) - 1))
    return str(_min)

n, m, R = [int(i) for i in input().split()]
r = [int(i) - 1 for i in input().split()]
adj = [[0 for _ in range(n)] for _ in range(n)]
for i in range(m):
    a, b, c = [int(i) for i in input().split()]
    adj[a - 1][b - 1] = c
    adj[b - 1][a - 1] = c
print(func(n, m, r, adj))
"""
print("2 vs "+func(3, 3, [0, 1, 2], [[0, 1, 4], [1, 0, 1], [4, 1, 0]]))
print("4 vs "+func(3, 3, [0, 2], [[0, 2, 6], [2, 0, 2], [6, 2, 0]]))
print("3 vs "+func(4, 6, [1, 2, 3], [[0, 4, 6, 1], [4, 0, 3, 2], [6, 3, 0, 1], [1, 2, 1, 0]]))
# print("print(func({}, {}, {}, {}))".format(n, m, r, adj))
"""

Submission status: Time Limit Exceeded

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

from itertools import permutations

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
G = [[float('inf')] * (N) for _ 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):
            # 始点 = 終点、は例外的に距離0にしておく
            if i == j:
                G[i][j] = 0
            else:
                G[i][j] = min(G[i][j], G[i][k] + G[k][j])

ans = float('inf')
# 町の順番は順列全部試す(最大8なら大丈夫)
for p in permutations(r):
    sm = 0
    # 最短経路を足し合わせていく
    for i in range(1, len(p)):
        sm += G[p[i-1]-1][p[i]-1]
    ans = min(sm, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def washall_floyd(graph):
    num_v = len(graph)
    for k in range(num_v):
        for i in range(num_v):
            for j in range(num_v):
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
    return graph


n, m, r = map(int, input().split())
r_list = list(map(int, input().split()))
graph = [[float("inf") for _ in range(n)] for _ in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    graph[a - 1][b - 1] = c
    graph[b - 1][a - 1] = c

graph = washall_floyd(graph)
result = float("inf")
import itertools
permi = itertools.permutations(r_list)
for per in permi:
    r = 0
    start = per[0] - 1
    for p in per[1:]:
        end = p - 1
        r += graph[start][end]
        start = p - 1
    result = min(r, result)
print(result)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
import sys
N, M, R = map(int, input().split())
rs = [x - 1 for x in map(int, input().split())]
# グラフを作る
dist = [[float('inf')] * (N) for _ in range(N)]
for e in sys.stdin:
    A, B, C = map(int, e.split())
    dist[A - 1][B - 1] = dist[B - 1][A - 1] = C
# ワーシャルフロイドで全頂点間距離算出
for k in range(N):
    for i in range(N):
        for j in range(N):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
# 組み合わせ全探索
ans = float('inf')
for p in permutations(rs):
    tmp = 0
    for u, v in zip(p, p[1:]):
        tmp += dist[u][v]
        if tmp > ans:
            break
    else:
        ans = tmp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
N, M, R = map(int, input().split())
rs = [x - 1 for x in map(int, input().split())]
dist = [[float('inf')] * (N) for _ in range(N)]
for _ in range(M):
    A, B, C = map(int, input().split())
    dist[A - 1][B - 1] = dist[B - 1][A - 1] = C
for k in range(N):
    for i in range(N):
        for j in range(N):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
ans = float('inf')
for p in permutations(rs):
    tmp = 0
    for i in range(R - 1):
        tmp += dist[p[i]][p[i + 1]]
        if tmp > ans:
            break
    else:
        ans = tmp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
N, M, R = map(int, input().split())
r = [x - 1 for x in map(int, input().split())]
dist = [[float('inf')] * (N) for _ in range(N)]
for i in range(N): dist[i][i] = 0
for _ in range(M):
    A, B, C = map(int, input().split())
    dist[A - 1][B - 1] = dist[B - 1][A - 1] = C
# Warshall–Floyd algorithm
for k in range(N):
    for i in range(N):
        for j in range(N):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
ans = float('inf')
for p in permutations(r, R):
    ans = min(ans, sum(dist[u][v] for u, v in zip(p, p[1:])))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from itertools import permutations

inf = 10**6
n,m,r = map(int, input().split())
rl = list(map(int, input().split()))
edge = [[inf for _ in range(n)] for _ in range(n)]

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

for k in range(n):
    for i in range(n):
        for j in range(n):
            if i==j:
                edge[i][i] = 0
            else:
                edge[i][j] = min(edge[i][j], edge[i][k]+edge[k][j])

res = inf
for c in permutations(rl, r):
    tmp = 0
    for i in range(r-1):
        tmp += edge[c[i]-1][c[i+1]-1]
    res = min(res, tmp)

print(res)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from itertools import permutations

inf = 10**10
n,m,r = map(int, input().split())
rl = list(map(int, input().split()))
edge = [[inf for _ in range(n)] for _ in range(n)]

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

for k in range(n):
    for i in range(n):
        for j in range(n):
            if i==j:
                edge[i][i] = 0
            else:
                edge[i][j] = min(edge[i][j], edge[i][k]+edge[k][j])

res = inf
for c in permutations(rl, r):
    tmp = 0
    for i in range(r-1):
        tmp += edge[c[i]-1][c[i+1]-1]
    res = min(res, tmp)

print(res)

Submission status: Time Limit Exceeded

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
A = Warshall_Floyd(A,N)
 
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: Time Limit Exceeded

Solution code:
N, M, R = list(map(int, input().split()))
rs = list(map(int, input().split()))
 
ds = [[float('inf') for i in range(N)] for j in range(N)]
 
# for i in range(N):
#     ds[i][i] = 0
 
for i in range(M):
    a,b,c=list(map(int, input().split()))
    a,b=a-1,b-1
    ds[a][b] = c
    ds[b][a] = c
 
# Floyd–Warshall
for k in range(N):
    for i in range(N):
        for j in range(N):
                ds[i][j] = min(ds[i][j], ds[i][k] + ds[k][j])
 
import itertools
 
ans = float('inf')
 
for p in list(itertools.permutations(rs)):
    ln = 0
    for r in range(R-1):
        ln += ds[p[r]-1][p[r+1]-1]
    ans = min(ans, ln)
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M, R = list(map(int, input().split()))
rs = list(map(int, input().split()))
 
ds = [[float('inf') for i in range(N)] for j in range(N)]
 
for i in range(N):
    ds[i][i] = 0
 
for i in range(M):
    a,b,c=list(map(int, input().split()))
    a,b=a-1,b-1
    ds[a][b] = c
    ds[b][a] = c

for k in range(N):
    for i in range(N):
        for j in range(N):
                ds[i][j] = min(ds[i][j], ds[i][k] + ds[k][j])
 
import itertools
 
ans = float('inf')
 
for p in list(itertools.permutations(rs)):
    ln = 0
    for r in range(R-1):
        ln += ds[p[r]-1][p[r+1]-1]
    ans = min(ans, ln)
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M, R = list(map(int, input().split()))
rs = list(map(int, input().split()))
 
ds = [[float('inf')]*N for j in range(N)]
 
for i in range(N):
    ds[i][i] = 0
 
for i in range(M):
    a,b,c=list(map(int, input().split()))
    a,b=a-1,b-1
    ds[a][b] = c
    ds[b][a] = c
 
# Floyd–Warshall
for k in range(N):
    for i in range(N):
        for j in range(N):
                ds[i][j] = min(ds[i][j], ds[i][k] + ds[k][j])
 
from itertools import permutations
 
ans = float('inf')
 
for p in permutations(rs):
    ln = 0
    for r in range(R-1):
        ln += ds[p[r]-1][p[r+1]-1]
    ans = min(ans, ln)
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M, R = list(map(int, input().split()))
rs = list(map(lambda x: int(x)-1, input().split()))

ds = [[float('inf')]*N for j in range(N)]

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

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

# Floyd–Warshall
for k in range(N):
    for i in range(N):
        for j in range(N):
            dd = ds[i][k] + ds[k][j]
            if ds[i][j] > dd:
                ds[i][j] = dd

from itertools import permutations

ans = float('inf')

for p in permutations(rs):
    ln = 0
    for r in range(R-1):
        ln += ds[p[r]][p[r+1]]
    ans = min(ans, ln)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M, R = list(map(int, input().split()))
rs = list(map(lambda x: int(x)-1, input().split()))

ds = [[float('inf') for i in range(N)] for j in range(N)]

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

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

# Floyd–Warshall
for k in range(N):
    for i in range(N):
        for j in range(N):
            dd = ds[i][k] + ds[k][j]
            if ds[i][j] > dd:
                ds[i][j] = dd

from itertools import permutations

ans = float('inf')

for p in permutations(rs):
    ln = 0
    for r in range(R-1):
        ln += ds[p[r]][p[r+1]]
    ans = min(ans, ln)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M, R = list(map(int, input().split()))
rs = list(map(lambda x: int(x)-1, input().split()))

INF = 10e+10
ds = [[INF for i in range(N)] for j in range(N)]

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

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

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

from itertools import permutations

ans = INF

for p in list(permutations(rs)):
    ln = 0
    for r in range(R-1):
        ln += ds[p[r]][p[r+1]]
    ans = min(ans, ln)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M, R = list(map(int, input().split()))
rs = list(map(lambda x: int(x)-1, input().split()))

INF = 10e+10
ds = [[INF for i in range(N)] for j in range(N)]

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

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

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

from itertools import permutations

ans = INF

for p in permutations(rs):
    ln = 0
    for r in range(R-1):
        ln += ds[p[r]][p[r+1]]
    ans = min(ans, ln)

print(ans)

Submission status: Time Limit Exceeded

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


def iter_patterns(l):
    if len(l) == 1:
        return [l]
    patterns = []
    for i in range(len(l)):
        patterns += [[l[i]] + p for p in iter_patterns(l[:i] + l[i+1:])]
    return patterns


def main():
    N, M, R = map(int, input().split())
    r = list(map(int, input().split()))
    paths = [[float("inf")] * N for _ in range(N)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        paths[A-1][B-1] = C
        paths[B-1][A-1] = C
    for i in range(N):
        paths[i][i] = 0
    warshall_floyd(paths, N)
    retval = float("inf")
    for p in iter_patterns(r):
        dist = 0
        for i in range(R-1):
            dist += paths[p[i]-1][p[i+1]-1]
        retval = min(retval, dist)
    print(retval)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

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

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

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


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

# print(edges)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

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

edges=[[10**9 for i in range(n+1)] for i in range(n+1)]

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


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

# print(edges)

permutations
ans = 10**9
for i in permutations(R):
  tmp = 0
  for j in range(r-1):
    # print("i",i,"j",j)
    tmp += edges[i[j]][i[j+1]]
  ans = min(tmp, ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

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

edges=[[10**9 for i in range(n+1)] for i in range(n+1)]

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


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

# print(edges)

permutations
ans = 10**9
for i in permutations(R):
  tmp = 0
  for j in range(r-1):
    # print("i",i,"j",j)
    tmp += edges[i[j]][i[j+1]]
  ans = min(tmp, ans)

print(ans)

Submission status: Time Limit Exceeded

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

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

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

dist=[]
for i in range(V):
    dist.append(dijkstra(i))

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

print(ans)

Submission status: Time Limit Exceeded

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

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

dist=[]
for i in range(V):
    dist.append(dijkstra(i))

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

Submission status: Time Limit Exceeded

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

for i in range(V):
    G.append([])
for i in range(E):
    at,bt,ct=map(int,input().strip().split(' '))
    G[at-1].append([ct,bt-1])
    G[bt-1].append([ct,at-1]) #無向グラフのときはon
'''
#入力が0-indexedのとき
    G[at].append([ct,bt])
    G[bt].append([ct,at]) #無向グラフのときはon
'''
#入力が1-indexedのとき

def dijkstra(s):
    d=[inf]*V
    d[s]=0
    q=queue.PriorityQueue()
    q.put([0,s])
    while q.empty()==False:
        dq,v=q.get()
        if d[v]<dq:
            continue
        for i in range(len(G[v])):
            ec, et=G[v][i]
            #print(ec,et)
            if d[et]>d[v]+ec:
                d[et]=d[v]+ec
                q.put([d[et],et])
    return d

dist=[]
for i in range(V):
    dist.append(dijkstra(i))

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

Submission status: Time Limit Exceeded

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

for i in range(V):
    G.append([])
for i in range(E):
    at,bt,ct=map(int,input().strip().split(' '))
    G[at-1].append([ct,bt-1])
    G[bt-1].append([ct,at-1]) #無向グラフのときはon


def dijkstra(s):
    d=[inf]*V
    d[s]=0
    q=queue.PriorityQueue()
    q.put([0,s])
    while q.empty()==False:
        dq,v=q.get()
        if d[v]<dq:
            continue
        for i in range(len(G[v])):
            ec, et=G[v][i]
            #print(ec,et)
            if d[et]>d[v]+ec:
                d[et]=d[v]+ec
                q.put([d[et],et])
    return d

dist=[]
for i in range(V):
    dist.append(dijkstra(i))

ans=inf
def dfs(i,p,d):
    global ans
    if i==R:
        if d<ans:
            ans=d
        return
    for j in range(R):
        if visited[j]==False:
            visited[j]=True
            if p==-1:
                dfs(i+1,j,0)
            else:
                #print(rlis[p]-1,rlis[i]-1)
                dfs(i+1,j,d+dist[rlis[p]-1][rlis[j]-1])
            visited[j]=False

            
visited=[False]*V

dfs(0,-1,0)
            
print(ans)