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:
from itertools import permutations

N, M, R = [int(n) for n in input().split()]
r = [int(n)-1 for n in input().split()]
d = [[100000000]*N for n in range(N)]

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

for m in range(M):
  A, B, C = [int(n) for n in input().split()]
  A-=1
  B-=1
  d[A][B] = C
  d[B][A] = C

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

res = 10000000000
for perm in permutations(range(R)):
  s = 0
  for i in range(R-1):
    s += d[r[perm[i]]][r[perm[i+1]]]
  res = min(s, res)

print(res)

Submission status: Time Limit Exceeded

Solution code:
import itertools

def main():
    N, M, R = map(int, input().split())
    RR = tuple(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 i in range(N):
        dist[i][i] = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = dist[i][j] if dist[i][j] < dist[i][k] + dist[k][j] else dist[i][k] + dist[k][j]

    ans = float('inf')
    for r in itertools.permutations(RR):
        move = 0
        for i in range(R - 1):
            a = r[i] - 1
            b = r[i+1] - 1
            move += dist[a][b]
        ans = ans if ans < move else move

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

def main():
    N, M, R = map(int, input().split())
    RR = tuple(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):
                dist[i][j] = dist[i][j] if dist[i][j] < dist[i][k] + dist[k][j] else dist[i][k] + dist[k][j]

    ans = float('inf')
    for r in itertools.permutations(RR):
        move = 0
        for i in range(R - 1):
            a = r[i] - 1
            b = r[i+1] - 1
            move += dist[a][b]
        ans = ans if ans < move else move

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

def main():
    N, M, R = map(int, input().split())
    RR = tuple(map(int, input().split()))

    dist = [[float('inf')] * N for _ in range(N)]
    for a, b, c in (map(int, input().split()) for _ in range(M)):
        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):
                dist[i][j] = dist[i][j] if dist[i][j] < dist[i][k] + dist[k][j] else dist[i][k] + dist[k][j]

    ans = float('inf')
    for r in itertools.permutations(RR):
        move = 0
        for i in range(R - 1):
            a = r[i] - 1
            b = r[i+1] - 1
            move += dist[a][b]
        ans = ans if ans < move else move

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

def main():
    N, M, R = map(int, input().split())
    RR = tuple(map(int, input().split()))
    ABC = (tuple(map(int, input().split())) for _ in range(M))

    dist = [[float('inf')] * N for _ in range(N)]
    for a, b, c in ABC:
        dist[a-1][b-1] = dist[b-1][a-1] = c
        dist[a-1][a-1] = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = dist[i][j] if dist[i][j] < dist[i][k] + dist[k][j] else dist[i][k] + dist[k][j]

    ans = float('inf')
    for r in itertools.permutations(RR):
        move = 0
        for i in range(R - 1):
            a = r[i] - 1
            b = r[i+1] - 1
            move += dist[a][b]
        ans = ans if ans < move else move

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

def main():
    N, M, R = map(int, input().split())
    RR = tuple(map(int, input().split()))
    ABC = {tuple(map(int, input().split())) for _ in range(M)}

    dist = [[float('inf')] * N for _ in range(N)]
    for a, b, c in ABC:
        dist[a-1][b-1] = dist[b-1][a-1] = c
        dist[a-1][a-1] = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = dist[i][j] if dist[i][j] < dist[i][k] + dist[k][j] else dist[i][k] + dist[k][j]

    ans = float('inf')
    for r in itertools.permutations(RR):
        move = 0
        for i in range(R - 1):
            a = r[i] - 1
            b = r[i+1] - 1
            move += dist[a][b]
        ans = ans if ans < move else move

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

def main():
    N, M, R = map(int, input().split())
    RR = tuple(map(int, input().split()))
    ABC = {tuple(map(int, input().split())) for _ in range(M)}

    dist = [[float('inf')] * N for j in range(N)]
    for a, b, c in ABC:
        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):
                dist[i][j] = dist[i][j] if dist[i][j] < dist[i][k] + dist[k][j] else dist[i][k] + dist[k][j]

    ans = float('inf')
    for r in itertools.permutations(RR):
        move = 0
        for i in range(R - 1):
            a = r[i] - 1
            b = r[i+1] - 1
            move += dist[a][b]
        ans = ans if ans < move else move

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

def main():
    N, M, R = map(int, input().split())
    RR = tuple(map(int, input().split()))
    ABC = {tuple(map(int, input().split())) for _ in range(M)}

    dist = [[float('inf') for i in range(N)] for j in range(N)]
    for a, b, c in ABC:
        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):
                dist[i][j] = dist[i][j] if dist[i][j] < dist[i][k] + dist[k][j] else dist[i][k] + dist[k][j]

    ans = float('inf')
    for r in itertools.permutations(RR):
        move = 0
        for i in range(R - 1):
            a = r[i] - 1
            b = r[i+1] - 1
            move += dist[a][b]
        ans = ans if ans < move else move

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

def main():
    N, M, R = map(int, input().split())
    RR = tuple(map(int, input().split()))
    ABC = {tuple(map(int, input().split())) for _ in range(M)}

    dist = [[float('inf') for i in range(N + 1)] for j in range(N + 1)]
    for a, b, c in ABC:
        dist[a][b] = dist[b][a] = c
    for k in range(1, N + 1):
        for i in range(1, N + 1):
            for j in range(1, N + 1):
                dist[i][j] = dist[i][j] if dist[i][j] < dist[i][k] + dist[k][j] else dist[i][k] + dist[k][j]

    ans = float('inf')
    for r in itertools.permutations(RR):
        move = 0
        for i in range(R - 1):
            a = r[i]
            b = r[i+1]
            move += dist[a][b]
        ans = ans if ans < move else move

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

def main():
    N, M, R = map(int, input().split())
    RR = tuple(map(int, input().split()))
    ABC = {tuple(map(int, input().split())) for _ in range(M)}

    dist = [[float('inf') for i in range(N + 1)] for j in range(N + 1)]
    for a, b, c in ABC:
        dist[a][b] = dist[b][a] = c
    for k, i, j in itertools.product(range(1, N + 1), repeat=3):
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    ans = float('inf')
    for r in itertools.permutations(RR):
        move = 0
        for i in range(R - 1):
            a = r[i]
            b = r[i+1]
            move += dist[a][b]
        ans = min(ans, move)

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

def main():
    N, M, R = map(int, input().split())
    RR = tuple(map(int, input().split()))
    ABC = {tuple(map(int, input().split())) for _ in range(M)}

    dist = [[float('inf') for i in range(N + 1)] for j in range(N + 1)]
    for a, b, c in ABC:
        dist[a][b] = dist[b][a] = c
    for k, i, j in itertools.product(range(N + 1), repeat=3):
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    ans = float('inf')
    for r in itertools.permutations(RR):
        move = 0
        for i in range(R - 1):
            a = r[i]
            b = r[i+1]
            move += dist[a][b]
        ans = min(ans, move)

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

def main():
    N, M, R = map(int, input().split())
    RR = tuple(map(int, input().split()))
    ABC = {tuple(map(int, input().split())) for _ in range(M)}

    dist = [[float('inf') for i in range(N + 1)] for j in range(N + 1)]
    for a, b, c in ABC:
        dist[a][b] = dist[b][a] = c
    for k in range(N + 1):
        for i in range(N + 1):
            for j in range(N + 1):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    ans = float('inf')
    for r in itertools.permutations(RR):
        move = 0
        for i in range(R - 1):
            a = r[i]
            b = r[i+1]
            move += dist[a][b]
        ans = min(ans, move)

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

n, m, r = [int(x) for x in input().strip().split()]
targets = [int(x) for x in input().strip().split()]

LARGE = 100000 * 201
roads = [[LARGE for _ in range(n+1)] for _ in range(n+1)]
for i in range(n+1):
    roads[i][i] = 0

for _ in range(m):
    a, b, c = [int(x) for x in input().strip().split()]
    roads[a][b] = roads[b][a] = c

# Warshall-Floyd Algorithm
for k in range(1, n+1):
    for i in range(1, n+1):
        d_ik = roads[i][k]
        for j in range(1, n+1):
            d_ij = roads[i][j]
            d_kj = roads[k][j]
            if d_ij > d_ik + d_kj:
                roads[i][j] = roads[j][i] = d_ik + d_kj

way_abcd = {}
if r >= 4:
    for seq in permutations(targets, 4):
        if tuple(seq) in way_abcd:
            continue
        a, b, c, d = seq
        if roads[a][b] + roads[c][d] < roads[a][c] + roads[b][d]:
            way_abcd[(a,b,c,d)] = way_abcd[(a,c,b,d)] = way_abcd[(d,b,c,a)] = way_abcd[(d,c,b,a)] = roads[a][b] + roads[b][c] + roads[c][d]
        else:
            way_abcd[(a,b,c,d)] = way_abcd[(a,c,b,d)] = way_abcd[(d,b,c,a)] = way_abcd[(d,c,b,a)] = roads[a][c] + roads[c][b] + roads[b][d]

best = LARGE
done = set()
for seq in permutations(targets):
    total = 0
    i = 0
    m = len(seq) - 1
    while i < m:
        if m - i >= 4:
            total += way_abcd[(seq[i], seq[i+1], seq[i+2], seq[i+3])]
            i += 3
        else:
            total += roads[seq[i]][seq[i+1]]
            i += 1
    if total < best:
        best = total
print(best)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

n, m, r = [int(x) for x in input().strip().split()]
targets = [int(x) for x in input().strip().split()]

LARGE = 100000 * 201
roads = [[LARGE for _ in range(n+1)] for _ in range(n+1)]
for i in range(n+1):
    roads[i][i] = 0

for _ in range(m):
    a, b, c = [int(x) for x in input().strip().split()]
    roads[a][b] = roads[b][a] = c

# Warshall-Floyd Algorithm
for k in range(1, n+1):
    for i in range(1, n+1):
        d_ik = roads[i][k]
        for j in range(1, n+1):
            d_ij = roads[i][j]
            d_kj = roads[k][j]
            if d_ij > d_ik + d_kj:
                roads[i][j] = roads[j][i] = d_ik + d_kj

best = LARGE
for seq in permutations(targets, r):
    it = iter(seq)
    a = next(it)
    dist = 0
    for b in it:
        dist += roads[a][b]
        a = b
    if dist < best:
        best = dist
print(best)

Submission status: Time Limit Exceeded

Solution code:
import itertools

def main():
    N, M, R = map(int, input().split())
    RR = tuple(map(int, input().split()))
    ABC = {tuple(map(int, input().split())) for _ in range(M)}

    dist = [[100001 for i in range(N + 1)] for j in range(N + 1)]
    for a, b, c in ABC:
        dist[a][b] = dist[b][a] = c
    for k in range(N + 1):
        for i in range(N + 1):
            for j in range(N + 1):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    ans = float('inf')
    for r in itertools.permutations(range(1, min(N + 1, 9))):
        move = 0
        flag = {i: 1 for i in RR}
        for i in range(min(N - 1, 8)):
            a = r[i]
            b = r[i+1]
            move += dist[a][b]
            flag[a] = flag[b] = 0
            if sum(flag.values()) == 0: break
        ans = min(ans, move)

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

def main():
    N, M, R = map(int, input().split())
    RR = tuple(map(int, input().split()))
    ABC = {tuple(map(int, input().split())) for _ in range(M)}

    dist = [[100001 for i in range(N + 1)] for j in range(N + 1)]
    for a, b, c in ABC:
        dist[a][b] = dist[b][a] = c
    for k in range(N + 1):
        for i in range(N + 1):
            for j in range(N + 1):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    ans = float('inf')
    for r in itertools.permutations(range(1, N + 1)):
        move = 0
        flag = {i: 1 for i in RR}
        for i in range(N - 1):
            a = r[i]
            b = r[i+1]
            move += dist[a][b]
            flag[a] = flag[b] = 0
            if sum(flag.values()) == 0: break
        ans = min(ans, move)

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
# ワーシャル・フロイド法
# <https://ja.wikipedia.org/wiki/%E3%83%AF%E3%83%BC%E3%82%B7%E3%83%A3%E3%83%AB%E2%80%93%E3%83%95%E3%83%AD%E3%82%A4%E3%83%89%E6%B3%95>

import collections as cl
import numpy as np
import sys
import itertools

# コマンドライン引き数の取得
args = sys.argv
if len(args) < 2:
    isDebug = False
elif args[1] == 'DEBUG':
    isDebug = True
else:
    isDebug = False


# 宣言
result = sys.maxsize
A_list = []
B_list = []
C_list = []

# 入力部
if isDebug:
    # sample1
    # (N, M, R) = (3, 3, 3)
    # r = (1, 2, 3)
    # A_list = [1, 2, 3]
    # B_list = [2, 3, 1]
    # C_list = [1, 1, 4]

    # sample2
    # (N, M, R) = (3, 3, 2)
    # r = (1, 3)
    # A_list = [2, 1, 1]
    # B_list = [3, 3, 2]
    # C_list = [2, 6, 2]

    # sample3
    (N, M, R) = (4, 6, 3)
    r = (2, 3, 4)
    A_list = [1, 2, 4, 1, 4, 3]
    B_list = [2, 3, 3, 4, 2, 1]
    C_list = [4, 3, 1, 1, 2, 6]

else:
    (N, M, R) = map(int, input().split(' '))
    r = map(int, input().split(' '))
    
    for i in range(M):
        (A, B, C) = map(int, input().split(' '))
        A_list.append(A)
        B_list.append(B)
        C_list.append(C)

# 処理部
# グラフ初期化
graph = (np.identity(N) - 1) * -1
graph *= sys.maxsize
for i in range(M):
    graph[A_list[i] - 1][B_list[i] - 1] = C_list[i]
    graph[B_list[i] - 1][A_list[i] - 1] = C_list[i]

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

# 経路長計算
for root in itertools.permutations(r):
    distance = 0
    for i in range(len(root) - 1):
        distance += graph[root[i]-1][root[i+1]-1]                 
    if result > distance:
        result = distance

# 出力部
print(int(result))

Submission status: Time Limit Exceeded

Solution code:
n, m, r = map(int, input().split())
*R, = map(int, input().split())
E = [[10**18]*n for i in range(n)]
for i in range(n):
    E[i][i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    E[a-1][b-1] = E[b-1][a-1] = c
for k in range(n):
    for i in range(n):
        for j in range(n):
            E[i][j] = min(E[i][j], E[i][k] + E[k][j])

memo = {}
ALL = 2**r-1
def dfs(state, pos):
    if (state, pos) in memo:
        return memo[state, pos]
    if state == ALL:
        return 0
    res = 10**18
    for i in range(r):
        if state & (1 << i) == 0:
            res = min(res, dfs(state | (1 << i), R[i]-1) + E[pos][R[i]-1])
    memo[state, pos] = res
    return res
print(min(dfs(0, i) for i in range(n)))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python

import sys

p=[0]*10000;mp=[];inf=65536;v=[0]*1000;t=[0]*1000
 
 
ans=100000

 
n,m,r=map(int,sys.stdin.readline().split(" "))

s=sys.stdin.readline().replace("\n","")

p=map(int,s.split(" "))


def dsss(x,now):
	global ans
	if x==r+1:
		ans=min(ans,now)
		return 
	else :
		for i in range(r):
			if v[p[i]]==0 :
				v[p[i]]=1
				t[x]=p[i]
				if x==1:
					dsss(x+1,now)
				else :
					dsss(x+1,now+mp[p[i]-1][t[x-1]-1])
				v[p[i]]=0
	return 
 
 
for i in range(n+5):
	mp.append(range(n+5))
 
 
for i in range(n+5):
    for j in range(n+5):
        if(i!=j):
            mp[i][j]=inf
 
for i in range(m):
	a,b,c=map(lambda x: int(x),sys.stdin.readline().split(" ",3))
	a-=1;b-=1;
	mp[a][b]=min(mp[a][b],c)
	mp[b][a]=min(mp[b][a],c)
 
for i in range(n):
	for j in range(n):
		for k in range(n):
			mp[j][k]=min(mp[j][k],mp[j][i]+mp[i][k])


dsss(1,0)
 
print ans

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python

import sys

p=[0]*10000;mp=[];inf=65536;v=[0]*10;t=[0]*10
 
 
ans=100000

 
n,m,r=map(int,sys.stdin.readline().split(" "))

s=sys.stdin.readline().replace("\n","")

p=map(int,s.split(" "))


def dsss(x,now):
	global ans
	if x==r+1:
		ans=min(ans,now)
		return 
	else :
		for i in range(r):
			if v[p[i]]==0 :
				v[p[i]]=1
				t[x]=p[i]
				if x==1:
					dsss(x+1,now)
				else :
					dsss(x+1,now+mp[p[i]-1][t[x-1]-1])
				v[p[i]]=0
	return 
 
 
for i in range(n+5):
	mp.append(range(n+5))
 
 
for i in range(n+5):
    for j in range(n+5):
        if(i!=j):
            mp[i][j]=inf
 
for i in range(m):
	a,b,c=map(lambda x: int(x),sys.stdin.readline().split(" ",3))
	a-=1;b-=1;
	mp[a][b]=min(mp[a][b],c)
	mp[b][a]=min(mp[b][a],c)
 
for i in range(n):
	for j in range(n):
		for k in range(n):
			mp[j][k]=min(mp[j][k],mp[j][i]+mp[i][k])
 
dsss(1,0)
 
print ans

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python

import sys

p=[0]*10;mp=[];inf=65536;v=[0]*10;t=[0]*10
 
 
ans=100000
 
n,m,r=map(int,raw_input().split(' '))
 
p=map(int,raw_input().split(' '))
 
def dsss(x,now):
	global ans
	if x==r+1:
		ans=min(ans,now)
		return 
	else :
		for i in range(r):
			if v[p[i]]==0 :
				v[p[i]]=1
				t[x]=p[i]
				if x==1:
					dsss(x+1,now)
				else :
					dsss(x+1,now+mp[p[i]-1][t[x-1]-1])
				v[p[i]]=0
	return 
 
 
for i in range(n+5):
	mp.append(range(n+5))
 
 
for i in range(n+5):
    for j in range(n+5):
        mp[i][j]=inf
 
for i in range(m):
	a,b,c=map(lambda x: int(x),sys.stdin.readline().split(" ",3))
	a-=1;b-=1;
	mp[a][b]=min(mp[a][b],c)
	mp[b][a]=min(mp[b][a],c)
 
for i in range(n):
	for j in range(n):
		for k in range(n):
			mp[j][k]=min(mp[j][k],mp[j][i]+mp[i][k])
 
dsss(1,0)
 
print ans

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python

import sys

p=[0]*10000;mp=[];inf=65536;v=[0]*10000;t=[0]*10000
 
 
ans=100000
 
n,m,r=map(int,raw_input().split(' '))
 
p=map(int,raw_input().split(' '))
 
def dsss(x,now):
	global ans
	if x==r+1:
		ans=min(ans,now)
		return 
	else :
		for i in range(r):
			if v[p[i]]==0 :
				v[p[i]]=1
				t[x]=p[i]
				if x==1:
					dsss(x+1,now)
				else :
					dsss(x+1,now+mp[p[i]-1][t[x-1]-1])
				v[p[i]]=0
	return 
 
 
for i in range(n+5):
	mp.append(range(n+5))
 
 
for i in range(n+5):
    for j in range(n+5):
        mp[i][j]=inf
 
for i in range(m):
	a,b,c=map(lambda x: int(x),sys.stdin.readline().split(" ",3))
	a-=1;b-=1;
	mp[a][b]=min(mp[a][b],c)
	mp[b][a]=min(mp[b][a],c)
 
for i in range(n):
	for j in range(n):
		for k in range(n):
			mp[j][k]=min(mp[j][k],mp[j][i]+mp[i][k])
 
dsss(1,0)
 
print ans

Submission status: Time Limit Exceeded

Solution code:
import sys

p=[0]*10000;mp=[];inf=65536;v=[0]*10000;t=[0]*10000
 
 
ans=100000
 
n,m,r=map(int,raw_input().split(' '))
 
p=map(int,raw_input().split(' '))
 
def dsss(x,now):
	global ans
	if x==r+1:
		ans=min(ans,now)
		return 
	else :
		for i in range(r):
			if v[p[i]]==0 :
				v[p[i]]=1
				t[x]=p[i]
				if x==1:
					dsss(x+1,now)
				else :
					dsss(x+1,now+mp[p[i]-1][t[x-1]-1])
				v[p[i]]=0
	return 
 
 
for i in range(n+5):
	mp.append(range(n+5))
 
 
for i in range(n+5):
    for j in range(n+5):
        mp[i][j]=inf
 
for i in range(m):
	a,b,c=map(int,sys.stdin.readline().split(" ",3))
	a-=1;b-=1;
	mp[a][b]=min(mp[a][b],c)
	mp[b][a]=min(mp[b][a],c)
 
for i in range(n):
	for j in range(n):
		for k in range(n):
			mp[j][k]=min(mp[j][k],mp[j][i]+mp[i][k])
 
dsss(1,0)
 
print ans

Submission status: Time Limit Exceeded

Solution code:
import itertools

N, M, R = map(int, input().split())
r = [a-1 for a in list(map(int, input().split()))]
d = [[float('inf')]*N for _ in range(N)]

for _ in range(M):
    a, b, c = map(int, input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
    
for i in range(N):
    d[i][i] = 0
    
for k in range(N):
    for i in range(N):
        for j in range(N):
            dd = d[i][k] + d[k][j]
            if dd < d[i][j]:
                d[i][j] = dd

ans = float("inf")

for perm in itertools.permutations(r):
    a = 0
    for i in range(len(perm)-1):
        a += d[perm[i]][perm[i+1]]
    ans = min(a, ans)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
p=[0]*10000;mp=[];inf=65536;v=[0]*10000;t=[0]*10000


ans=100000

n,m,r=map(int,raw_input().split(' '))

p=map(int,raw_input().split(' '))

def dsss(x,now):
	global ans
	if x==r+1:
		ans=min(ans,now)
		return 
	else :
		for i in range(r):
			if v[p[i]]==0 :
				v[p[i]]=1
				t[x]=p[i]
				if x==1:
					dsss(x+1,now)
				else :
					dsss(x+1,now+mp[p[i]-1][t[x-1]-1])
				v[p[i]]=0
	return 


for i in range(n+5):
	mp.append(range(n+5))


for i in range(n+5):
    for j in range(n+5):
        mp[i][j]=inf

for i in range(m):
	a,b,c=map(int,raw_input().split(' '))
	a-=1;b-=1;
	mp[a][b]=min(mp[a][b],c)
	mp[b][a]=min(mp[b][a],c)

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

dsss(1,0)

print ans

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

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

n, m, r = input_list()
rlist = input_list()
rlist = [r-1 for r in rlist]
d = [[float('inf')]*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()
    d[a-1][b-1] = c
    d[b-1][a-1] = c

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

ans = float('inf')
for p in permutations(rlist):
    distance = 0
    for i in range(r-1):
        distance += d[p[i]][p[i+1]]

    if ans > distance:
        ans = distance

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from itertools import product, groupby, permutations
from math import pi
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = 10 ** 10


def main():
    N, M, R = map(int, input().split())
    r_list = list(map(int, input().split()))
    dp = [[INF] * (N + 1) for _ in range(N + 1)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        dp[A][B] = C
        dp[B][A] = C

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

    for m in range(N + 1):
        for s in range(N + 1):
            for e in range(N + 1):
                if dp[s][m] != INF and dp[m][e] != INF:
                    dist = dp[s][m] + dp[m][e]
                    if dist < dp[s][e]:
                        dp[s][e] = dist

    ans = INF
    for p in permutations(r_list, len(r_list)):
        total = 0
        for i in range(len(p) - 1):
            total += dp[p[i]][p[i + 1]]
            if total >= ans:
                break
        else:
            if total < ans:
                ans = total
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from itertools import product, groupby, permutations
from math import pi
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = 10 ** 10


def main():
    N, M, R = map(int, input().split())
    r_list = list(map(int, input().split()))
    dp = [[INF] * (N + 1) for _ in range(N + 1)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        dp[A][B] = C
        dp[B][A] = C

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

    for m in range(N + 1):
        for s in range(N + 1):
            for e in range(N + 1):
                if dp[s][m] != INF and dp[m][e] != INF:
                    dp[s][e] = min(dp[s][e], dp[s][m] + dp[m][e])

    ans = INF
    for p in permutations(r_list, len(r_list)):
        total = 0
        for i in range(len(p) - 1):
            total += dp[p[i]][p[i + 1]]
        ans = min(ans, total)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, m, R = [int(x) for x in input().split()]
r = [int(x) for x in input().split()]

cost = [[int(1e9) for x in range(n + 1)] for y in range(n + 1)]

for _ in range(m):
    a, b, c = [int(x) for x in input().split()]
    cost[a][b] = cost[b][a] = min(c, cost[b][a])

for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if cost[i][k] + cost[k][j] < cost[i][j] and i != j:
                cost[i][j] = cost[i][k] + cost[k][j]

from itertools import permutations

minCost = int(1e9)

for perm in permutations(range(R)):
    totalCost = 0
    for i in range(1, len(perm)):
        totalCost += cost[r[perm[i]]][r[perm[i - 1]]]
    minCost = min(minCost, totalCost)

print(minCost)

Submission status: Time Limit Exceeded

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

cost = [[int(2e9) for x in range(n + 1)] for y in range(n + 1)]

for _ in range(m):
    a, b, c = list(map(int, input().split()))
    cost[a][b] = min(c, cost[a][b])
    cost[b][a] = min(c, cost[b][a])

for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if cost[i][k] + cost[k][j] < cost[i][j] and i != j:
                cost[i][j] = cost[i][k] + cost[k][j]

from itertools import permutations

minCost = int(2e9)

for perm in permutations(range(R)):
    totalCost = 0
    for i in range(1, len(perm)):
        totalCost += cost[r[perm[i]]][r[perm[i - 1]]]
    minCost = min(minCost, totalCost)

print(minCost)

Submission status: Time Limit Exceeded

Solution code:
import itertools

INF = 1e9
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
d = [[INF for j in range(N + 1)] for i in range(N + 1)]

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

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

p = itertools.permutations(r)
res = INF

for l in p:
    s = 0
    for i in range(R - 1):
        s += d[l[i]][l[i + 1]]
        if s > res:
            break
    res = min(res, s)

print(res)

Submission status: Time Limit Exceeded

Solution code:
import itertools

INF = 1e9
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
d = [[INF for j in range(N + 1)] for i in range(N + 1)]

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

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

p = itertools.permutations(r)
result = INF

for l in p:
    result = min(result, sum([d[l[i]][l[i + 1]] for i in range(R - 1)]))

print(result)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
import sys

N, M, R = map(int, sys.stdin.readline().split())
r = [int(i) - 1 for i in sys.stdin.readline().split()]
d = [[float('inf')] * N for j in range(N)]
for i in range(M):
    A, B, C = map(int, sys.stdin.readline().split())
    d[A-1][B-1] = min(d[A-1][B-1], C)
    d[B-1][A-1] = min(d[B-1][A-1], C)
for k in range(N):
    for s in range(N):
        for e in range(N):
            d[s][e] = min(d[s][e], d[s][k] + d[k][e])
l = float('inf')
for o in permutations(r):
    tmp_l = 0
    for s, e in zip(o[:-1], o[1:]):
        tmp_l = tmp_l + d[s][e]
    l = min(l, tmp_l)
print(l)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

N,M,R = map(int,input().split())
rseq = list(map(int,input().split()))
graph = [[-1]*N for x in range(N)]

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

#FloydWarshall
for k in range(N):
    for i in range(N):
        for j in range(N):
            if graph[i][k] == -1 or graph[k][j] == -1:
                continue
            new_dist = graph[i][k] + graph[k][j]
            if graph[i][j] == -1 or graph[i][j] > new_dist:
                graph[i][j] = new_dist

minimum = 200000000
for p in permutations(rseq):
    total = 0
    for i in range(1,R):
        total += graph[p[i]-1][p[i-1]-1]
        if total > minimum:
            break
    if total < minimum:
        minimum = total
print(minimum)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

N,M,R = map(int,input().split())
rseq = list(map(int,input().split()))
graph = [[-1]*N for x in range(N)]

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

#FloydWarshall
for k in range(N):
    for i in range(N):
        for j in range(N):
            if graph[i][k] == -1 or graph[k][j] == -1:
                continue
            if graph[i][j] == -1 or graph[i][j] > graph[i][k] + graph[k][j]:
                graph[i][j] = graph[i][k] + graph[k][j]

minimum = 200000000
for p in permutations(rseq):
    total = 0
    for i in range(1,R):
        total += graph[p[i]-1][p[i-1]-1]
        if total > minimum:
            break
    if total < minimum:
        minimum = total
print(minimum)