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:
N, M, R = map(int, input().split())
R_LIST = list(map(int, input().split()))
ABC = []
for _ in range(M):
    a,b,c = map(int, input().split())
    ABC.append((a,b,c))
    
edges = ABC[:]

 
# 無効グラフなので双方向にする
graph = {}
for a,b,c in edges:
    if not a in graph:
        graph[a] = {}
    if not b in graph:
        graph[b] = {}
    graph[a][b] = c
    graph[b][a] = c
 
 
from heapq import heappush, heappop
 
def dijkstra(graph, start):
    A = [None] * (N+1)
    queue = [(0, start)]
    while queue:
        path_len, v = heappop(queue)
        if A[v] is None: # v is unvisited
            A[v] = path_len
            for w, edge_len in graph[v].items():
                if A[w] is None:
                    heappush(queue, (path_len + edge_len, w))
 
    # to give same result as original, assign zero distance to unreachable vertices             
    return [0 if x is None else x for x in A]
 

#最短経路
shortest = [[0] * (N+1)]
for i in range(1, N+1):
    shortest.append(dijkstra(graph, i))
    
# 順列全探索
import sys
INT_MAX = sys.maxsize # 9223372036854775807
ans = INT_MAX

import queue

rest = set(R_LIST[:])

import copy  
def dfs(cost,pre,rest):
    if len(rest) == 0:
        return cost
    
    ret = INT_MAX
    for r in rest:
        if pre == None:
            next_cost = 0
        else:
            next_cost = cost + shortest[pre][r]
        
        if next_cost >= ret:
            continue
            
        next_rest = copy.copy(rest)
        next_rest.remove(r)
        
        tmp_ret = dfs(next_cost, r, next_rest)
        ret = min(ret, tmp_ret)
        
    return ret


print(dfs(0, None, rest))

Submission status: Time Limit Exceeded

Solution code:
N, M, R = map(int, input().split())
R_LIST = list(map(int, input().split()))
ABC = []
for _ in range(M):
    a,b,c = map(int, input().split())
    ABC.append((a,b,c))
    
edges = ABC[:]

def warshall_floyd(d, n):
    # d: グラフ二次元リスト
    # n: 頂点数 (0始まり)
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

# グラフ無効グラフ化
graph = [[float("inf") for i in range(N+1)] for i in range(N+1)] 
for x,y,z in edges:
    graph[x][y] = z
    graph[y][x] = z
for i in range(N+1):
    graph[i][i] = 0 #自身のところに行くコストは０

#最短経路
shortest =  warshall_floyd(graph, N+1)
    
# 順列全探索
import sys
INT_MAX = sys.maxsize # 9223372036854775807
ans = INT_MAX

import queue

rest = set(R_LIST[:])

import copy  
def dfs(cost,pre,rest):
    if len(rest) == 0:
        return cost
    
    ret = INT_MAX
    for r in rest:
        if pre == None:
            next_cost = 0
        else:
            next_cost = cost + shortest[pre][r]
        
        if next_cost >= ret:
            continue
            
        next_rest = copy.copy(rest)
        next_rest.remove(r)
        
        tmp_ret = dfs(next_cost, r, next_rest)
        ret = min(ret, tmp_ret)
        
    return ret
        
    

print(dfs(0, None, rest))

Submission status: Time Limit Exceeded

Solution code:
N, M, R = map(int, input().split())
R_LIST = list(map(int, input().split()))
ABC = []
for _ in range(M):
    a,b,c = map(int, input().split())
    ABC.append((a,b,c))
    
    
edges = ABC[:]


def warshall_floyd(d, n):
    # d: グラフ二次元リスト
    # n: 頂点数 (0始まり)
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

# グラフ無効グラフ化
graph = [[float("inf") for i in range(N+1)] for i in range(N+1)] 
for x,y,z in edges:
    graph[x][y] = z
    graph[y][x] = z
for i in range(N+1):
    graph[i][i] = 0 #自身のところに行くコストは０

#最短経路
shortest =  warshall_floyd(graph, N+1)
    
# 順列全探索
import sys
INT_MAX = sys.maxsize # 9223372036854775807
ans = INT_MAX

import queue

rest = set(R_LIST[:])

import copy  
def dfs(cost,pre,rest):
    if len(rest) == 0:
        return cost
    
    ret = INT_MAX
    for r in rest:
        if pre == None:
            next_cost = 0
        else:
            next_cost = cost + shortest[pre][r]
        next_rest = copy.copy(rest)
        next_rest.remove(r)
        
        tmp_ret = dfs(next_cost, r, next_rest)
        ret = min(ret, tmp_ret)
        
    return ret
        
    

print(dfs(0, None, rest))

Submission status: Time Limit Exceeded

Solution code:
N, M, R = map(int, input().split())
R_LIST = list(map(int, input().split()))
ABC = []
for _ in range(M):
    a,b,c = map(int, input().split())
    ABC.append((a,b,c))
    
edges = ABC[:]


def warshall_floyd(d, n):
    # d: グラフ二次元リスト
    # n: 頂点数 (0始まり)
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

# グラフ無効グラフ化
graph = [[float("inf") for i in range(N+1)] for i in range(N+1)] 
for x,y,z in edges:
    graph[x][y] = z
    graph[y][x] = z
for i in range(N+1):
    graph[i][i] = 0 #自身のところに行くコストは０

#最短経路
shortest =  warshall_floyd(graph, N+1)
    
# 順列全探索
import sys
INT_MAX = sys.maxsize # 9223372036854775807
ans = INT_MAX

import queue

q = queue.Queue()
travels = R_LIST[:]

for t in travels:
    q.put((
        0,
        (t,)
    ))


def dfs(cost,past):
    #print('aaa', past)
    if len(past) == len(travels):
        return cost
    
    ret = INT_MAX
    for t in travels:
        if t in past:
            continue
        
        if len(past) == 0:
            tmp_ret = dfs(0, [t])
            ret = min(ret, tmp_ret)
        else:
            next_cost = cost + shortest[past[-1]][t]
            if ret <= next_cost:
                continue

            next_past = past[:] + [t]
            tmp_ret = dfs(next_cost, next_past)
            ret = min(ret, tmp_ret)
        
    return ret

print(dfs(0, []))

Submission status: Time Limit Exceeded

Solution code:
N, M, R = map(int, input().split())
R_LIST = list(map(int, input().split()))
ABC = []
for _ in range(M):
    a,b,c = map(int, input().split())
    ABC.append((a,b,c))
edges = ABC[:]


def warshall_floyd(d, n):
    # d: グラフ二次元リスト
    # n: 頂点数 (0始まり)
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

# グラフ無効グラフ化
graph = [[float("inf") for i in range(N)] for i in range(N)] 
for x,y,z in edges:
    graph[x-1][y-1] = z
    graph[y-1][x-1] = z
for i in range(N):
    graph[i][i] = 0 #自身のところに行くコストは０

#最短経路
shortest =  warshall_floyd(graph, N)
    
# 順列全探索
import sys
INT_MAX = sys.maxsize # 9223372036854775807
ans = INT_MAX

import itertools
line = R_LIST
for l in itertools.permutations(line):
    #print(l)
    tmp_len = 0
    for a,b in zip(l[:-1], l[1:]):
        tmp_len += shortest[a-1][b-1]

    #print(tmp_len)
    ans = min(ans, tmp_len)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M, R = map(int, input().split())
R_LIST = list(map(int, input().split()))
ABC = []
for _ in range(M):
    a,b,c = map(int, input().split())
    ABC.append((a,b,c))
    
edges = ABC[:]


def warshall_floyd(d, n):
    import copy
    # d: グラフ二次元リスト
    # n: 頂点数 (0始まり)
    #d[i][j]: iからjへの最短距離
    for i, d_sub in enumerate(copy.deepcopy(d)):
        for j, j_v in enumerate(d_sub):
            for k, k_v in enumerate(d_sub):
                d[i][j] = min(j_v,k_v + d[k][j])
    return d

# グラフ無効グラフ化
graph = [[float("inf") for i in range(N+1)] for i in range(N+1)] 
for x,y,z in edges:
    graph[x][y] = z
    graph[y][x] = z
for i in range(N+1):
    graph[i][i] = 0 #自身のところに行くコストは０

#最短経路
shortest =  warshall_floyd(graph, N+1)
    
# 順列全探索
import sys
INT_MAX = sys.maxsize # 9223372036854775807
ans = INT_MAX

import itertools
line = R_LIST
for l in itertools.permutations(line):
    #print(l)
    tmp_len = 0
    for a,b in zip(l[:-1], l[1:]):
        tmp_len += shortest[a][b]

    #print(tmp_len)
    ans = min(ans, tmp_len)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M, R = map(int, input().split())
R_LIST = list(map(int, input().split()))
ABC = []
for _ in range(M):
    a,b,c = map(int, input().split())
    ABC.append((a,b,c))
    
edges = ABC[:]


def warshall_floyd(d, n):
    # d: グラフ二次元リスト
    # n: 頂点数 (0始まり)
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

# グラフ無効グラフ化
graph = [[float("inf") for i in range(N+1)] for i in range(N+1)] 
for x,y,z in edges:
    graph[x][y] = z
    graph[y][x] = z
for i in range(N+1):
    graph[i][i] = 0 #自身のところに行くコストは０

#最短経路
shortest =  warshall_floyd(graph, N+1)
    
# 順列全探索
import sys
INT_MAX = sys.maxsize # 9223372036854775807
ans = INT_MAX

import itertools
line = R_LIST
for l in itertools.permutations(line):
    #print(l)
    tmp_len = 0
    for a,b in zip(l[:-1], l[1:]):
        tmp_len += shortest[a][b]

    #print(tmp_len)
    ans = min(ans, tmp_len)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M, R = map(int, input().split())
R_LIST = list(map(int, input().split()))
ABC = []
for _ in range(M):
    a,b,c = map(int, input().split())
    ABC.append((a,b,c))
    
edges = ABC[:]

# 無効グラフなので双方向にする
graph = {}
for a,b,c in edges:
    if not a in graph:
        graph[a] = {}
    if not b in graph:
        graph[b] = {}
    graph[a][b] = c
    graph[b][a] = c


from heapq import heappush, heappop

def dijkstra(graph, start):
    A = [None] * (N+1)
    queue = [(0, start)]
    while queue:
        path_len, v = heappop(queue)
        if A[v] is None: # v is unvisited
            A[v] = path_len
            for w, edge_len in graph[v].items():
                if A[w] is None:
                    heappush(queue, (path_len + edge_len, w))

    # to give same result as original, assign zero distance to unreachable vertices             
    return [0 if x is None else x for x in A]


shortest = [[0] * (N+1)]
for i in range(1, N+1):
    shortest.append(dijkstra(graph, i))
    
#print(shortest)

import sys
INT_MAX = sys.maxsize # 9223372036854775807
ans = INT_MAX

import itertools
line = R_LIST
for l in itertools.permutations(line):
    #print(l)
    tmp_len = 0
    for a,b in zip(l[:-1], l[1:]):
        tmp_len += shortest[a][b]

    #print(tmp_len)
    ans = min(ans, tmp_len)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

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

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

ans = 10 ** 12

for each in permutations(r):
    t_dis = 0
    for i in range(R - 1):
        t_dis += d[each[i]][each[i + 1]]

    ans = min(ans, t_dis)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

INF=1145141919810

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

road=[[0 if x==y else INF for y in range(N+1)] for x in range(N+1)]

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

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

print(min(sum(road[p[i-1]][p[i]] for i in range(1, R)) for p in permutations(r)))

Submission status: Time Limit Exceeded

Solution code:
import itertools
N, M, R = map(int, input().split())
INF = 2 ** 63 - 1
d = [[INF for i in range(N+1)] for j in range(N+1)]
r = list(map(int, input().split()))
r = list(itertools.permutations(r))
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):
    d[i][i] = 0


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

ans = INF
for path in r:
    anstemp = 0
    for i in range(R-1):
        anstemp += d[path[i]][path[i+1]]
    ans = min(anstemp, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
def warshall_floyd(n,e):
  INF=float("inf")
  g=[[INF]*n for _ in range(n)]
  for i in range(n):g[i][i]=0
  for a,b,c in e:g[a][b],g[b][a]=c,c
  for k in range(n):
    for i in range(n):
      for j in range(n):g[i][j]=min(g[i][k]+g[k][j],g[i][j])
  return g
n,m,rl=map(int,input().split());r,e=list(map(lambda x:int(x)-1,input().split())),[]
for i in range(m):x,y,z=map(int,input().split());e.append([x-1,y-1,z])
d=warshall_floyd(n,e)
a=float("inf")
for i in permutations(range(rl)):
  aa=0
  for x,y in zip(i,i[1:]):aa+=d[r[x]][r[y]]
  a=min(a,aa)
print(a)

Submission status: Time Limit Exceeded

Solution code:
def warshall_floyd(n,e):
  INF=float("inf")
  g=[[INF]*n for _ in range(n)]
  for i in range(n):g[i][i]=0
  for a,b,c in e:g[a][b],g[b][a]=c,c
  for k in range(n):
    for i in range(n):
      for j in range(n):g[i][j]=min(g[i][k]+g[k][j],g[i][j])
  return g
n,m,rl=map(int,input().split());r,e=list(map(int,input().split())),[]
for i in range(m):x,y,z=map(int,input().split());e.append([x-1,y-1,z])
d=warshall_floyd(n,e)
a=float("inf")
from itertools import permutations
for i in permutations(range(rl)):
  aa=0
  for x,y in zip(i,i[1:]):aa+=d[r[x]-1][r[y]-1]
  a=min(a,aa)
print(a)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
def warshall_floyd(n,e):
  INF=float("inf")
  g=[[INF]*n for _ in range(n)]
  for i in range(n):g[i][i]=0
  for a,b,c in e:g[a][b],g[b][a]=c,c
  for k in range(n):
    for i in range(n):
      for j in range(n):g[i][j]=min(g[i][k]+g[k][j],g[i][j])
  return g
n,m,rl=map(int,input().split());r,e=list(map(int,input().split())),[]
for i in range(m):x,y,z=map(int,input().split());e.append([x-1,y-1,z])
d=warshall_floyd(n,e)
a=float("inf")
for i in permutations(range(rl)):
  aa=0
  for x,y in zip(i,i[1:]):aa+=d[r[x]-1][r[y]-1]
  a=min(a,aa)
print(a)

Submission status: Time Limit Exceeded

Solution code:
import heapq

N,M,R = map(int,input().split())
r = list(map(int,input().split()))
r = [a-1 for a in r]
paper = set()
T = [[] for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    T[a].append((c,b))
    T[b].append((c,a))

memo = {}
def distance(a,b):
    #print('distance(',a,',',b,') =?')
    if a > b:
        a,b = b,a
    if (a,b) in memo.keys():
        return memo[(a,b)]
    q = []
    heapq.heappush(q, (0,a))
    try:
        while True:
            c, t = heapq.heappop(q)
            if t == b:
                memo[(a,b)] = c
                #print('distance(',a,',',b,') =',c)
                return c
            for i in T[t]:
                heapq.heappush(q, (c+i[0],i[1]))
    except IndexError:
        pass

inf = 1 << 60
arrived = [False] * R
ans = inf

def calc(src, rest, total):
    global ans
    if total >= ans:
        return
    if rest == 0:
        ans = min(ans,total)
        return

    for i in range(R):
        if not arrived[i]:
            arrived[i] = True
            calc(r[i], rest-1, total + distance(src,r[i]))
            arrived[i] = False

for i in range(R):
    arrived[i] = True
    calc(r[i], R-1, 0)
    arrived[i] = False

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

N,M,R = map(int,input().split())
r = list(map(int,input().split()))
r = [a-1 for a in r]
paper = set()
T = [[] for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    T[a].append((c,b))
    T[b].append((c,a))

memo = {}
def distance(a,b):
    #print('distance(',a,',',b,') =?')
    if a > b:
        a,b = b,a
    if (a,b) in memo.keys():
        return memo[(a,b)]
    q = []
    heapq.heappush(q, (0,a))
    try:
        while True:
            c, t = heapq.heappop(q)
            if t == b:
                memo[(a,b)] = c
                #print('distance(',a,',',b,') =',c)
                return c
            for i in T[t]:
                heapq.heappush(q, (c+i[0],i[1]))
    except IndexError:
        pass

inf = 1 << 60
arrived = [False] * R
def calc(src, rest):
    if rest == 0:
        return 0
    ret = inf
    for i in range(R):
        if not arrived[i]:
            arrived[i] = True
            ret = min(ret, distance(src,r[i]) + calc(r[i], rest-1))
            arrived[i] = False
    return ret

ans = inf
for i in range(R):
    arrived[i] = True
    ans1 = calc(r[i], R-1)
    #print('ans1',ans1)
    ans = min(ans, ans1)
    arrived[i] = False

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
n,m,rl=map(int,input().split());r=list(map(int,input().split()))
d=[[float("inf")for _ in range(n)]for _ in range(n)]
for i in range(m):
  x,y,z=map(int,input().split())
  d[x-1][y-1],d[y-1][x-1]=z,z
for i in range(n):d[i][i]=0
for k in range(n):
  for i in range(n):
    for j in range(n):d[i][j]=min(d[i][j],d[i][k]+d[k][j])
a=float("inf")
for i in permutations(r,rl):
  aa=0
  for j in range(rl-1):aa+=d[i[j]-1][i[j+1]-1]
  a=min(a,aa)
print(a)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N,M,R = map(int,input().split())
r = list(map(lambda x:int(x)-1,input().split()))
ABC = [list(map(int,input().split())) for _ in range(M)]
INF = 10**7
d = [[INF]*N for _ in range(N)]

for A,B,C in ABC:
    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(i+1,N):
            d[i][j] = min(d[i][j],d[i][k]+d[k][j])
            d[j][i] = d[i][j]
ans = INF * M
for r in itertools.permutations(r):
    S = 0
    for i,ri in enumerate(r[:-1]):
        S += d[ri][r[i+1]]
    ans = min(ans,S)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class WarshallFloyd():
    def __init__(self, N):
        self.N = N
        self.d = [[float("inf") for i in range(N)]
                  for i in range(N)]  # d[u][v] : 辺uvのコスト(存在しないときはinf)

    def add(self, u, v, c, directed=False):
        """
        0-indexedであるに注意
        u = from, v = to, c = cost
        directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.d[u][v] = c
            self.d[v][u] = c
        else:
            self.d[u][v] = c

    def WarshallFloyd_search(self):
        # これを d[i][j]: iからjへの最短距離 にする
        # TODO verify both in directed and non-directed
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    self.d[i][j] = min(
                        self.d[i][j], self.d[i][k] + self.d[k][j])
        for i in range(self.N):
            self.d[i][i] = 0
        return self.d


import itertools

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
ABC = [list(map(int, input().split())) for i in range(M)]
graph = WarshallFloyd(N)
for a, b, c in ABC:
    graph.add(a-1, b-1, c)

d = graph.WarshallFloyd_search()
ans = float('inf')
for each in itertools.permutations(r):
    cur = 0
    for i in range(R - 1):
        cur += d[each[i] - 1][each[i + 1] - 1]
    ans = min(ans, cur)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#じゅっぴーフロイド
from collections import*
from itertools import*
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(1,n+1):
        for i in range(1,n+1):
            for j in range(1,n+1):
                d[(i,j)] = min(d[(i,j)],d[(i,k)] + d[(k,j)])
    return d

##############################
n,w,r = map(int,input().split()) #n:頂点数　w:辺の数
d = defaultdict(lambda:float("inf"))
*r,=map(int,input().split())
#d[u][v] : 辺uvのコスト(存在しないときはinf)

for i in range(w):
    x,y,z = map(int,input().split())
    d[(x,y)] = z
    d[(y,x)] = z
#print(d)
for i in range(n):
    d[(i,i)] = 0 #自身のところに行くコストは０
d=warshall_floyd(d)
#print(d)
#print([d[i] for i in permutations(r)])
print(min(sum(d[(s,t)]for s,t in zip(i,i[1:]))for i in permutations(r)))

Submission status: Time Limit Exceeded

Solution code:
import itertools
N,M,R=map(int,input().split())
r=list(map(int,input().split()))

L=[[10**15 for i in range(N)]for j in range(N)]
for i in range(N):
    L[i][i]=0
for a in range(M):
    A,B,C=map(int,input().split())
    L[A-1][B-1]=C
    L[B-1][A-1]=C

#print(L)

for c in range(N):
    for a in range(N):
        for b in range(N):
            L[a][b]=min(L[a][b],L[a][c]+L[c][b])
#print(L)
LIS=list(itertools.permutations(r))
#print(LIS)
ans=10**15
#print(LIS[0][2])
for i in range(len(LIS)):
    cnt=0
    for x in range(1,len(r)):
        #print(i,x)
        cnt+=L[LIS[i][x-1]-1][LIS[i][x]-1]
    if cnt<ans:
        ans=cnt
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
N, M, R = map(int, input().split())
r = list(map(lambda x: int(x) - 1, input().split()))
G = [[float('inf')] * N for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    G[a][b] = c
    G[b][a] = c


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


ans = float('inf')
for perm in permutations(r):
    tmp = 0
    for i in range(R - 1):
        tmp += G[perm[i]][perm[i + 1]]
    ans = min(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import numpy as np
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import math
import itertools

f_inf = float('inf')

N,M,R = map(int,input().split())
nodes = list(map(int,input().split()))
ways = []
for i in range(M):
    a,b,c = map(int,input().split())
    ways.append([a,b,c])

def warshall_floyd(n):
    dp = [[f_inf for i in range(N)] for j in range(N)]
    for i in range(n):
        dp[i][i] = 0
    for way in ways:
        dp[way[0]-1][way[1]-1] = way[2]
        dp[way[1]-1][way[0]-1] = way[2]

    for i in range(N):#頂点数　ノード数
        for j in range(N):#始点
            for k in range(N):#終点
                dp[j][k] = min(dp[j][k],dp[j][i]+dp[i][k])

    return dp


dp = warshall_floyd(N)
routes = list(itertools.permutations(nodes))

ans = f_inf
for route in routes:
#     route = list(print(route))
    tmp = 0
    for i in range(len(route)-1):
        # print(route[i])
        tmp += dp[route[i]-1][route[i+1]-1]
    ans = min(ans,tmp)


print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
n, m, r = map(int, input().split())
r_list = list(map(int, input().split()))
#ワーシャルフロイド法
inf = 1e18
dist = [[inf for i in range(n)] for j in range(n)]
for i in range(n):
    dist[i][i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    dist[a-1][b-1] = c
    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 = inf               
for v in permutations(r_list, r):
    res = 0
    for i in range(r-1):
        res += dist[v[i]-1][v[i+1]-1]
    if ans > res:
        ans = res
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
n, m, r = [int(item) for item in input().split()]
rs = [int(item) for item in input().split()]
abc = [[int(item) for item in input().split()] for _ in range(m)]

INF = 10**6
path = [[INF] * n for _ in range(n)]
short_path = [[INF] * n for _ in range(n)]
for i in range(n):
    path[i][i] = 0
for a, b, c in abc:
    path[a-1][b-1] = path[b-1][a-1] = c

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

ans = INF
for pattern in permutations(rs):
    distance = 0
    for i in range(1,r):
        distance += short_path[pattern[i-1]-1][pattern[i]-1]
    ans = min(ans, distance)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N, M, R = map(int, input().split())
r = [int(s) - 1 for s in input().split()]
a, b, c = [0] * M, [0] * M, [0] * M
for i in range(M):
    a[i], b[i], c[i] = map(int, input().split())
    a[i] -= 1
    b[i] -= 1

wf = [[float('inf')] * N for _ in range(N)]
for i in range(M):
    wf[a[i]][b[i]] = c[i]
    wf[b[i]][a[i]] = c[i]

for k, i, j in itertools.product(range(N), repeat=3):
    wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j])

x = float('inf')
for route in itertools.permutations(r):
    y = sum(wf[route[i]][route[i + 1]] for i in range(R - 1))
    x = min(x, y)

print(x)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations 
inf=10**10
n, m, r = map(int, input().split())
r=list(map(int, input().split()))
abc=[list(map(int, input().split())) for _ in range(m)]
d=[[inf]*n for i in range(n)]
for i in range(n):
    d[i][i]=0
for ai, bi, ci in abc:
    d[ai-1][bi-1]=ci
    d[bi-1][ai-1]=ci
for k in range(n):
    for i in range(n):
        for j in range(i, n):
            d[i][j]=min(d[i][j], d[i][k]+d[k][j])
            d[j][i]=d[i][j]
p=list(permutations(r))
print(min(sum(d[pi[i]-1][pi[i+1]-1] for i in range(len(r)-1)) for pi in p))

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations 
inf=10**10
n, m, r = map(int, input().split())
r=list(map(int, input().split()))
abc=[list(map(int, input().split())) for _ in range(m)]
d=[[inf]*n for i in range(n)]
for i in range(n):
    d[i][i]=0
for ai, bi, ci in abc:
    d[ai-1][bi-1]=ci
    d[bi-1][ai-1]=ci
for k in range(n):
    for i in range(n):
        for j in range(i, n):
            d[i][j]=min(d[i][j], d[i][k]+d[k][j])
            d[j][i]=min(d[i][j], d[i][k]+d[k][j])
p=list(permutations(r))
print(min(sum(d[pi[i]-1][pi[i+1]-1] for i in range(len(r)-1)) for pi in p))

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations 
inf=10**10
n, m, r = map(int, input().split())
r=list(map(int, input().split()))
abc=[list(map(int, input().split())) for _ in range(m)]
d=[[inf]*n for i in range(n)]
for i in range(n):
    d[i][i]=0
for ai, bi, ci in abc:
    d[ai-1][bi-1]=ci
    d[bi-1][ai-1]=ci
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])
p=list(permutations(r))
print(min(sum(d[pi[i]-1][pi[i+1]-1] for i in range(len(r)-1)) for pi in p))

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations 
inf=float('inf')
n, m, r = map(int, input().split())
r=list(map(int, input().split()))
abc=[list(map(int, input().split())) for _ in range(m)]
d=[[inf]*n for i in range(n)]
for i in range(n):
    d[i][i]=0
for ai, bi, ci in abc:
    d[ai-1][bi-1]=ci
    d[bi-1][ai-1]=ci
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])
p=list(permutations(r))
print(min(sum(d[pi[i]-1][pi[i+1]-1] for i in range(len(r)-1)) for pi in p))

Submission status: Time Limit Exceeded

Solution code:
def getN():
    return int(input())

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

import heapq
inf = 1000000000
ans = inf

def dijkstra(n, graph, start):
    h = []
    routes = [[inf, i] for i in range(n)]
    routes[start][0] = 0
    heapq.heappush(h, routes[start][1])
    while(h):
        cur = heapq.heappop(h)
        for edge in graph[cur]:
            target, cost = edge
            if routes[target][0] > routes[cur][0] + cost:
                routes[target][0] = routes[cur][0] + cost
                heapq.heappush(h, routes[target][1])

    return [route[0] for route in routes]


def dfs(depth, rlist, tmpcost, tmppos, dist):
    if depth == r-1:
        #print("return: cost = {}, terminal = {}".format(tmpcost, tmppos))
        return tmpcost
    else:
        ans = 100000000
        for rnum in rlist:
            if flag[rnum] == 0:
                flag[rnum] = 1
                #print("depth {} pos {} tmpcost {} ".format(depth, tmppos, tmpcost))
                returncost = dfs(depth+1, rlist, tmpcost+dist[rnum-1][tmppos-1], rnum, dist)
                flag[rnum] = 0
                if ans > returncost:
                    ans = returncost
        return ans


n, m, r = getlist()
graph = [[] for i in range(n)]
rlist = getlist()
dist = []
for i in range(m):
    v1, v2, cost = getlist()
    graph[v1-1].append((v2-1, cost))
    graph[v2-1].append((v1-1, cost))

for i in range(n):
    dist.append(dijkstra(n, graph, i))
flag = [0 for i in range(n+1)]

ans_candidate = []
for i in rlist:
    #print("start = {}".format(i))
    flag[i] = 1
    ans_candidate.append(dfs(0, rlist, 0, i, dist))
    flag[i] = 0

print(min(ans_candidate))

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import permutations

def warshall_floyd(d):
    n = len(d)
    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])
    return d


def main():
    input = sys.stdin.readline
    N, M, R = map(int, input().split())
    r = list(map(int, input().split()))

    INF = 10**9
    A = [[INF 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

    A = warshall_floyd(A)

    ans = INF
    for start in r[:2]:
        passed = [start]
        temp_ans = 0
        while len(passed) < len(r):
            cur = INF
            next_start = -1
            for dest in r:
                if dest in passed:
                    continue

                if A[start-1][dest-1] < cur:
                    next_start = dest
                    cur = A[start-1][dest-1]

            passed.append(next_start)
            start = next_start
            temp_ans += cur

        ans = min(ans, temp_ans)

    return ans


if __name__ == '__main__':
    print(main())