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 collections import Counter
def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, m, r = read_line(int, int, int)

rs = [int(r) for r in input().split()]

cities = Counter()

routes = {}
costs = {}
for _ in range(m):
    a, b, c = read_line(int, int, int)

    cities[a] = 1
    cities[b] = 1

    if a in routes:
        routes[a][b] = c
    else:
        routes[a] = { b : c }

    if b in routes:
        routes[b][a] = c
    else:
        routes[b] = { a : c }

for a in cities.keys():
    for b in cities.keys():
        if a not in costs:
            costs[a] = {}
        if b not in costs[a]:
            if a in routes and b in routes[a]:
                costs[a][b] = routes[a][b]
            else:
                costs[a][b] = 100000 + 1

for k in cities.keys():
    for a in cities.keys():
        for b in cities.keys():
            if costs[a][b] > costs[a][k] + costs[k][b]:
                costs[a][b] = costs[a][k] + costs[k][b]

def cost(selected):
    c = 0
    for i in range(len(selected) - 1):
        a = selected[i]
        b = selected[i + 1]
        c += costs[a][b]
    return c

smallest = 100000 + 1

def passing_all_cities(selected):
    for r in rs:
        if r not in selected:
            return False
    return True

def f(selected, rest):
    global smallest
    if len(rest) == 0:
        c = cost(selected)
        if smallest > c:
            smallest = c
    else:
        for i in range(len(rest)):
            r = rest[i]
            rest_copy = rest[:]
            del rest_copy[i]
            if cost(selected + [r]) < smallest:
                f(selected + [r], rest_copy)

f([], list(rs))
print(smallest)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, m, r = read_line(int, int, int)

rs = [int(r) for r in input().split()]

cities = Counter()

routes = {}
costs = {}
for _ in range(m):
    a, b, c = read_line(int, int, int)

    cities[a] = 1
    cities[b] = 1

    if a in routes:
        routes[a][b] = c
    else:
        routes[a] = { b : c }

    if b in routes:
        routes[b][a] = c
    else:
        routes[b] = { a : c }

for a in cities.keys():
    for b in cities.keys():
        if a not in costs:
            costs[a] = {}
        if b not in costs[a]:
            if a in routes and b in routes[a]:
                costs[a][b] = routes[a][b]
            else:
                costs[a][b] = 100000 + 1

for k in cities.keys():
    for a in cities.keys():
        for b in cities.keys():
            if costs[a][b] > costs[a][k] + costs[k][b]:
                costs[a][b] = costs[a][k] + costs[k][b]

def cost(selected):
    c = 0
    for i in range(len(selected) - 1):
        a = selected[i]
        b = selected[i + 1]
        c += costs[a][b]
    return c

smallest = 100000 + 1

def passing_all_cities(selected):
    for r in rs:
        if r not in selected:
            return False
    return True

def f(selected, rest):
    global smallest
    if len(rest) == 0 or passing_all_cities(selected):
        c = cost(selected)
        if smallest > c:
            smallest = c
    else:
        for i in range(len(rest)):
            r = rest[i]
            rest_copy = rest[:]
            del rest_copy[i]
            if cost(selected + [r]) < smallest:
                f(selected + [r], rest_copy)

f([], list(rs))
print(smallest)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, m, r = read_line(int, int, int)

rs = [int(r) for r in input().split()]

cities = Counter()

routes = {}
costs = {}
for _ in range(m):
    a, b, c = read_line(int, int, int)

    cities[a] = 1
    cities[b] = 1

    if a in routes:
        routes[a][b] = c
    else:
        routes[a] = { b : c }

    if b in routes:
        routes[b][a] = c
    else:
        routes[b] = { a : c }

for a in cities.keys():
    for b in cities.keys():
        if a not in costs:
            costs[a] = {}
        if b not in costs[a]:
            if a in routes and b in routes[a]:
                costs[a][b] = routes[a][b]
            else:
                costs[a][b] = 100000 + 1

for k in cities.keys():
    for a in cities.keys():
        for b in cities.keys():
            if costs[a][b] > costs[a][k] + costs[k][b]:
                costs[a][b] = costs[a][k] + costs[k][b]

def cost(selected):
    c = 0
    for i in range(len(selected) - 1):
        a = selected[i]
        b = selected[i + 1]
        c += costs[a][b]
    return c

smallest = 100000 + 1

def passing_all_cities(selected):
    for r in rs:
        if r not in selected:
            return False
    return True

def f(selected, rest):
    global smallest
    if len(rest) == 0 or passing_all_cities(selected):
        c = cost(selected)
        if smallest > c:
            smallest = c
    else:
        for i in range(len(rest)):
            r = rest[i]
            rest_copy = rest[:]
            del rest_copy[i]
            # if cost(selected + [r]) < smallest:
            #     f(selected + [r], rest_copy)
            f(selected + [r], rest_copy)

f([], list(cities.keys()))
print(smallest)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, m, r = read_line(int, int, int)

rs = [int(r) for r in input().split()]

cities = Counter()

routes = {}
costs = {}
for _ in range(m):
    a, b, c = read_line(int, int, int)

    cities[a] = 1
    cities[b] = 1

    if a in routes:
        routes[a][b] = c
    else:
        routes[a] = { b : c }

    if b in routes:
        routes[b][a] = c
    else:
        routes[b] = { a : c }

for a in cities.keys():
    for b in cities.keys():
        if a not in costs:
            costs[a] = {}
        if b not in costs[a]:
            if a in routes and b in routes[a]:
                costs[a][b] = routes[a][b]
            else:
                costs[a][b] = 100000 + 1

for k in cities.keys():
    for a in cities.keys():
        for b in cities.keys():
            if costs[a][b] > costs[a][k] + costs[k][b]:
                costs[a][b] = costs[a][k] + costs[k][b]

def cost(selected):
    c = 0
    for i in range(len(selected) - 1):
        a = selected[i]
        b = selected[i + 1]
        c += costs[a][b]
    return c

smallest = 100000 + 1

def passing_all_cities(selected):
    for r in rs:
        if r not in selected:
            return False
    return True

def f(selected, rest):
    global smallest
    if len(rest) == 0 or passing_all_cities(selected):
        c = cost(selected)
        if smallest > c:
            smallest = c
    else:
        for i in range(len(rest)):
            r = rest[i]
            rest_copy = rest[:]
            del rest_copy[i]
            if cost(selected + [r]) < smallest:
                f(selected + [r], rest_copy)

f([], list(cities.keys()))
print(smallest)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-
import itertools
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
d = [[0 for x in range(N)] for y in range(N)]
ans = float("inf")
for y in range(N):
    for x in range(N):
        d[y][x] = 0 if x == y else float('inf')

for tmp 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 y in range(N):
        if d[y][k] == float('inf'):
            continue
        for x in range(N):
            if d[k][x] == float('inf'):
                continue
            d[y][x] = min(d[y][x], d[y][k]+d[k][x])

for tmp in list(itertools.permutations(r)):
    factor = 0
    for tmp2 in range(0, len(tmp)-1):
        if d[tmp[tmp2]-1][tmp[tmp2+1]-1] != 0 and d[tmp[tmp2]-1][tmp[tmp2+1]-1] != float('inf'):
            factor += d[tmp[tmp2]-1][tmp[tmp2+1]-1]
        else:
            break
    ans = min(ans, factor)
print(ans)

Submission status: Time Limit Exceeded

Solution code:

import itertools
 
N, M, R = map(int, input().split())
rs = map(int, input().split())
rs = list(map(lambda x:x-1 , rs))
ABCs = [list(map(int, input().split())) for i in range(M)]
 
d = [[10**6] * N for i in range(N)]
 
for abc in ABCs:
    d[abc[0]-1][abc[1]-1] = abc[2]
    d[abc[1]-1][abc[0]-1] = abc[2]
 
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])
            
kyori = 0
ans = 10**6
narabi = list(itertools.permutations(rs,R))
for pt in narabi:
    for i in range(len(pt)-1):
        kyori += d[pt[i]][pt[i+1]]
    if kyori < ans:
        ans = kyori
    kyori = 0

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
 
N, M, R = map(int, input().split())
rs = map(int, input().split())
rs = list(map(lambda x:x-1 , rs))
ABCs = [list(map(int, input().split())) for i in range(M)]
 
d = [[10**6] * N for i in range(N)]
 
for abc in ABCs:
    d[abc[0]-1][abc[1]-1] = abc[2]
    d[abc[1]-1][abc[0]-1] = abc[2]
 
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])
            
for i in range(N):
    d[i][i] = 10**6
 
kyori = 0
ans = 10**6
narabi = list(itertools.permutations(rs,R))
for pt in narabi:
    for i in range(len(pt)-1):
        kyori += d[pt[i]][pt[i+1]]
    if kyori < ans:
        ans = kyori
    kyori = 0

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, m, r = read_line(int, int, int)

rs = [int(r) for r in input().split()]

cities = Counter()

routes = {}
for _ in range(m):
    a, b, c = read_line(int, int, int)

    cities[a] = 1
    cities[b] = 1

    if a in routes:
        routes[a][b] = c
    else:
        routes[a] = { b : c }

    if b in routes:
        routes[b][a] = c
    else:
        routes[b] = { a : c }

def cost(selected):
    c = 0
    for i in range(len(selected) - 1):
        a = selected[i]
        b = selected[i + 1]
        if a in routes and b in routes[a]:
            c += routes[a][b]
        else:
            c += 100000 + 1
    return c

def passing_all_cities(selected):
    for r in rs:
        if r not in selected:
            return False
    return True


smallest = 100000 + 1

def f(selected, rest):
    global smallest
    if passing_all_cities(selected):
        c = cost(selected)
        if smallest > c:
            smallest = c
    else:
        for i in range(len(rest)):
            r = rest[i]
            rest_copy = rest[:]
            del rest_copy[i]
            if cost(selected + [r]) <= smallest:
                f(selected + [r], rest_copy)

f([], list(cities.keys()))
print(smallest)

Submission status: Time Limit Exceeded

Solution code:
#coding=UTF-8

def search(jun):
    global ans
    global R
    global Kost
    tmpans=0
    if len(jun)==R:
        mae=jun[0]
        for idx in range(1,R,1):
            ba=jun[idx]
            tmpans += Kost[r[mae]][r[ba]]
            mae=ba

        if ans==None or tmpans<ans:
            ans=tmpans
    else:
        for me in range(0,R,1):
            if not (me in jun):
                search(jun+[me])

mozir=input()
hyo=mozir.split(' ')
N=int(hyo[0])
M=int(hyo[1])
R=int(hyo[2])

mozir=input()
hyo=mozir.split(' ')
r=[(int(mono)-1) for mono in hyo]

Kost=[]
for idx in range(0,N,1):
    Kost.append([None]*N)

for idx in range(0,N,1):
    Kost[idx][idx]=0

miru=[]
for idx in range(0,M,1):
    mozir=input()
    hyo=mozir.split(' ')
    A=int(hyo[0])-1
    B=int(hyo[1])-1
    C=int(hyo[2])

    Kost[A][B]=C
    Kost[B][A]=C
    miru.append((A,B,C))
    miru.append((B,A,C))

while miru:
    nextmiru=[]
    for idx in range(0,N,1):
        for keiro in miru:
            tui=Kost[keiro[1]][idx]
            if tui==None:
                continue

            tmpKost=keiro[2]+tui
            if Kost[keiro[0]][idx]==None or tmpKost < Kost[keiro[0]][idx]:
                Kost[keiro[0]][idx]=tmpKost
                nextmiru.append((keiro[0],idx,tmpKost))
    miru=nextmiru

#for gyo in Kost:
#    print(gyo)

ans=None
search([])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, m, r = read_line(int, int, int)

rs = [int(r) for r in input().split()]

cities = Counter()

routes = {}
for _ in range(m):
    a, b, c = read_line(int, int, int)

    cities[a] = 1
    cities[b] = 1

    if a in routes:
        routes[a][b] = c
    else:
        routes[a] = { b : c }

    if b in routes:
        routes[b][a] = c
    else:
        routes[b] = { a : c }

def cost(selected):
    c = 0
    for i in range(len(selected) - 1):
        a = selected[i]
        b = selected[i + 1]
        if a in routes and b in routes[a]:
            c += routes[a][b]
        else:
            c += 100000 + 1
    return c

def passing_all_cities(selected):
    for r in rs:
        if r not in selected:
            return False
    return True


smallest = 100000 + 1

def f(selected, rest):
    global smallest
    if passing_all_cities(selected):
        c = cost(selected)
        if smallest > c:
            smallest = c
    else:
        for i in range(len(rest)):
            r = rest[i]
            rest_copy = rest[:]
            del rest_copy[i]
            f(selected + [r], rest_copy)

f([], list(cities.keys()))
print(smallest)

Submission status: Time Limit Exceeded

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

targets=list(map(int, input().split()))

import numpy as np

inf=100001*n
A=(1-np.eye(n))*inf

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

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

from itertools import permutations

print(int(min(sum(A[targetslist[i]-1,targetslist[i+1]-1] for i in range(len(targetslist)-1)) for targetslist in permutations(targets))))

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

N, M, R = map(int, raw_input().split())
g = [[0 for x in xrange(N)] for x in xrange(N)]
r = map(int, raw_input().split())
r = [x-1 for x in r]
for m in xrange(0, M):
    A, B, C = map(int, raw_input().split())
    A -= 1
    B -= 1
    g[B][A] = C
    g[A][B] = C
# print g

for k in xrange(N):
    for i in xrange(N):
        for j in xrange(N):
            g[j][i] = g[i][j] = min(g[j][i], g[i][k]+g[k][j])
# print g

min_d = 10000000000
n = len(r)
for rr in permutations(r):
    # print rr
    d = 0
    for i in xrange(n-1):
        d += g[rr[i]][rr[i+1]]
    min_d = min(d, min_d)
print min_d

Submission status: Time Limit Exceeded

Solution code:
#coding=UTF-8

def search(jun):
    global ans
    global R
    global Kost
    tmpans=0
    if len(jun)==R:
        mae=jun[0]
        for idx in range(1,R,1):
            ba=jun[idx]
            tmpans += Kost[r[mae]][r[ba]]
            mae=ba

        if ans==None or tmpans<ans:
            ans=tmpans
    else:
        for me in range(0,R,1):
            if not (me in jun):
                search(jun+[me])

mozir=input()
hyo=mozir.split(' ')
N=int(hyo[0])
M=int(hyo[1])
R=int(hyo[2])

mozir=input()
hyo=mozir.split(' ')
r=[(int(mono)-1) for mono in hyo]

Kost=[]
for idx in range(0,N,1):
    Kost.append([None]*N)

for idx in range(0,N,1):
    Kost[idx][idx]=0


for idx in range(0,M,1):
    mozir=input()
    hyo=mozir.split(' ')
    A=int(hyo[0])-1
    B=int(hyo[1])-1
    C=int(hyo[2])

    Kost[A][B]=C
    Kost[B][A]=C

changed=True
while changed:
    changed=False
    for idx in range(0,N,1):
        for idt in range(0,N,1):
            if bool(Kost[idx][idt]) == False:
                continue
            else:
                zen=Kost[idx][idt]
                for idy in range(0,N,1):
                    ato=Kost[idt][idy]
                    if ato == None:
                        continue
                    
                    tmpKost=zen+ato
                    if Kost[idx][idy]==None or Kost[idx][idy]>tmpKost:
                        Kost[idx][idy]=tmpKost
                        changed=True

#for gyo in Kost:
#    print(gyo)

ans=None
search([])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

class Graph:
  def __init__(self):
    self.nodes = set()
    self.edges = {}
    self.distances = {}

  def add_node(self, value):
    self.nodes.add(value)
    self.edges[value] = list()

  def add_edge(self, from_node, to_node, distance):
    self.edges[from_node].append(to_node)
    self.edges[to_node].append(from_node)
    self.distances[(from_node, to_node)] = distance
    self.distances[(to_node, from_node)] = distance


def dijkstra(graph, initial):
  visited = {initial: 0}
  path = {}

  nodes = set(graph.nodes)

  while nodes: 
    min_node = None
    for node in nodes:
      if node in visited:
        if min_node is None:
          min_node = node
        elif visited[node] < visited[min_node]:
          min_node = node

    if min_node is None:
      break

    nodes.remove(min_node)
    current_weight = visited[min_node]

    for edge in graph.edges[min_node]:
      weight = current_weight + graph.distances[(min_node, edge)]
      if edge not in visited or weight < visited[edge]:
        visited[edge] = weight
        path[edge] = min_node

  return visited, path

(n,m,r) = map(int,raw_input().split(' '))
routes = map(int,raw_input().split(' '))
min_l = 800000*200
l=0
g = Graph()
for i in range(n):
  g.add_node(i+1)
for i in range(m):
  (a,b,c) = map(int,raw_input().split(' '))
  g.add_edge(a,b,c)
for rs in permutations(routes):
  l=0
  for i in range(r-1):
    (w,e) = dijkstra(g,rs[i])
    l += w[rs[i+1]]
  if min_l > l:
    min_l = l
print min_l

Submission status: Time Limit Exceeded

Solution code:
import copy
tmp=input().split()
N=int(tmp[0])
M=int(tmp[1])
R=int(tmp[2])

r=[int(i) for i in input().split()]
ABC=[[int(j) for j in input().split()] for i in range(M)]
INF=999999999
root=[[INF for j in range(N+1)] for i in range(N+1)]
for i in range(M):
	root[ABC[i][0]][ABC[i][1]] = ABC[i][2]
	root[ABC[i][1]][ABC[i][0]] = ABC[i][2]
	
#構成
#[次の場所、距離]

#最短距離

#初期位置
ans=INF
def roop(here,left,length):
	#print(here)
	if len(left)==0:
		global ans		
		ans=min(ans,length)
		#print(str(here)+" "+str(ans))
	else:
		for next_ in left:
			tmpLeft=copy.deepcopy(left)
			tmpLeft.remove(next_)
			roop(next_,tmpLeft,length+minRootAll[here][next_])

			
	
def checkMinRoot(here):
	d=[INF for i in range(N+1)]
	color=[0 for i in range(N+1)]
	d[here]=0
	color[here]=1
	
	
	while True:
		minv=INF
		u=-1
		for i in range(1,N+1):
			if minv>d[i] and color[i]!=2:
				u=i
				minv=d[i]
		if u==-1:
			break
		color[u]=2
		for v in range(1,N+1):
			if(color[v]!=2 and root[u][v]!=INF):
				if d[v]>d[u]+root[u][v]:
					d[v]=d[u]+root[u][v]
					color[v]=1
	return d
	

#下準備		
minRootAll=[]
for i in range(N+1):
	minRootAll.append(checkMinRoot(i))
#print(minRootAll)
#計算
for i in r:
	tmpr=copy.deepcopy(r)
	#print("why!?")
	tmpr.remove(i)
	roop(i,tmpr,0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
from itertools import permutations
import heapq

INF = float('inf')
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
memo = [[INF for _ in range(N)] for _ in range(N)]

Adj_list = defaultdict(set)

for i in range(M):
    a, b, c = map(int, sys.stdin.readline().split())
    if memo[a-1][b-1]:
        memo[a-1][b-1] = min(memo[a-1][b-1], c)
        
    Adj_list[a-1].add((b-1, memo[a-1][b-1]))
    Adj_list[b-1].add((a-1, memo[a-1][b-1]))


def dijkstra(x, vertex):
    d = [INF] * x
    d[vertex] = 0
    hq = [(0, vertex)]
    
    while hq:
        u = heapq.heappop(hq)[1]
        for (v, c) in Adj_list[u]:
            if d[v] > d[u] + c:
                d[v] = d[u] + c
                heapq.heappush(hq, (d[u]+c, v))

    return d

ans = INF

table = []
for i in range(N):
    d = dijkstra(N, i)
    table.append(d)

for each in permutations(r):
    t_dis = 0
    for i in range(R-1):
        t_dis += table[each[i]-1][each[i+1]-1]
    ans = min(ans, t_dis)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from itertools import permutations
import heapq

INF = float('inf')
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
memo = [[INF for _ in range(N)] for _ in range(N)]

Adj_list = defaultdict(set)

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


def dijkstra(x, vertex):
    d = [INF] * x
    d[vertex] = 0
    hq = [(0, vertex)]
    
    while hq:
        u = heapq.heappop(hq)[1]
        for (v, c) in Adj_list[u]:
            if d[v] > d[u] + c:
                d[v] = d[u] + c
                heapq.heappush(hq, (d[u]+c, v))

    return d

ans = INF

table = []
for i in range(N):
    d = dijkstra(N, i)
    table.append(d)

for each in permutations(r):
    t_dis = 0
    for i in range(R-1):
        t_dis += table[each[i]-1][each[i+1]-1]
    ans = min(ans, t_dis)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python

import itertools
import sys

def main(argv):
    line = sys.stdin.readline()
    while line:
        N, M, R = map(lambda x: int(x), line.split(" ", 3))
        r  = map(lambda x: int(x) - 1, sys.stdin.readline().split(" "))
        weights = [[0 for i in xrange(N)] for j in xrange(N)]
        for i in xrange(M):
            a, b, c = map(lambda x: int(x), sys.stdin.readline().split(" ", 3))
            weights[a - 1][b - 1] = c
            weights[b - 1][a - 1] = c

        for k in xrange(N):
            for i in xrange(N):
                for j in xrange(N):
                    if weights[i][k] > 0 and weights[k][j] > 0:
                        length = weights[i][k] + weights[k][j]
                        if weights[i][j] == 0 or weights[i][j] > length:
                            weights[i][j] = length

        min_length = -1
        for p in itertools.permutations(r):
            length = 0
            previous = p[0]
            for i in p[1:]:
                length += weights[previous][i]
                previous = i
            if min_length == -1:
                min_length = length
            elif min_length > length:
                min_length = length
        print min_length

        line = sys.stdin.readline()

if __name__ == "__main__":
    main(sys.argv)

Submission status: Time Limit Exceeded

Solution code:

import itertools

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

d = [[10**6] * N for i in range(N)]

for abc in ABCs:
    d[abc[0]-1][abc[1]-1] = abc[2]
    d[abc[1]-1][abc[0]-1] = abc[2]

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])
            
for i in range(N):
    d[i][i] = 10**6

kyori = []
narabi = list(itertools.combinations(rs,2))
for n in narabi:
    kyori.append(d[n[0]][n[1]])

if len(kyori) >= 2:
    z = max(kyori)
    print(sum(kyori) - z)
else:
    print(sum(kyori))

Submission status: Time Limit Exceeded

Solution code:
n,m,R=[int(x) for x in input().split()]
r=[int(x) -1 for x in input().split()]
d=[[float("inf") for _ in [0]*n] for _ in [0]*n]
for i in range(n):
    d[i][i]=0
path=[]
for i in [0]*m:
    a,b,c=[int(x) for x in input().split()]
    d[a-1][b-1]=d[b-1][a-1]=c
    path.append(a-1)
    path.append(b-1)
path=set(path)
from itertools import permutations
def Long(args):
    ans=0
    c=0
    tmp=[]
    for i in args:
        tmp.append(i)
        if i in r:
            c+=1
        if c==len(r):
            break
    args=tmp
    for i in range(len(args)-1):
        if ans==float("inf"):
            return ans
        ans+=d[args[i+1]][args[i]]
    return ans
print(min(Long(i) for i in permutations(path)))

Submission status: Time Limit Exceeded

Solution code:
n,m,R=[int(x) for x in input().split()]
r=[int(x) -1 for x in input().split()]
d=[[float("inf") for _ in [0]*n] for _ in [0]*n]
for i in range(n):
    d[i][i]=0
for i in [0]*m:
    a,b,c=[int(x) for x in input().split()]
    d[a-1][b-1]=d[b-1][a-1]=c
from itertools import permutations
def Long(args):
    ans=0
    c=0
    tmp=[]
    for i in args:
        tmp.append(i)
        if i in r:
            c+=1
        if c==len(r):
            break
    args=tmp
    for i in range(len(args)-1):
        if ans==float("inf"):
            return ans
        ans+=d[args[i+1]][args[i]]
    return ans
print(min(Long(i) for i in permutations(range(n))))

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
N, M, R = map(int, input().split())
r = [int(i) - 1 for i in input().split()]
d = [[10000000 for i in range(N)] for j in range(N)]
for i in range(M):
    A, B, C = map(int, input().split())
    d[A-1][B-1] = min(d[A-1][B-1], C)
    d[B-1][A-1] = min(d[A-1][B-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 = True
for o in permutations(r):
    tmp_l = 0
    for s, e in zip(o[:-1], o[1:]):
        tmp_l = tmp_l + d[s][e]
    if l is True:
        l = tmp_l
    else:
        l = min(l, tmp_l)
print(l)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
N, M, R = [int(i) for i in input().split()]
r = [int(i) - 1 for i in input().split()]
V = N
# Define infinity as the large enough value. This value will be
# used for vertices not connected to each other
INF  = 10000000
 
graph = [[INF for i in range(N)] for j in range(N)]

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

# Solves all pair shortest path via Floyd Warshall Algrorithm
def floydWarshall(graph):
    dist = graph
    for k in range(V):
 
        # pick all vertices as source one by one
        for i in range(V):
 
            # Pick all vertices as destination for the
            # above picked source
            for j in range(V):
 
                # If vertex k is on the shortest path from 
                # i to j, then update the value of dist[i][j]
                dist[i][j] = min(dist[i][j] ,
                                  dist[i][k]+ dist[k][j]
                                )
    return(dist)

new_graph = floydWarshall(graph)
smallest_dist = INF
for sub_permute in permutations(r):
    tmp = 0
    for i in range(R-1):
        tmp += new_graph[sub_permute[i]][sub_permute[i+1]]
    smallest_dist = min(smallest_dist, tmp)
print(smallest_dist)

Submission status: Time Limit Exceeded

Solution code:
import copy
tmp=input().split()
N=int(tmp[0])
M=int(tmp[1])
R=int(tmp[2])

r=[int(i) for i in input().split()]
ABC=[[int(j) for j in input().split()] for i in range(M)]

root=[[] for i in range(N+1)]
for i in range(M):
	root[ABC[i][0]].append([ABC[i][1],ABC[i][2]])
	root[ABC[i][1]].append([ABC[i][0],ABC[i][2]])
	
#構成
#[次の場所、距離]

#最短距離

#初期位置
ans=999999
def roop(here,left,length):
	#print(here)
	if len(left)==0:
		global ans		
		ans=min(ans,length)
		#print(str(here)+" "+str(ans))
	else:
		for next_ in left:
			tmpLeft=copy.deepcopy(left)
			tmpLeft.remove(next_)
			roop(next_,tmpLeft,length+checkMinRoot(here,next_))

def checkMinRoot(here,next_):
	minRoot=[999999 for i in range(N+1)]
	minRoot[here]=0
	next=[here]
	while len(next)!=0:
		#ある地点からスタート
		now=next[-1]
		next.pop(-1)
		
		#ある地点までが現状最短経路なら、nextに加える
		for will in root[now]:
			if minRoot[will[0]] > minRoot[now]+will[1]:
				minRoot[will[0]] = minRoot[now]+will[1]
				next.append(will[0])
	return minRoot[next_]

#print(len(r))
for i in r:
	tmpr=copy.deepcopy(r)
	#print("why!?")
	tmpr.remove(i)
	roop(i,tmpr,0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
from itertools import *
N,M,R = map(int,input().split())
rlist = list(map(int,input().split()))
D = []
V = []
for i in range(N):
  D.append([-1]*N)
  V.append([0]*N)
for i in range(N):
  D[i][i] = 0
H = []
heapify(H)
for _ in range(M):
  a,b,c = map(int,input().split())
  D[a-1][b-1] = c
  D[b-1][a-1] = c
  heappush(H,(a-1,b-1))
while H:
  a,b = heappop(H)
  if V[a][b] == 1:
    continue
  V[a][b] = 1
  for i in range(N):
    if D[i][a] != -1:
      d = D[i][a]+D[a][b]
      if D[i][b] == -1 or D[i][b] > d:
        D[i][b] = d
        D[b][i] = d
        heappush(H,(i,b))
    if D[b][i] != -1:
      d = D[a][b]+D[b][i]
      if D[a][i] == -1 or D[a][i] > d:
        D[i][a] = d
        D[a][i] = d
        heappush(H,(i,a))
ret = N*100000
for l in permutations(rlist):
  d = 0
  for i in range(R-1):
    a = l[i]-1
    b = l[i+1]-1
    di = D[a][b]
    if di == -1:
      d = -1
      break
    d += di
  if d >= 0 and ret >= d:
    ret = d
print(ret)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
n,m,r = map(int, input().split())

cities = list(map(int, input().split()))
g = [[10**12 for i in range(n+1)] for j in range(n+1)]
for i in range(n+1):
    g[i][i] = 0
for i in range(m):
    a,b,c = map(int, input().split())
    g[a][b] = c
    g[b][a] = c
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            if i == j or j == k or i == k:
                continue
            g[i][k] = min(g[i][k], g[i][j] + g[j][k])
ans = 10**12
for p in permutations(cities):
    path = 0
    for i in range(1, len(p)):
        path += g[p[i-1]][p[i]]
    ans = min(ans, path)
print(ans)