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: Wrong Answer

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

n, m, r = [ int(v) for v in input().split() ]
town_list = sorted([ int(v)-1 for v in input().split() ])

road_matrix = [ [ 10**9 for j in range(n) ] for i in range(n) ]


for i in range(m):
	s, e, d = [ int(v) - 1 for v in input().split() ]
	road_matrix[s][e] = d + 1
	road_matrix[e][s] = d + 1



min_dist_matrix = []
for h in town_list:
	min_dist = road_matrix[h]
	searched_point = []
	sarching_point = []
	j = h
	while len(searched_point) < n:
		heapq.heappush(searched_point,j)
		for i in range(n):
			#if j < h and i < h:


			if road_matrix[j][i] != 10**9 and i != h:
				heapq.heappush(sarching_point,(road_matrix[j][i],i))

				min_dist[i] = min(min_dist[i],min_dist[j] + road_matrix[j][i])

		for k in range(len(sarching_point)):
			s = heapq.heappop(sarching_point)
			if s[1] not in searched_point:
				j = s[1]
				break

	min_dist_matrix.append(min_dist)


mindist = 10**9
for i in itertools.permutations(town_list,r):
	dist = 0

	for j in range(r-1):
		dist += min_dist_matrix[town_list.index(i[j])][i[j+1]]

	mindist = min(mindist,dist)
print(mindist)

Submission status: Wrong Answer

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

n, m, r = [ int(v) for v in input().split() ]
town_list = [ int(v)-1 for v in input().split() ]

road_matrix = [ [ 10**9 for j in range(n) ] for i in range(n) ]


for i in range(m):
	s, e, d = [ int(v) - 1 for v in input().split() ]
	road_matrix[s][e] = d + 1
	road_matrix[e][s] = d + 1



min_dist_matrix = []
for h in town_list:
	min_dist = road_matrix[h]
	searched_point = []
	sarching_point = []
	j = h
	while len(searched_point) < n:
		heapq.heappush(searched_point,j)
		for i in range(n):
			#if j < h and i < h:


			if road_matrix[j][i] != 10**9 and i != h:
				heapq.heappush(sarching_point,(road_matrix[j][i],i))

				min_dist[i] = min(min_dist[i],min_dist[j] + road_matrix[j][i])

		for k in range(len(sarching_point)):
			s = heapq.heappop(sarching_point)
			if s[1] not in searched_point:
				j = s[1]
				break

	min_dist_matrix.append(min_dist)


mindist = 10**9
for i in itertools.permutations(town_list,r):
	dist = 0

	for j in range(r-1):
		dist += min_dist_matrix[town_list.index(i[j])][i[j+1]]

	mindist = min(mindist,dist)
print(mindist)

Submission status: Wrong Answer

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

n, m, r = [ int(v) for v in input().split() ]
town_list = [ int(v)-1 for v in input().split() ]

road_matrix = [ [ 10**9 for j in range(n) ] for i in range(n) ]


for i in range(m):
	s, e, d = [ int(v) - 1 for v in input().split() ]
	road_matrix[s][e] = d + 1
	road_matrix[e][s] = d + 1


min_dist_matrix = []
for h in range(n):
	min_dist = [ min_dist_matrix[i][h] for i in range(h)] + road_matrix[h][h:]
	searched_point = [ i for i in range(h) ]
	sarching_point = []
	j = h
	while len(searched_point) < n:
		searched_point.append(j)
		for i in range(n):
			if road_matrix[j][i] != 10**9 and i != h:
				heapq.heappush(sarching_point,(road_matrix[j][i],i))
				min_dist[i] = min(min_dist[i],min_dist[j] + road_matrix[j][i])
		sarching_point.sort()

		for k in range(len(sarching_point)):
			s = heapq.heappop(sarching_point)
			if s[1] not in searched_point:
				j = s[1]
				break

	min_dist_matrix.append(min_dist)


mindist = 10**9
for i in itertools.permutations(town_list,r):
	dist = 0
	for j in range(r-1):
		dist += min_dist_matrix[i[j]][i[j+1]]

	mindist = min(mindist,dist)
print(mindist)

Submission status: Wrong Answer

Solution code:

import itertools

n, m, r = [ int(v) for v in input().split() ]
town_list = [ int(v)-1 for v in input().split() ]

road_matrix = [ [ 10**9 for j in range(n) ] for i in range(n) ]


for i in range(m):
	s, e, d = [ int(v) - 1 for v in input().split() ]
	road_matrix[s][e] = d + 1
	road_matrix[e][s] = d + 1

mindist = 10**9
for i in itertools.permutations(town_list,r):
	dist = 0
	for j in range(r-1):
		dist += road_matrix[i[j]][i[j+1]]

	mindist = min(mindist,dist)
print(mindist)

Submission status: Wrong Answer

Solution code:
n,m,r = map(int,input().split())
R = tuple(map(int,input().split()))
ABC = [list(map(int,input().split())) for _ in range(m)]
inf = 1000000000

edge = [[inf]*(n+1) for _ in range(n+1)]

for a,b,c in ABC:
    edge[a][b] = c
    edge[b][a] = c
    
def dijkstra(start,e,N):
    for v in range(1,N+1):#中間
        for g in range(1,N+1):#ゴール
            e[start][g] = min(e[start][g],e[start][v] + e[v][g])
            e[g][start] = e[start][g]
    return e[start]

dic = {}
for rr in R:
    dic[rr] = dijkstra(rr,edge,n)

from itertools import permutations as pm

temp = list(pm(R))

ans = 10000000000
for RR in temp:
    cost = 0
    for i in range(r-1):
        cost += dic[RR[i]][RR[i+1]]
    if cost < ans:
        ans = cost
print(ans)

Submission status: Wrong Answer

Solution code:
n,m,r = map(int,input().split())
R = tuple(map(int,input().split()))
ABC = [list(map(int,input().split())) for _ in range(m)]
inf = 1000000000

edge = [[inf]*(n+1) for _ in range(n+1)]

for a,b,c in ABC:
    edge[a][b] = c
    edge[b][a] = c
    
def dijkstra(start,e,N):
    for v in range(1,N+1):#中間
        for g in range(1,N+1):#ゴール
            e[start][g] = min(e[start][g],e[start][v] + e[v][g])
            e[g][start] = e[start][g]
    return e[start]

dic = {}
for rr in R:
    dic[rr] = dijkstra(rr,edge,n)

from itertools import permutations as pm

temp = list(pm(R))

ans = 10000000000
for RR in temp:
    cost = 0
    for i in range(r-1):
        cost += dic[RR[i]][RR[i+1]]
    if cost < ans:
        ans = cost

print(ans)

Submission status: Wrong Answer

Solution code:
n,m,r = map(int,input().split())
R = list(map(int,input().split()))
ABC = [list(map(int,input().split())) for _ in range(m)]
inf = 1000000000

edge = [[inf]*(n+1) for _ in range(n+1)]

for a,b,c in ABC:
    edge[a][b] = c
    edge[b][a] = c
    
def dijkstra(start,e,N):

    for v in range(1,N+1):#中間
        for g in range(1,N+1):#ゴール
            e[start][g] = min(e[start][g],e[start][v] + e[v][g])
            e[g][start] = e[start][g]
    return e[start]

cost = 0
for j  in range(r-1):
    temp = dijkstra(R[j],edge,n)
    cost += temp[R[j+1]]
print(cost)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from itertools import permutations

def warshall_floyd(conn):
    n = len(conn)
    #dp = [[float('inf') for _ in range(n)] for _ in range(n)]
    dp = [[] for _ in range(n)]
    for i, C in enumerate(conn):
        for j, c in enumerate(C):
            dp[i].append(c)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    return dp


def solve(N: int, M: int, R: int, r: "List[int]", A: "List[int]", B: "List[int]", C: "List[int]"):
    conn = [[float('inf') for _ in range(N)] for _ in range(N)]
    for i in range(N):
        conn[i][i] = 0
    for j in range(M):
        a = A[j] - 1
        b = B[j] - 1
        conn[a][b] = C[j]
        conn[b][a] = C[j]
    dp = warshall_floyd(conn)
    #print(dp)
    ret = float('inf')
    perms = list(permutations(list(range(R))))
    for perm in perms:
        tmp = 0
        for i in range(R - 1):
            s = perm[i] - 1
            t = perm[i + 1] - 1
            #print(r[s], r[t], dp[s][t])
            tmp += dp[s][t]
        ret = min(ret, tmp)
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    R = int(next(tokens))  # type: int
    r = [ int(next(tokens)) for _ in range(R) ]  # type: "List[int]"
    A = [int()] * (M)  # type: "List[int]" 
    B = [int()] * (M)  # type: "List[int]" 
    C = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    solve(N, M, R, r, A, B, C)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from itertools import permutations
 
def warshall_floyd(conn):
    n = len(conn)
    #dp = [[float('inf') for _ in range(n)] for _ in range(n)]
    dp = [[] for _ in range(n)]
    for i, C in enumerate(conn):
        for j, c in enumerate(C):
            dp[i].append(c)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    return dp
 
 
def solve(N: int, M: int, R: int, r: "List[int]", A: "List[int]", B: "List[int]", C: "List[int]"):
    conn = [[float('inf') for _ in range(N)] for _ in range(N)]
    for j in range(M):
        a = A[j] - 1
        b = B[j] - 1
        conn[a][b] = C[j]
        conn[b][a] = C[j]
    dp = warshall_floyd(conn)
    #print(dp)
    ret = float('inf')
    perms = list(permutations(list(range(R))))
    for perm in perms:
        tmp = 0
        for i in range(R - 1):
            s = perm[i] - 1
            t = perm[i + 1] - 1
            #print(r[s], r[t], dp[s][t])
            tmp += dp[s][t]
        ret = min(ret, tmp)
    print(ret)
    return
 
 
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    R = int(next(tokens))  # type: int
    r = [ int(next(tokens)) for _ in range(R) ]  # type: "List[int]"
    A = [int()] * (M)  # type: "List[int]" 
    B = [int()] * (M)  # type: "List[int]" 
    C = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    solve(N, M, R, r, A, B, C)
 
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
r = list(map(lambda v: v-1, r))
grp = []
for i in range(0, N):
	lst = []
	for j in range(0, N):
		lst.append(-1)
	grp.append(lst)
for i in range(0, M):
	A, B, C = map(int, input().split())
	grp[A-1][B-1] = C
	grp[B-1][A-1] = C
movecost = []
for i in range(0, R):
	lst = []
	for j in range(0, R):
		lst.append(-1)
	movecost.append(lst)
for i in range(0, R):
	for j in range(i+1, R):
		start = r[i]
		goal = r[j]
		memo = []
		for k in range(0, N):
			memo.append(True)
		min = 5000000000000000
		queue = [[start, 0, memo]]
		while queue != []:
			now = queue.pop(0)
			if now[0] == goal:
				if now[1] < min: min = now[1]
				break
			newmemo = []
			for k in range(0, N):
				if now[0] == k: newmemo.append(False)
				else: newmemo.append(now[2][k])
			for k in range(0, N):
				if grp[now[0]][k] != -1:
					if now[1] + grp[now[0]][k] < min:
						queue.append([k, now[1]+grp[now[0]][k], newmemo])
		movecost[i][j] = min
		movecost[j][i] = min
stack = []
min = 5000000000000000
for i in range(0, R):
	memo = []
	for j in range(0, R):
		memo.append(i!=j)
	stack.append([i, 0, memo])
while stack != []:
	now = stack.pop(-1)
	if True not in now[2]:
		if now[1] < min: min = now[1]
	else:
		for i in range(0, R):
			if now[2][i]:
				if now[1] + movecost[now[0]][i] < min:
					newmemo = []
					for j in range(0, R):
						if i == j: newmemo.append(False)
						else: newmemo.append(now[2][j])
					stack.append([i, now[1]+movecost[now[0]][i], newmemo])
print(min)

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [input() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    from itertools import permutations
    N, M, R = MI()
    r = LI_()
    d=[[float("inf")] * N for i in range(N)]
    for i in range(N):
        d[i][i]=0
    for _ in range(M):
        a, b, c = MI_()
        c += 1
        d[a][b] = c
        d[b][a] = c
    def warshall_floyd(d, N):
        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])


    warshall_floyd(d, N)

    ans=inf
    for p in permutations(r):
        prev = p[0]
        cost = 0
        for to in p[1:]:
            cost += d[prev][to]
        ans=min(cost,ans)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [input() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    from heapq import heappop,heappush
    N, M, R = MI()
    r = LI_()
    edge = [[]for _ in range(N)]
    for _ in range(M):
        a, b, c = MI_()
        c += 1
        edge[a].append((c,b))
        edge[b].append((c,a))
    pri_queue = [(0, 0)]
    decided = set()
    distanse = [inf]*N
    while pri_queue:
        path_length, from_ = heappop(pri_queue)
        if from_ in decided:
            continue
        decided.add(from_)
        distanse[from_] = path_length
        for weight,to in edge[from_]:
            if to in decided:
                continue
            heappush(pri_queue, (path_length + weight, to))
    ans=0
    for go in r:
        ans=max(distanse[go],ans)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [input() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    from heapq import heappop,heappush
    N, M, R = MI()
    r = LI()
    edge = [[]for _ in range(N)]
    for _ in range(M):
        a, b, c = MI_()
        c += 1
        edge[a].append((c,b))
        edge[b].append((c,a))
    pri_queue = [(0, 0)]
    decided = set()
    distanse = [inf]*N
    while pri_queue:
        path_length, from_ = heappop(pri_queue)
        if from_ in decided:
            continue
        decided.add(from_)
        distanse[from_] = path_length
        for  weight,to in edge[from_]:
            if to in decided:
                continue
            heappush(pri_queue, (path_length + weight, to))
    print(max(distanse))
            
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#from numpy import*
#from scipy import*
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby
from operator import mul
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial
from copy import deepcopy
import sys
from scipy.sparse.csgraph import floyd_warshall

#input=sys.stdin.readline  #危険！基本オフにしろ！
sys.setrecursionlimit(10**6)


def main():
    n,m,r=map(int,input().split())
    grid=[[0]*n for i in range(n)]
    *R,=map(int,input().split())
    for i in range(m):
        a,b,c=map(int,input().split())
        grid[a-1][b-1]=c
        grid[b-1][a-1]=c
    d,p=floyd_warshall(csgraph=grid, directed=False, return_predecessors=True)
#    print(p)
    
    print(min(sum(grid[i[j]-1][i[j+1]-1]for j in range(len(i)-1))for i in permutations(R)))
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,M,R=map(int, input().split())
r=list(map(int, input().split()))
ABC=[list(map(int,input().split())) for i in range(M)]
c=[[10**9]*N for i in range(N)]
for i,j,w in ABC:
    c[i-1][j-1]=w
    c[j-1][i-1]=w
mat=[]
for start in r:
    start-=1
    d=[10**9]*N
    d[start]=0
    prev=[-1]*N
    from heapq import heappop,heappush
    q=[]
    heappush(q,(0,start))
    while len(q)>0:
        u=heappop(q)[1]
        for v in range(N):
            if c[u][v]<10**9:
                temp=d[u]+c[u][v]
                if d[v]>temp:
                    d[v]=temp
                    prev[v]=u
                    heappush(q,(d[v],v))
    m=[]
    for i in range(R):
        m.append(d[r[i]-1])
    mat.append(m)
from itertools import permutations
ans=10**9
for i in permutations(range(R),R):
    a=0
    for j in range(R-1):
        a+=mat[i[j]][i[j+1]]
    ans=min(ans,a)
print(a)

Submission status: Wrong Answer

Solution code:
import sys
import itertools

N,M,R=map(int, raw_input().split())

d=[  [ float("inf") for j in range(N+1) ]  for i in range(N+1) ]

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

for _ in range(M):
	a,b,c=map(int, sys.stdin.readline().split())
	if d[a][b]>c:
		d[a][b]=c
		d[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 d[i][j]>d[i][k]+d[k][j]:
				d[i][j]=d[i][k]+d[k][j]


C=list(itertools.permutations(r))


ans=float("inf")
for x in C:
	tmp_ans=0
	for i in range(R-1):
		fro=x[i]
		to=x[i+1]
		tmp_ans+=d[fro][to]
	ans=min(ans, tmp_ans)

print ans

Submission status: Wrong Answer

Solution code:
import sys
import itertools

N,M,R=map(int, raw_input().split())

d=[  [ float("inf") for j in range(N+1) ]  for i in range(N+1) ]

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

for _ in range(M):
	a,b,c=map(int, sys.stdin.readline().split())
	if d[a][b]>c:
		d[a][b]=c
		d[b][a]=c

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


C=list(itertools.permutations(r))


ans=float("inf")
for x in C:
	tmp_ans=0
	for i in range(R-1):
		fro=x[i]
		to=x[i+1]
		tmp_ans+=d[fro][to]
	ans=min(ans, tmp_ans)

print ans

Submission status: Wrong Answer

Solution code:
import sys
import itertools

N,M,R=map(int, raw_input().split())

d=[  [ float("inf") for j in range(N+1) ]  for i in range(N+1) ]

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

for _ in range(M):
	a,b,c=map(int, sys.stdin.readline().split())
	d[a][b]=c
	d[b][a]=c


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


C=list(itertools.permutations(r))


ans=float("inf")
for x in C:
	tmp_ans=0
	for i in range(R-1):
		fro=x[i]
		to=x[i+1]
		tmp_ans+=d[fro][to]
	ans=min(ans, tmp_ans)

print ans

Submission status: Wrong Answer

Solution code:
import sys
import itertools

N,M,R=map(int, raw_input().split())

d=[  [ float("inf") for j in range(N+1) ]  for i in range(N+1) ]
for i in range(N+1):
	d[i][i]=0

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

for _ in range(M):
	a,b,c=map(int, sys.stdin.readline().split())
	d[a][b]=c
	d[b][a]=c


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


C=list(itertools.permutations(r))


ans=float("inf")
for x in C:
	tmp_ans=0
	for i in range(R-1):
		fro=x[i]
		to=x[i+1]
		tmp_ans+=d[fro][to]
	ans=min(ans, tmp_ans)

print ans

Submission status: Wrong Answer

Solution code:
import sys
import itertools

N,M,R=map(int, raw_input().split())

d=[  [ float("inf") for j in range(N+1) ]  for i in range(N+1) ]

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

for _ in range(M):
	a,b,c=map(int, sys.stdin.readline().split())
	d[a][b]=c
	d[b][a]=c
	d[a][a]=0
	d[b][b]=0


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


C=list(itertools.permutations(r))


ans=float("inf")
for x in C:
	tmp_ans=0
	for i in range(R-1):
		fro=x[i]
		to=x[i+1]
		tmp_ans+=d[fro][ to ]
	ans=min(ans, tmp_ans)

print ans

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
N, M, R = map(int, input().split())
rs = list(map(int, input().split()))
G=[[]for i in range(N+1)] #各点が繋がってる点とその距離を記録
for i in range(M):
    a, b, c = map(int,input().split())
    G[a] += (b,c),
    G[b] += (a,c),
d = [10**9]*R #各スタート地点からの最短経路の距離のリスト
def f(v,l,u,n,s):#v:今見ているとこ lこれまで訪れたリスト　uこれまでの距離 nこれまで訪れた点の種類 sスタート地点
    if u >= d[s]:
        return 'hoge'
    if n == R: 
        if d[s] > u:
            d[s] = u
    for r, c in G[v]:
        if r not in l: 
            if r in rs:
                f(r, l+[r], u+c, n+1, s)
            else:
                f(r, l+[r], u+c, n, s)
for i in range(R): 
    f(rs[i], [rs[i]], 0, 1, i)
print(min(d))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
N, M, R = map(int, input().split())
rs = list(map(int, input().split()))
G=[[]for i in range(N+1)] #各点が繋がってる点とその距離を記録
for i in range(M):
    a, b, c = map(int,input().split())
    G[a] += (b,c),
    G[b] += (a,c),
d = [10**6]*R #各スタート地点からの最短経路の距離のリスト
def f(v,l,u,n,s): #v:今見ているとこ lこれまで訪れたリスト　uこれまでの距離 nこれまで訪れた点の種類 sスタート地点
    if n == R: 
        if d[s] > u:
            d[s] = u
    for r, c in G[v]:
        if r not in l: 
            if r in rs:
                f(r, l+[r], u+c, n+1, s)
            else:
                f(r, l+[r], u+c, n, s)
for i in range(R): 
    f(rs[i], [rs[i]], 0, 1, i)
print(min(d))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
N, M, R = map(int, input().split())
rs = list(map(int, input().split()))
G=[[]for i in range(N+1)] #各点が繋がってる点とその距離を記録
for i in range(M):
    a, b, c = map(int,input().split())
    G[a] += (b,c),
    G[b] += (a,c),
d = [10**6]*R #各スタート地点からの最短経路の距離のリスト
def f(v,l,u,n,s): #v:今見ているとこ lこれまで訪れたリスト　uこれまでの距離 nこれまで訪れた点の種類 sスタート地点
    if n == R: 
        if d[s] > u:
            d[s] = u
    for r, c in G[v]:
        if r not in l and r in rs: #これまで訪れてなくて訪れるべきところなら訪れる
            f(r, l+[r], u+c, n+1, s)
for i in range(R): 
    f(rs[i], [rs[i]], 0, 1, i)
print(min(d))

Submission status: Wrong Answer

Solution code:
n,m,r = map(int,input().split())
r = list(map(int,input().split()))
node = [list(map(int,input().split())) for _ in range(m)]
dic = {}
for i in range(1,n+1):
    dic[i] = {}
    for j in range(1,n+1):
        dic[i][j]=10**6
for a,b,c in node:
    dic[a][b] = c
    dic[b][a] = c
dp = [[float('inf')]*(n+1) for _ in range(n+1)]
for i in range(n+1):
    dp[0][i] = 0
for i in range(1,n+1):
    for j in range(1,n+1):
        if i==j:
            dp[i][j] = 0
            continue
        dp[i][j] = dic[i][j]
        for k in range(1,n+1):
            if i==k or k==j:
                continue
            dp[i][j] = min(dp[i][j], dic[i][k]+dic[k][j])
import copy
import sys
rest = set(r[:])
def dfs(cost,pre,rest):
    if 0==len(rest):
        return cost
    ret = sys.maxsize
    for i in rest:
        if pre==None:
            next_cost = 0
        else:
            next_cost = cost + dp[pre][i]
        next_rest = copy.copy(rest)
        next_rest.remove(i)
        tmp_ret = dfs(next_cost, i, next_rest)
        ret = min(ret,tmp_ret)
    return ret
print(dfs(0,None,rest))

Submission status: Wrong Answer

Solution code:
n,m,r = map(int,input().split())
r = list(map(int,input().split()))
node = [list(map(int,input().split())) for _ in range(m)]
dic = {}
for i in range(1,n+1):
    dic[i] = {}
    for j in range(1,n+1):
        dic[i][j]=10**6
for a,b,c in node:
    dic[a][b] = c
    dic[b][a] = c
dp = [[float('inf')]*(n+1) for _ in range(n+1)]
for i in range(n+1):
    dp[0][i] = 0
for i in range(1,n+1):
    for j in range(1,n+1):
        if i==j:
            dp[i][j] = 0
            continue
        dp[i][j] = dic[i][j]
        for k in range(1,n+1):
            dp[i][j] = min(dp[i][j], dic[i][k]+dic[k][j])
import copy
def dfs(dv,nv,cost):
    if sum(dv)==len(dv):
        return cost
    ret = []
    for i in range(len(dv)):
        if dv[i]==1:
            continue
        dv_ = copy.copy(dv)
        dv_[i] = 1
        ret.append(dfs(dv_,r[i],cost+dp[nv][r[i]]))
    return min(ret)
print(dfs([0]*len(r),0,0))

Submission status: Wrong Answer

Solution code:
n,m,r = map(int,input().split())
r = list(map(int,input().split()))
node = [list(map(int,input().split())) for _ in range(m)]
dp = [[float('inf')]*(n+1) for _ in range(n+1)]
for x,y,z in node:
    dp[x][y] = z
    dp[y][x] = z
for i in range(n+1):
    dp[i][i] = 0
def wf(d,n):
    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]
    return d
dp = wf(dp,n+1)
import copy
rest = set(r[:])
def dfs(cost,pre,rest):
    if 0==len(rest):
        return cost
    ret = 10*12
    for i in rest:
        if pre==None:
            next_cost = 0
        else:
            next_cost = cost + dp[pre][i]
        next_rest = copy.copy(rest)
        next_rest.remove(i)
        tmp_ret = dfs(next_cost, i, next_rest)
        ret = min(ret,tmp_ret)
    return ret
print(dfs(0,None,rest))

Submission status: Wrong Answer

Solution code:
n,m,r = map(int,input().split())
r = list(map(int,input().split()))
node = [list(map(int,input().split())) for _ in range(m)]
dp = [[10**9]*(n+1) for _ in range(n+1)]
for x,y,z in node:
    dp[x][y] = z
    dp[y][x] = z
for i in range(n+1):
    dp[i][i] = 0
def wf(d,n):
    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]
    return d
dp = wf(dp,n+1)
import copy
rest = set(r[:])
def dfs(cost,pre,rest):
    if 0==len(rest):
        return cost
    ret = 10*12
    for i in rest:
        if pre==None:
            next_cost = 0
        else:
            next_cost = cost + dp[pre][i]
        next_rest = copy.copy(rest)
        next_rest.remove(i)
        tmp_ret = dfs(next_cost, i, next_rest)
        ret = min(ret,tmp_ret)
    return ret
print(dfs(0,None,rest))

Submission status: Wrong Answer

Solution code:
n,m,r = map(int,input().split())
r = list(map(int,input().split()))
node = [list(map(int,input().split())) for _ in range(m)]
dic = {}
for i in range(1,n+1):
    dic[i] = {}
    for j in range(1,n+1):
        dic[i][j]=10**6
for a,b,c in node:
    dic[a][b] = c
    dic[b][a] = c
dp = [[10**8]*(n+1) for _ in range(n+1)]
for i in range(n+1):
    dp[0][i] = 0
for i in range(1,n+1):
    for j in range(1,n+1):
        if i==j:
            dp[i][j] = 0
            continue
        dp[i][j] = dic[i][j]
        for k in range(1,n+1):
            if i==k or k==j:
                continue
            dp[i][j] = min(dp[i][j], dic[i][k]+dic[k][j])
import copy
rest = set(r[:])
def dfs(cost,pre,rest):
    if 0==len(rest):
        return cost
    ret = 10*12
    for i in rest:
        if pre==None:
            next_cost = 0
        else:
            next_cost = cost + dp[pre][i]
        next_rest = copy.copy(rest)
        next_rest.remove(i)
        tmp_ret = dfs(next_cost, i, next_rest)
        ret = min(ret,tmp_ret)
    return ret
print(dfs(0,None,rest))

Submission status: Wrong Answer

Solution code:
n,m,r = map(int,input().split())
r = list(map(int,input().split()))
node = [list(map(int,input().split())) for _ in range(m)]
dic = {}
for i in range(1,n+1):
    dic[i] = {}
    for j in range(1,n+1):
        dic[i][j]=10**6
for a,b,c in node:
    dic[a][b] = c
    dic[b][a] = c
dp = [[10**8]*(n+1) for _ in range(n+1)]
for i in range(n+1):
    dp[0][i] = 0
for i in range(1,n+1):
    for j in range(1,n+1):
        if i==j:
            dp[i][j] = 0
            continue
        dp[i][j] = dic[i][j]
        for k in range(1,n+1):
            if i==k or k==j:
                continue
            dp[i][j] = min(dp[i][j], dic[i][k]+dic[k][j])
import copy
def dfs(dv,nv,cost):
    if sum(dv)==len(dv):
        return cost
    ret = 10*12
    for i in range(len(dv)):
        if dv[i]==1:
            continue
        dv_ = copy.copy(dv)
        dv_[i] = 1
        ret = min(ret,dfs(dv_,r[i],cost+dp[nv][r[i]]))
    return ret
print(dfs([0]*len(r),0,0))