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

inf = 10 ** 9
n, m, r = map(int, input().split())
r_list = [int(i) - 1 for i in input().split()]
a_list = [[inf for _ in range(n)] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    a_list[a][b] = a_list[b][a] = c
for k in range(n):
    for i in range(n):
        for j in range(i + 1, n):
            x = a_list[i][k] + a_list[k][j]
            if x < a_list[i][j]:
                a_list[i][j] = a_list[j][i] = x
k = list(itertools.permutations(r_list))
ans = inf
for kk in k[:len(k)//2]:
    temp = 0
    for k1, k2 in zip(kk[:-1], kk[1:]):
        temp += a_list[k1][k2]
    if ans > temp:
        ans = temp
print(ans)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n,m = LI()
    a = LIR(n)
    ans = 0
    for i in range(2):
        for j in range(2):
            for k in range(2):
                a.sort(key = lambda x:(-1)**i*x[0]+(-1)**j*x[1]+(-1)**k*x[2])
                p = [0,0,0]
                for l in range(m):
                    p[0] += a[l][0]
                    p[1] += a[l][1]
                    p[2] += a[l][2]
                p = abs(p[0])+abs(p[1])+abs(p[2])
                if p > ans:
                    ans = p
    print(ans)
    return

#B
def B():
    def root(x):
        if x == par[x]:
            return x
        par[x] = root(par[x])
        return par[x]

    def unite(x,y,su):
        x = root(x)
        y = root(y)
        su += comb_2(s[x])+comb_2(s[y])
        if rank[x] < rank[y]:
            s[y] += s[x]
            su -= comb_2(s[y])
            par[x] = y
        else:
            s[x] += s[y]
            su -= comb_2(s[x])
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1
        return su

    def comb_2(a):
        return a*(a-1)//2

    n,m = LI()
    v = LIR(m)
    par = [i for i in range(n)]
    rank = [0]*n
    s = [1]*n
    su = comb_2(n)
    ans = [su]
    for a,b in v[:0:-1]:
        a -= 1
        b -= 1
        if root(a) != root(b):
            su = unite(a,b,su)
        ans.append(su)
    for i in ans[::-1]:
        print(i)
    return

#C
def C():
    def root(x):
        if par[x] == x:
            return par[x]
        r = root(par[x])
        d[x] += d[par[x]]
        par[x] = r
        return par[x]

    def weight(x):
        root(x)
        return d[x]

    def unite(x,y,w):
        w += weight(x)
        w -= weight(y)
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
            d[x] = -w
        else:
            par[y] = x
            d[y] = w
            if rank[x] == rank[y]:
                rank[x] += 1
    n,m = LI()
    par = [i for i in range(n)]
    rank = [0]*n
    d = [0]*n
    for i in range(m):
        l,r,w = LI()
        l -= 1
        r -= 1
        if root(l) != root(r):
            unite(l,r,w)
        else:
            if weight(r)-weight(l) != w:
                print("No")
                return
    print("Yes")
    return

#D
def D():
    h,w = LI()
    n = I()
    a = LI()
    ans = [0]*h*w
    p = 0
    for i in range(n):
        for j in range(a[i]):
            ans[p+j] = i+1
        p += a[i]
    for i in range(h):
        s = ans[i*w:(i+1)*w]
        if i%2:
            print(*s[::-1])
        else:
            print(*s)
    return

#E
def E():
    n,k = LI()
    s = [int(x) for x in input()]
    f = [0]*n
    j = 0
    su = 1
    p = s[0]
    for i in range(1,n):
        if s[i] != p:
            f[j] = su
            j += 1
            su = 1
            p = s[i]
        else:
            su += 1
    f[j] = su
    f.append(0)
    if s[0]:
        m = sum(f[:2*k+1])
        ans = m
        for i in range(2*k+1,n):
            m -= f[i-2*k-1]
            if not i%2:
                m += f[i-1]
                m += f[i]
            ans = max(m,ans)
    else:
        m = sum(f[:2*k])
        ans = m
        for i in range(2*k,n):
            m -= f[i-2*k]
            if not i%2:
                m += f[i]
                m += f[i+1]
            ans = max(m,ans)
    print(ans)
    return

#F
def F():
    n = I()
    a = LI()
    s = [0,0,0]
    for i in a:
        if i%4 == 0:
            s[0] += 1
        elif i%2 == 0:
            s[1] += 1
        else:
            s[2] += 1
    a = [0]
    while 1:
        if s[2]:
            if a[-1] == 2:
                print("No")
                return
            s[2] -= 1
            a.append(2)
            if s[0]:
                s[0] -= 1
                a.append(0)
        elif s[1]:
            if a[-1] == 2:
                print("No")
            else:
                print("Yes")
            return
        else:
            print("Yes")
            return
    return

#G
def G():
    n,m,l = LI()
    r = LI()
    for i in range(l):
        r[i] -= 1
    d = [[float("inf")]*n for i in range(n)]
    for i in range(n):
        d[i][i] = 0
    for i in range(m):
        a,b,c = LI()
        a -= 1
        b -= 1
        d[a][b] = c
        d[b][a] = c
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])
    m = 1<<l
    dp = [[float("inf")]*l for i in range(m)]
    for i in range(l):
        dp[1<<i][i] = 0
    for i in range(l):
        x = r[i]
        for b in range(m):
            if not b&(1<<i):
                continue
            for j in range(l):
                if b&(1<<j):
                    continue
                nb = b|(1<<j)
                y = r[j]
                res = dp[b][i]+d[x][y]
                if res < dp[nb][j]:
                    dp[nb][j] = res
    print(min(dp[m-1]))
    return

#H
def H():

    return

#I
def I_():

    return

#Solve
if __name__ == "__main__":
    G()

Submission status: Wrong Answer

Solution code:
from itertools import permutations

n,m,r=map(int,input().split())
*R,=map(int,input().split())
INF=float("inf")
dist=[[INF]*n for _ in range(n)]
for i in range(n):
	dist[i][i]=0
for _ in range(m):
	a,b,c=map(int,input().split())
	dist[a-1][b-1]=c
	dist[b-1][a-1]=c
for k in range(n):
	for i in range(n):
		for j in range(n):
			dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])
v=[]
for i in R:
	t=[]
	for j in R:
		t.append(dist[i-1][j-1])
	v.append(t)
mn=INF
print(v)
for t in permutations(range(r)):
	a=0;f=1
	for i,j in zip(t,t[1:]):
		if v[i][j]==INF:
			f=0
			break
		else:
			a+=v[i][j]
	if f:
		mn=min(mn,a)
print(mn)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math
import itertools

# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    tmp = float('inf')
    a = 1
    aa = []
    
    aa.append(3)
    aa.append(2)
    aa.append(1)
    aa.append(float('inf'))
    
    
    print(aa)
		
            	
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math
import itertools

# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N,M,R = inputMap()
    r = inputList()
    A = [[100000 for _ in range(N)] for _ in range(N)]
    
    for _ in range(M):
        a,b,c = inputList()
        A[a-1][b-1] = c
        A[b-1][a-1] = c
    
    for i in range(N):
        A[i][i] = 0
        
    A = warshall_floyd(A, N)
        
    ans = -1
    visi = list(itertools.permutations(r))
    for sp in visi:
        tmp = 0
        for i, val in enumerate(sp):
            if i == 0:
                continue
            tmp += A[sp[i-1]-1][sp[i]-1]
            
        if ans == -1 or ans > tmp:
            ans = tmp
            
    print(ans)
        
def warshall_floyd(d, n):
	#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
		
            	
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math
import itertools

# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N,M,R = inputMap()
    r = inputList()
    A = [[100000 for _ in range(N)] for _ in range(N)]
    
    for _ in range(M):
        a,b,c = inputList()
        A[a-1][b-1] = c
        A[b-1][a-1] = c
        
    A = warshall_floyd(A, N)
        
    ans = -1
    visi = list(itertools.permutations(r))
    for sp in visi:
        tmp = 0
        for i, val in enumerate(sp):
            if i == 0:
                continue
            tmp += A[sp[i-1]-1][sp[i]-1]
            
        if ans == -1 or ans > tmp:
            ans = tmp
            
    print(ans)
        
def warshall_floyd(d, n):
	#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
		
            	
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math
import itertools

# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N,M,R = inputMap()
    r = inputList()
    A = [[100000 for _ in range(N)] for _ in range(N)]
    
    for _ in range(M):
        a,b,c = inputList()
        A[a-1][b-1] = c
        
    A = warshall_floyd(A, N)
        
    ans = -1
    visi = list(itertools.permutations(r))
    for sp in visi:
        tmp = 0
        for i, val in enumerate(sp):
            if i == 0:
                continue
            tmp += A[sp[i-1]-1][sp[i]-1]
            
        if ans == -1 or ans > tmp:
            ans = tmp
            
    print(ans)
        
def warshall_floyd(d, n):
	#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
		
            	
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
import itertools

Submission status: Wrong Answer

Solution code:
import copy, itertools

n, m, R = map(int, input().split())
r = list(map(int, input().split()))
route = {i + 1 : {} for i in range(n)}
for i in range(m):
    a, b, c = map(int, input().split())
    route[a][b] = c
    route[b][a] = c

def distance(start, route, goal):
    route_copy = copy.deepcopy(route)
    dis = [float("inf")] * n
    dis[start - 1] = 0
    determined = [start]
    while goal not in determined:
        length_list = {}
        for i in determined:
            for j in route_copy[i]:
                length_list[j] = dis[i - 1] + route_copy[i][j]
        length_list = list(length_list.items())
        length_list.sort(key = lambda x: x[1])
        x, y = length_list[0][0], length_list[0][1]
        for i in determined:
            if x in route_copy[i]:
                del route_copy[i][x]
                del route_copy[x][i]
        determined.append(x)
        dis[x - 1] = y
    return dis[goal - 1]

ans = []
for i in itertools.permutations(r):
    temp = 0
    for j in range(R - 1):
        temp += distance(i[j], route, i[j + 1])
    ans.append(temp)
print(min(ans))

Submission status: Wrong Answer

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

N, M, R = map(int, input().split())
L = [int(v) - 1 for v in input().split()]
AA = [[10 ** 18 for _ in range(N)] for _ in range(N)]
MAP = [set() for _ in range(N)]

for _ in range(M):
    a, b, c = map(int, input().split())
    AA[a - 1][b - 1] = c
    AA[b - 1][a - 1] = c
    
    MAP[a - 1].add(b - 1)
    MAP[b - 1].add(a - 1)
    
ans = 10 ** 18
def dfs(now, al, c):
    global ans
    if ans < c:
        return

    t = MAP[now]
    
    f = True
    for v in L:
        if v not in al:
            f = False
            break
    if f:
        ans = min(ans, c)
    
    for p in t:
        if p not in al:
            dfs(p, al + [p], c + AA[now][p])
    
    return

for i in range(N):
    dfs(i, [i], 0)
    
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
ABC = [list(map(int, input().split())) for _ in range(M)]

# 距離表の初期化
INF = 100# ** 12
dist = [[INF] * N for _ in range(N)]
for i in range(N):
	dist[i][i] = 0

# グラフを読み込みつつ距離表の更新
for a, b, c in ABC:
	a, b = a - 1, b - 1
	dist[a][b] = c
	dist[b][a] = c

# ワーシャル–フロイド法の前処理
for k in range(N):
	for i in range(N):
		for j in range(N):
			dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

#print(dist)

# 全探索(*^_^*)つ[rCr]
min_dist = INF
for p in itertools.permutations(r):
	d = 0
	for n in range(1, R):
		d += dist[p[n] - 1][p[n - 1] - 1]
	if d < min_dist:
		min_dist = d
		#print(d, p)
print(min_dist)

Submission status: Wrong Answer

Solution code:
N, M, R = map(int, input().split())
T = list(map(int, input().split()))
D = [[0] * N for _ in range(N)]
for _ in range(M):
    A, B, C = map(int, input().split())
    A -= 1
    B -= 1
    D[A][B] = C
    D[B][A] = C


def dfs(i, d, v):
    v[i] = True
    if all(v[t - 1] for t in T) is True:
        return d
    dd = float('INF')
    for j in range(N):
        if v[j] is True:
            continue
        if D[i][j] == 0:
            continue
        dd = min(dd, dfs(j, d + D[i][j], v[::]))
    return dd


def main():
    ans = float('INF')
    for i in range(N):
        v = [False] * N
        ans = min(ans, dfs(i, 0, v[::]))
    print(ans)


main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import itertools

def main():
    node_num, edge_num, visit_num = map(int, input().split())
    visit_place = list(map(int, input().split()))
    data = [list(map(int, input().split())) for i in range(edge_num)]

    hashi_set = defaultdict(set)
    kyori_data = [defaultdict(int) for i in range(node_num + 1)]

    saitan_data = [[-1 for i in range(node_num + 1)] for j in range(node_num + 1)]

    for i in range(edge_num):
        a, b, c = data[i]
        hashi_set[a].add(b)
        hashi_set[b].add(a)
        kyori_data[a][b] = c
        kyori_data[b][a] = c
        saitan_data[a][b] = c
        saitan_data[b][a] = c


    for k in range(1, node_num + 1):
        for i in range(1, node_num + 1):
            for j in range(1, node_num + 1):
                if i == j:
                    saitan_data[i][j] = 0
                    continue
                saitan_data[i][j] = min(saitan_data[i][j], saitan_data[i][k] + saitan_data[k][j])

    ans = 10 ** 10
    for ikikata in list(itertools.permutations(visit_place, visit_num)):
        kari = 0
        for i in range(visit_num - 1):
            kari += saitan_data[ikikata[i]][ikikata[i + 1]]
        if kari < ans:
            ans = kari
    print(ans)





if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class Tree:
  def __init__(s, N):
    s.T = [-1] * N
  def root(s, x):
    if s.T[x] < 0:
      return x, -s.T[x]
    r, d = s.root(s.T[x])
    s.T[x] = r
    return r, d
  def merge(s, a, b):
    ar, ad = s.root(a)
    br, bd = s.root(b)
    if ar == br:
      return False
    if ad < bd:
      s.T[ar] = -max(ad, bd + 1)
      s.T[br] = ar
    else:
      s.T[br] = -max(bd, ad + 1)
      s.T[ar] = br
    return True


N, M, R = list(map(int, input().split()))
r = list(map(int, input().split()))
ABC = [list(map(int, input().split())) for _ in range(M)]

D = [[-1] * N for i in range(N)]

for a, b, c in ABC:
  a -= 1
  b -= 1
  D[a][b] = c
  D[b][a] = c

for i in range(N):
  for j in range(N):
    if i == j:
      D[i][j] = 0
    elif D[i][j] == -1:
      D[i][j] = 10 ** 10

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])

L = [[0] * R for _ in range(R)]
E = []
for i in range(R - 1):
  for j in range(i + 1, R):
    a = r[i] - 1
    b = r[j] - 1
    L[i][j] = D[a][b]
    L[j][i] = D[a][b]
    E.append([D[a][b], i, j])
E.sort()

T = Tree(R)
ans = 0
for d, i, j in E:
  if T.merge(i, j):
    ans += d

print(ans)

Submission status: Wrong Answer

Solution code:
class Tree:
  def __init__(s, N):
    s.T = [-1] * N
  def root(s, x):
    if s.T[x] < 0:
      return x, -s.T[x]
    r, d = s.root(s.T[x])
    s.T[x] = r
    return r, d
  def merge(s, a, b):
    ar, ad = s.root(a)
    br, bd = s.root(b)
    if ar == br:
      return False
    if ad < bd:
      s.T[ar] = -max(ad, bd + 1)
      s.T[br] = ar
    else:
      s.T[br] = -max(bd, ad + 1)
      s.T[ar] = br
    return True


N, M, R = list(map(int, input().split()))
r = list(map(int, input().split()))
ABC = [list(map(int, input().split())) for _ in range(M)]

D = [[0] * N for i in range(N)]

for a, b, c in ABC:
  a -= 1
  b -= 1
  D[a][b] = c
  D[b][a] = c

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

L = [[0] * R for _ in range(R)]
E = []
for i in range(R - 1):
  for j in range(i + 1, R):
    a = r[i] - 1
    b = r[j] - 1
    L[i][j] = D[a][b]
    L[j][i] = D[a][b]
    E.append([D[a][b], i, j])
E.sort()

T = Tree(R)
ans = 0
for d, i, j in E:
  if T.merge(i, j):
    ans += d

print(ans)

Submission status: Wrong Answer

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

class Route:
    def __init__(self, B, C):
        self.next = points[B]
        self.distance = C
class Point:
    def __init__(self, id):
        self.id = id
        self.neighbors = []
        self.clear()
    def clear(self):
        self.distances = [-1] * 2
    def set(self, cur):
        self.distances[cur.srcid] = cur.distance
        return self.isWent(0) and self.isWent(1)
    def isWent(self, n):
        return self.distances[n] >= 0
    def addNeighbor(self, B, C):
        self.neighbors.append(Route(B, C))
    def optimize(self):
        self.neighbors = sorted(self.neighbors, key=lambda obj:obj.distance)

class MeetInfo:
    def __init__(self):
        self.clear()
    def clear(self):
        self.distance = -1
    def isMet(self):
        return self.distance >= 0

class Cursor:
    def __init__(self, ri, pt, meetinfo, dist=0):
        self.srcid = ri
        self.point = pt
        self.cur_route = 0
        self.distance = dist
        self.meetinfo = meetinfo
        if self.point.set(self):
            meetinfo.distance = self.point.distances[0] + self.point.distances[1]

    def cost(self):
        while self.cur_route < len(self.point.neighbors):
            rt = self.point.neighbors[self.cur_route]
            if not rt.next.isWent(self.srcid):
                break
            self.cur_route+= 1
        else:
            return None

        return self.distance + rt.distance

    def progress(self):
        nextrt = self.point.neighbors[self.cur_route]
        addcursor(Cursor(self.srcid, nextrt.next, self.meetinfo, self.distance + nextrt.distance))
        self.cur_route += 1
        addcursor(self)
    def __lt__(self, other):
        return True
points = [Point(i) for i in range(N+1)]

in_r = [ri for ri in map(int, input().split())]
for A, B, C in (map(int, input().split()) for _ in range(M)):
    points[A].addNeighbor(B, C)
    points[B].addNeighbor(A, C)

for x in points:
    x.optimize()

def addcursor(cur):
    c = cur.cost()
    if not c is None:
        heapq.heappush(hq, (c, cur))

def getRs(rs = None, cnt = -1, ret = None):
    if rs is None:
        rs = [False] * R
        ret = []
        cnt = R

    if cnt <= 0:
        yield ret
        return

    cnt -= 1

    for i in range(R):
        if not rs[i]:
            rs[i] = True
            ret.append(i)
            yield from getRs(rs, cnt, ret)
            ret.pop()
            rs[i] = False

Rmatrix = [[-1 for _ in range(R)] for _ in range(R) ]

for i in range(R):
    for j in range(R):
        if i >= j:
            continue

        meetinfo = MeetInfo()
        for x in points:
            x.clear()
        rs = [Cursor(i, points[ri], meetinfo)  for i, ri in enumerate((in_r[i], in_r[j]))]
        hq = []
        addcursor(rs[0])

        while not meetinfo.isMet():
            cost, cursor = heapq.heappop(hq)
            cursor.progress()

        Rmatrix[i][j] = meetinfo.distance
        Rmatrix[j][i] = meetinfo.distance

M = 10 ** 9
for r in getRs():
    print(r)
    w = 0
    for i in range(R-1):
        w += Rmatrix[r[i]][r[i+1]]    
    M = min(M, w)

print(M)

Submission status: Wrong Answer

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

class Route:
    def __init__(self, B, C):
        self.next = points[B]
        self.distance = C
class Point:
    def __init__(self, id):
        self.id = id
        self.neighbors = []
        self.clear()
    def clear(self):
        self.distances = [-1] * 2
    def set(self, cur):
        self.distances[cur.srcid] = cur.distance
        return self.isWent(0) and self.isWent(1)
    def isWent(self, n):
        return self.distances[n] >= 0
    def addNeighbor(self, B, C):
        self.neighbors.append(Route(B, C))
    def optimize(self):
        self.neighbors = sorted(self.neighbors, key=lambda obj:obj.distance)

class MeetInfo:
    def __init__(self):
        self.clear()
    def clear(self):
        self.distance = -1
    def isMet(self):
        return self.distance >= 0

class Cursor:
    def __init__(self, ri, pt, meetinfo, dist=0):
        self.srcid = ri
        self.point = pt
        self.cur_route = 0
        self.distance = dist
        self.meetinfo = meetinfo
        if self.point.set(self):
            meetinfo.distance = self.point.distances[0] + self.point.distances[1]

    def cost(self):
        while self.cur_route < len(self.point.neighbors):
            rt = self.point.neighbors[self.cur_route]
            if not rt.next.isWent(self.srcid):
                break
            self.cur_route+= 1
        else:
            return None

        return self.distance + rt.distance

    def progress(self):
        nextrt = self.point.neighbors[self.cur_route]
        addcursor(Cursor(self.srcid, nextrt.next, self.meetinfo, self.distance + nextrt.distance))
        self.cur_route += 1
        addcursor(self)
    def __lt__(self, other):
        return True
points = [Point(i) for i in range(N+1)]

in_r = [ri for ri in map(int, input().split())]
for A, B, C in (map(int, input().split()) for _ in range(M)):
    points[A].addNeighbor(B, C)
    points[B].addNeighbor(A, C)

for x in points:
    x.optimize()

def addcursor(cur):
    c = cur.cost()
    if not c is None:
        heapq.heappush(hq, (c, cur))

def getRs(rs = None, cnt = -1, ret = None):
    if rs is None:
        rs = [False] * R
        ret = []
        cnt = R

    if cnt <= 0:
        yield ret
        return

    cnt -= 1

    for i in range(R):
        if not rs[i]:
            rs[i] = True
            ret.append(i)
            yield from getRs(rs, cnt, ret)
            ret.pop()
            rs[i] = False

Rmatrix = [[-1 for _ in range(R)] for _ in range(R) ]

for i in range(R):
    for j in range(R):
        if i >= j:
            continue

        meetinfo = MeetInfo()
        for x in points:
            x.clear()
        rs = [Cursor(i, points[ri], meetinfo)  for i, ri in enumerate((in_r[i], in_r[j]))]
        hq = []
        for ri in rs:
            addcursor(ri)

        while not meetinfo.isMet():
            cost, cursor = heapq.heappop(hq)
            cursor.progress()

        Rmatrix[i][j] = meetinfo.distance
        Rmatrix[j][i] = meetinfo.distance

M = 10 ** 9
for r in getRs():
    w = 0
    for i in range(R-1):
        w += Rmatrix[r[i]][r[i+1]]    
    M = min(M, w)

print(M)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
from scipy.sparse.csgraph import dijkstra as di
N,M,R=map(int,input().split())
r=list(map(int,input().split()))
dp=[[0 for _ in range(N)] for _ in range(N)]

for _ in range(M):
  A,B,C=map(int,input().split())
  if dp[A-1][B-1]==0 or dp[A-1][B-1]>C:
    dp[A-1][B-1]=C
    dp[B-1][A-1]=C
distance=di(dp)
'''
def get_target_min_index(min_index, distance, unsearched_nodes):
    start = 0
    while True:
        index = distance.index(min_index, start)
        found = index in unsearched_nodes
        if found:
            return index
        else:
            start = index + 1


distance = [[100001]*N] * N # ノードごとの距離のリスト


for i in range(R):
  for j in range(i+1,R):
    dist=[100001]*N
    dist[r[i]]=0
    unsearched_nodes = list(range(N)) # 未探索ノード
    previous_nodes = [-1] * N # 最短経路でそのノードのひとつ前に到達するノードのリスト
    while(len(unsearched_nodes) != 0): #未探索ノードがなくなるまで繰り返す
    # まず未探索ノードのうちdistanceが最小のものを選択する
      posible_min_distance = 100001 # 最小のdistanceを見つけるための一時的なdistance。初期値は inf に設定。
      for node_index in unsearched_nodes: # 未探索のノードのループ
          if posible_min_distance > dist[node_index]: 
              posible_min_distance = dist[node_index] # より小さい値が見つかれば更新
      target_min_index = get_target_min_index(posible_min_distance, dist, unsearched_nodes) # 未探索ノードのうちで最小のindex番号を取得
      unsearched_nodes.remove(target_min_index) # ここで探索するので未探索リストから除去

      target_edge = dp[target_min_index] # ターゲットになるノードからのびるエッジのリスト
      for index, route_dis in enumerate(target_edge):
          if route_dis != 0:
              if dist[index] > (dist[ target_min_index] + route_dis):
                  dist[index] = dist[ target_min_index] + route_dis # 過去に設定されたdistanceよりも小さい場合はdistanceを更新
                  previous_nodes[index] =  target_min_index #　ひとつ前に到達するノードのリストも更新
    #print("-----経路-----")
    previous_node = r[j]
    while previous_node != -1:
      if previous_node !=i:
        #print(str(previous_node + 1) + " <- ", end='')
      else:
        #print(str(previous_node + 1))
      previous_node = previous_nodes[previous_node]

    #print("-----距離-----")
    #print(dist[j])
    distance[i][j]=dist[j]
    distance[j][i]=dist[j]
'''

ans=10**11
for tmp in permutations(r):
  tmpans=0
  for i in range(len(tmp)-1):
    tmpans+=distance[tmp[i]-1][tmp[i+1]-1]
  if ans>tmpans:
    ans=tmpans
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
from scipy.sparse.csgraph import dijkstra as di
N,M,R=map(int,input().split())
r=list(map(int,input().split()))
dp=[[0 for _ in range(N)] for _ in range(N)]

for _ in range(M):
  A,B,C=map(int,input().split())
  if dp[A-1][B-1]==0 or dp[A-1][B-1]>C:
    dp[A-1][B-1]=C
    dp[B-1][A-1]=C
print(dp)
distance=di(dp)
'''
def get_target_min_index(min_index, distance, unsearched_nodes):
    start = 0
    while True:
        index = distance.index(min_index, start)
        found = index in unsearched_nodes
        if found:
            return index
        else:
            start = index + 1


distance = [[100001]*N] * N # ノードごとの距離のリスト


for i in range(R):
  for j in range(i+1,R):
    dist=[100001]*N
    dist[r[i]]=0
    unsearched_nodes = list(range(N)) # 未探索ノード
    previous_nodes = [-1] * N # 最短経路でそのノードのひとつ前に到達するノードのリスト
    while(len(unsearched_nodes) != 0): #未探索ノードがなくなるまで繰り返す
    # まず未探索ノードのうちdistanceが最小のものを選択する
      posible_min_distance = 100001 # 最小のdistanceを見つけるための一時的なdistance。初期値は inf に設定。
      for node_index in unsearched_nodes: # 未探索のノードのループ
          if posible_min_distance > dist[node_index]: 
              posible_min_distance = dist[node_index] # より小さい値が見つかれば更新
      target_min_index = get_target_min_index(posible_min_distance, dist, unsearched_nodes) # 未探索ノードのうちで最小のindex番号を取得
      unsearched_nodes.remove(target_min_index) # ここで探索するので未探索リストから除去

      target_edge = dp[target_min_index] # ターゲットになるノードからのびるエッジのリスト
      for index, route_dis in enumerate(target_edge):
          if route_dis != 0:
              if dist[index] > (dist[ target_min_index] + route_dis):
                  dist[index] = dist[ target_min_index] + route_dis # 過去に設定されたdistanceよりも小さい場合はdistanceを更新
                  previous_nodes[index] =  target_min_index #　ひとつ前に到達するノードのリストも更新
    #print("-----経路-----")
    previous_node = r[j]
    while previous_node != -1:
      if previous_node !=i:
        #print(str(previous_node + 1) + " <- ", end='')
      else:
        #print(str(previous_node + 1))
      previous_node = previous_nodes[previous_node]

    #print("-----距離-----")
    #print(dist[j])
    distance[i][j]=dist[j]
    distance[j][i]=dist[j]
'''

ans=10**11
for tmp in permutations(r):
  tmpans=0
  for i in range(len(tmp)-1):
    tmpans+=distance[tmp[i]-1][tmp[i+1]-1]
  if ans>tmpans:
    ans=tmpans
print(int(ans))