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:
def main():
    from sys import stdin
    input = stdin.readline

    n, m, r = map(int, input().split())
    l = [int(i) - 1 for i in input().split()]
    d = [[2*(10**7)] * n for _ in range(n)]
    for _ in range(m):
        i, j, k = map(int, input().split())
        d[i-1][j-1] = k
        d[j-1][i-1] = k

    # Warshall-Floyd algorithm
    for k in range(n):
        for i in range(n-1):
            for j in range(i+1, n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
                    d[j][i] = d[i][j]

    # full search
    # 8! = 40320
    from itertools import permutations

    answer = 2*(10**7)
    for i in permutations(l):
        ans = 0
        for j in range(r-1):
            ans += d[i[j]][i[j+1]]
        if ans < answer:
            answer = ans

    print(answer)

main()

Submission status: Wrong Answer

Solution code:
from collections import deque
INF = 10**12+7
N,M,R = map(int,input().split())
r = list(map(str,input().split()))
d = [[INF]*(N+1) for _ in range(N+1)]
for _ in range(M):
    A,B,C = map(int,input().split())
    d[A][B] = C
    d[B][A] = C
for i in range(1,N+1):
    d[i][i] = 0
for k in range(N+1):
    for i in range(N+1):
        for j in range(N+1):
            d[i][j] = min(d[i][j],d[i][k] + d[k][j])
#print(d)
ans = INF
que = deque(r)
while len(que) != 0:
    p = que.popleft()
    if len(p) == R:
        #print(p)
        val = 0
        for i in range(1,R):
            val += d[ int(p[i-1])][int(p[i])]
        ans = min(ans,val)
    else:
        for i in r:
            if not i in p:
                que.append(p+i)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
INF = 10**12+7
N,M,R = map(int,input().split())
r = list(map(str,input().split()))
d = [[INF]*(N+1) for _ in range(N+1)]
for _ in range(M):
    A,B,C = map(int,input().split())
    d[A][B] = C
    d[B][A] = C
for i in range(1,N+1):
    d[i][i] = 0
for k in range(N+1):
    for i in range(N+1):
        for j in range(N+1):
            d[i][j] = min(d[i][j],d[i][k] + d[k][j])
#print(d)
ans = INF
que = deque(r)
while len(que) != 0:
    p = que.popleft()
    if len(p) == R:
        val = 0
        for i in range(1,R):
            val += d[ int(p[i-1])][int(p[i])]
        ans = min(ans,val)
    else:
        for i in r:
            if not i in p:
                que.append(p+i)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
INF = 10**12+7
N,M,R = map(int,input().split())
r = list(map(str,input().split()))
d = [[INF]*(N+1) for _ in range(N+1)]
for _ in range(M):
    A,B,C = map(int,input().split())
    d[A][B] = C
    d[B][A] = C
for i in range(1,N+1):
    d[i][i] = 0
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            d[i][j] = min(d[i][j],d[i][k] + d[k][j])
ans = INF
que = deque(r)
while len(que) != 0:
    p = que.popleft()
    if len(p) == R:
        val = 0
        for i in range(1,R):
            val += d[int(p[i-1])][int(p[i])]
        ans = min(ans,val)
    else:
        for i in r:
            if not i in p:
                que.append(p+i)


print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
INF = 10**12+7
N,M,R = map(int,input().split())
r = list(map(str,input().split()))
d = [[INF]*(N+1) for _ in range(N+1)]
for _ in range(M):
    A,B,C = map(int,input().split())
    d[A][B] = C
    d[B][A] = C
for i in range(1,N+1):
    d[i][i] = 0
for k in range(N+1):
    for i in range(N+1):
        for j in range(N+1):
            d[i][j] = min(d[i][j],d[i][k] + d[k][j])
for k in range(N+1):
    for i in range(N+1):
        for j in range(N+1):
            d[i][j] = min(d[i][j],d[i][k] + d[k][j])
for k in range(N+1):
    for i in range(N+1):
        for j in range(N+1):
            d[i][j] = min(d[i][j],d[i][k] + d[k][j])
ans = INF
que = deque(r)
while len(que) != 0:
    p = que.popleft()
    if len(p) == R:
        val = 0
        for i in range(1,R):
            val += d[int(p[i-1])][int(p[i])]
        ans = min(ans,val)
    else:
        for i in r:
            if not i in p:
                que.append(p+i)


print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
INF = 10**12+7
N,M,R = map(int,input().split())
r = list(map(str,input().split()))
d = [[INF]*(N+1) for _ in range(N+1)]
for _ in range(M):
    A,B,C = map(int,input().split())
    d[A][B] = C
    d[B][A] = C
for i in range(1,N+1):
    d[i][i] = 0
for k in range(N+1):
    for i in range(N+1):
        for j in range(N+1):
            d[i][j] = min(d[i][j],d[i][k] + d[k][j])
ans = INF
que = deque(r)
while len(que) != 0:
    p = que.popleft()
    if len(p) == R:
        print(p)
        val = 0
        for i in range(1,R):
            val += d[int(p[i-1])][int(p[i])]
        ans = min(ans,val)
    else:
        for i in r:
            if not i in p:
                que.append(p+i)


print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
INF = 10**12+7
N,M,R = map(int,input().split())
r = list(map(str,input().split()))
d = [[INF]*(N+1) for _ in range(N+1)]
for _ in range(M):
    A,B,C = map(int,input().split())
    d[A][B] = C
    d[B][A] = C
for i in range(1,N+1):
    d[i][i] = 0
for k in range(N+1):
    for i in range(N+1):
        for j in range(N+1):
            d[i][j] = min(d[i][j],d[i][k] + d[k][j])
ans = INF
que = deque(r)
val = []
while len(que) != 0:
    p = que.popleft()
    if len(p) == R:
        val.append(list(p))

        # val = 0
        # for i in range(1,R):
        #     val += d[int(p[i-1])][int(p[i])]
        # ans = min(ans,val)
    else:
        for i in r:
            if not i in p:
                que.append(p+i)
#print(val)
for i in val:
    val = 0
    for j in range(1,R):
        val += d[ int(i[j-1]) ][ int(i[j])]
    ans = min(ans,val)


print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
INF = 10**12+7
N,M,R = map(int,input().split())
r = list(map(str,input().split()))
d = [[INF]*(N+1) for _ in range(N+1)]
for _ in range(M):
    A,B,C = map(int,input().split())
    d[A][B] = C
    d[B][A] = C
for i in range(1,N+1):
    d[i][i] = 0
for k in range(N+1):
    for i in range(N+1):
        for j in range(N+1):
            d[i][j] = min(d[i][j],d[i][k] + d[k][j])
ans = INF
que = deque(r)
while len(que) != 0:
    p = que.popleft()
    if len(p) == R:
        val = 0
        for i in range(1,R):
            val += d[int(p[i-1])][int(p[i])]
        ans = min(ans,val)
    else:
        for i in r:
            if not i in p:
                que.append(p+i)


print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
INF = 10**12+7
N,M,R = map(int,input().split())
r = list(map(str,input().split()))
d = [[INF]*(N+1) for _ in range(N+1)]
for _ in range(M):
    A,B,C = map(int,input().split())
    d[A][B] = C
    d[B][A] = C
for i in range(1,N+1):
    d[i][i] = 0
for k in range(N+1):
    for i in range(N+1):
        for j in range(N+1):
            d[i][j] = min(d[i][j],d[i][k] + d[k][j])
ans = INF
que = deque(r)
#print(que)
while len(que) != 0:
    p = que.popleft() 
    if len(p) == R:
        val = 0
        for i in range(1,R):
            val += d[int(p[i-1])][int(p[i])]
        ans = min(ans,val)
    else:
        for i in r:
            if not i in p:
                que.append(p+i)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
INF = 10**12+7
N,M,R = map(int,input().split())
r = list(map(str,input().split()))
d = [[INF]*(N+1) for _ in range(N+1)]
for _ in range(M):
    A,B,C = map(int,input().split())
    d[A][B] = C
    d[B][A] = C
for i in range(1,N+1):
    d[i][i] = 0
for k in range(N+1):
    for i in range(N+1):
        for j in range(N+1):
            d[i][j] = min(d[i][j],d[i][k] + d[k][j])
#print(d)
ans = INF
que = deque([])
for j in r:
    que = deque([(j,0)])
    while len(que) != 0:
        p = que.popleft() 
        if len(p[0]) == R:
            ans = min(ans,p[1])
        else:
            for i in r:
                if not i in p[0]:
                    que.append( (p[0]+i, p[1] + d[ int(p[0][-1]) ][int(i)]) )
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
INF = 10**12+7
N,M,R = map(int,input().split())
r = list(map(str,input().split()))
d = [[INF]*(N+1) for _ in range(N+1)]
for _ in range(M):
    A,B,C = map(int,input().split())
    d[A][B] = C
    d[B][A] = C
for i in range(1,N+1):
    d[i][i] = 0
for k in range(N+1):
    for i in range(N+1):
        for j in range(N+1):
            d[i][j] = min(d[i][j],d[i][k] + d[k][j])
#print(d)
ans = INF
que = deque([])
for j in r:
    que = deque([(j,0)])
    while len(que) != 0:
        p = que.popleft() 
        if len(p[0]) == R:
            ans = min(ans,p[1])
        else:
            for i in r:
                if not i in p[0]:
                    que.append( (''.join([p[0],i]), p[1] + d[ int(p[0][-1]) ][int(i)]) )
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
INF = 10**12+7
N,M,R = map(int,input().split())
r = list(map(str,input().split()))
d = [[INF]*(N+1) for _ in range(N+1)]
for _ in range(M):
    A,B,C = map(int,input().split())
    d[A][B] = C
    d[B][A] = C
for i in range(1,N+1):
    d[i][i] = 0
for k in range(N+1):
    for i in range(N+1):
        for j in range(N+1):
            d[i][j] = min(d[i][j],d[i][k] + d[k][j])
#print(d)
ans = INF
for j in r:
    que = deque([[j,0]])
    while len(que):
        p = que.popleft()
        #print(p)
        if len(p[0]) == R:
            ans = min(ans,p[1])
        else:
            for i in r:
                if not i in p[0]:
                    que.append([''.join([p[0],i]), p[1] + d[ int(p[0][-1]) ][ int(i)] ])
                    #print([''.join([p[0],i]), p[1]+d[int(p[0][-1])][int(i)]])
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
INF = 10**9+7
N,M,R = map(int,input().split())
r = list(map(str,input().split()))
d = [[INF]*(N+1) for _ in range(N+1)]
for _ in range(M):
    A,B,C = map(int,input().split())
    d[A][B] = C
    d[B][A] = C
# for i in range(1,N+1):
#     d[i][i] = 0
for k in range(N+1):
    for i in range(N+1):
        for j in range(N+1):
            d[i][j] = min(d[i][j],d[i][k] + d[k][j])
#print(d)
ans = INF
for j in r:
    que = deque([[j,0]])
    while len(que):
        p = que.popleft()
        if len(p[0]) == R:
            ans = min(ans,p[1])
        else:
            for i in r:
                if not i in p[0]:
                    que.append([''.join([p[0],i]), p[1]+d[int(p[0][-1])][int(i)]])
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
INF = 10**9+7
N,M,R = map(int,input().split())
r = list(map(str,input().split()))
d = [[INF]*(N+1) for _ in range(N+1)]
for _ in range(M):
    A,B,C = map(int,input().split())
    d[A][B] = C
    d[B][A] = C
# for i in range(1,N+1):
#     d[i][i] = 0
for k in range(N+1):
    for i in range(N+1):
        for j in range(N+1):
            d[i][j] = min(d[i][j],d[i][k] + d[k][j])
print(d)
ans = INF
for j in r:
    que = deque([[j,0]])
    while len(que):
        p = que.popleft()
        if len(p[0]) == R:
            ans = min(ans,p[1])
        else:
            for i in r:
                if not i in p[0]:
                    que.append([''.join([p[0],i]), p[1]+d[int(p[0][-1])][int(i)]])
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
INF = 10**9+7
N,M,R = map(int,input().split())
r = list(map(str,input().split()))
d = [[INF]*(N+1) for _ in range(N+1)]
for _ in range(M):
    A,B,C = map(int,input().split())
    d[A][B] = C
    d[B][A] = C
for k in range(N+1):
    for i in range(N+1):
        for j in range(N+1):
            d[i][j] = min(d[i][j],d[i][k] + d[k][j])
ans = INF
for j in r:
    que = deque([[j,0]])
    while len(que):
        p = que.popleft()
        if len(p[0]) == R:
            ans = min(ans,p[1])
        else:
            for i in r:
                if not i in p[0]:
                    que.append([''.join([p[0],i]), p[1]+d[int(p[0][-1])][int(i)]])
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
n_node, n_edge, R = map(int,input().split())
r_ls = list(map(int,input().split()))
for i in range(R):
    r_ls[i] -= 1
ad_mat = [[float('inf')]*n_node for _ in range(n_node)]
for i in range(n_node):
    ad_mat[i][i] = 0
for i in range(n_edge):
    a,b,c = map(int,input().split())
    ad_mat[a-1][b-1] = c
    ad_mat[b-1][a-1] = c

# ワーシャルフロイド
for start in range(n_node):
    for end in range(n_node):
        for stop in range(n_node):
            ad_mat[start][end] = min(ad_mat[start][end],ad_mat[start][stop]+ad_mat[stop][end])

ans = float('inf')
for path in permutations(r_ls):
    cost = 0
    for i in range(R-1):
        cost += ad_mat[path[i]][path[i+1]]
    ans = min(ans,cost)
print(ans)

Submission status: Wrong Answer

Solution code:
N, M, K = (int(x) for x in input().split())
R = [int(x)-1 for x in input().split()]
graph = [[] for _ in range(N)]
cost = {}
for _ in range(M):
    a, b, c = (int(x) for x in input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    cost[min(a-1,b-1), max(b-1,a-1)] = c 
del a, b, c, K

dist = [[10e8 for _ in range(N)] for _ in range(N)]
for i in range(N): dist[i][i] = 0

def dfs(v, r, passed):
    global graph, dist
    passed.add(v)
    for nv in graph[v]:
        dist[r][v] = dist[v][r] =  min(dist[r][v], dist[r][v] + cost[min(v,nv),max(v,nv)])
        if not nv in passed:
            dfs(nv, r, passed)
    passed.remove(v)
    return 0

def mindist(x, X):
    global dist
    Y = X.copy()
    Y.remove(x)
    if len(Y) == 0: return 0
    return min([dist[x][y] + mindist(y,Y) for y in Y])

passed = set()
for r in R:
    dfs(r, r, passed)
ans = min([mindist(r, R) for r in R])
print(ans)

Submission status: Wrong Answer

Solution code:
N, M, K = (int(x) for x in input().split())
R = [int(x)-1 for x in input().split()]
graph = [[] for _ in range(N)]
cost = {}
for _ in range(M):
    a, b, c = (int(x) for x in input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    cost[min(a-1,b-1), max(b-1,a-1)] = c 
del a, b, c, K

dist = [[10e8 for _ in range(N)] for _ in range(N)]
for i in range(N): dist[i][i] = 0 

for r in R:
    V = [r]
    found = {r}
    while len(V) !=0:
        for i in V:
            temp = 10e8
            if dist[r][i] < temp:
                temp = dist[r][i]
                v = i
        for nv in graph[v]:
            dist[r][nv] = dist[nv][r] = min(dist[r][nv], dist[r][v]+cost[min(v,nv), max(v,nv)])
            if nv in found: continue
            found.add(nv)
            V.append(nv)
        V.remove(v)

def mindist(x, X):
    global dist
    Y = X.copy()
    Y.remove(x)
    if len(Y) == 0: return 0
    return min([dist[x][y] + mindist(y,Y) for y in Y])


ans = min([mindist(r, R) for r in R])
print(ans)

Submission status: Wrong Answer

Solution code:
N, M, K = (int(x) for x in input().split())
R = [int(x)-1 for x in input().split()]
graph = [[] for _ in range(N)]
cost = {}
for _ in range(M):
    a, b, c = (int(x) for x in input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    cost[min(a-1,b-1), max(b-1,a-1)] = c 
del a, b, c, K

dist = [[10e8 for _ in range(N)] for _ in range(N)]
for i in range(N): dist[i][i] = 0 

for r in R:
    V = [r]
    found = {r}
    while len(V) !=0:
        for i in V:
            temp = 10e8
            if dist[r][i] < temp:
                temp = dist[r][i]
                v = i
        for nv in graph[v]:
            dist[r][nv] = dist[nv][r] = min(dist[r][nv], dist[r][v]+cost[min(v,nv), max(v,nv)])
            if nv in found: continue
            found.add(nv)
            V.append(nv)
        V.pop(0)

def mindist(x, X):
    global dist
    Y = X.copy()
    Y.remove(x)
    if len(Y) == 0: return 0
    return min([dist[x][y] + mindist(y,Y) for y in Y])


ans = min([mindist(r, R) for r in R])
print(ans)

Submission status: Wrong Answer

Solution code:
N, M, K = (int(x) for x in input().split())
R = [int(x)-1 for x in input().split()]
graph = [[] for _ in range(N)]
cost = {}
for _ in range(M):
    a, b, c = (int(x) for x in input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    cost[a-1,b-1] = c
    cost[b-1,a-1] = c
del a, b, c, K
dist = [[-1 for _ in range(N)] for _ in range(N)]
for i in range(N): dist[i][i] = 0 

v = [0]
found = {0}
passed = []
while len(v) != 0:
    passed.append(v[0])
    for nv in graph[v[0]]:
        for p in passed:
            if dist[p][nv] == -1: dist[p][nv] = dist[p][v[0]]+cost[v[0],nv]
            else: dist[p][nv] = dist[nv][p] = min(dist[p][nv], dist[p][v[0]]+cost[v[0],nv])
            if nv in found: continue
            found.add(nv)
            v.append(nv)
    v.pop(0)

def mindist(x, X):
    global dist
    Y = X.copy()
    Y.remove(x)
    if len(Y) == 0: return 0
    return min([dist[x][y] + mindist(y,Y) for y in Y])


ans = min([mindist(r, R) for r in R])
print(ans)

Submission status: Wrong Answer

Solution code:
N, M, K = (int(x) for x in input().split())
R = [int(x)-1 for x in input().split()]
graph = [[] for _ in range(N)]
cost = {}
for _ in range(M):
    a, b, c = (int(x) for x in input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    cost[a-1,b-1] = c
    cost[b-1,a-1] = c
del a, b, c, K
dist = [[-1 for _ in range(N)] for _ in range(N)]
for i in range(N): dist[i][i] = 0 

for r in R:
    v = [r]
    found = {r}
    while len(v) !=0:
        for nv in graph[v[0]]:
            if dist[r][nv] == -1: dist[r][nv] = dist[r][v[0]]+cost[v[0],nv]
            else: dist[r][nv] = dist[nv][r] = min(dist[r][nv], dist[r][v[0]]+cost[v[0],nv])
            if nv in found: continue
            found.add(nv)
            v.append(nv)
        v.pop(0)

def mindist(x, X):
    global dist
    Y = X.copy()
    Y.remove(x)
    if len(Y) == 0: return 0
    return min([dist[x][y]+mindist(y,Y) for y in Y])


ans = min([mindist(r, R) for r in R])
print(ans)

Submission status: Wrong Answer

Solution code:
N, M, K = (int(x) for x in input().split())
R = [int(x)-1 for x in input().split()]
graph = [[] for _ in range(N)]
cost = {}
for _ in range(M):
    a, b, c = (int(x) for x in input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    cost[a-1,b-1] = c
    cost[b-1,a-1] = c
del a, b, c, K
INF = 100000000
dist = [[INF for _ in range(N)] for _ in range(N)]
for i in range(N): dist[i][i] = 0 

for r in range(N):
    v = [r]
    found = {r}
    while len(v) !=0:
        for nv in graph[v[0]]:
            dist[r][nv] = dist[nv][r] = min(dist[r][nv], dist[r][v[0]]+cost[v[0],nv])
            if nv in found: continue
            found.add(nv)
            v.append(nv)
        v.pop(0)

def mindist(x, X):
    global dist
    result = 100000000
    Y = X.copy()
    Y.remove(x)
    if len(Y) == 0: return 0
    return min([dist[x][y]+mindist(y,Y) for y in Y])


ans = min([mindist(r, R) for r in R])
print(ans)

Submission status: Wrong Answer

Solution code:
N, M, K = (int(x) for x in input().split())
R = [int(x)-1 for x in input().split()]
graph = [[] for _ in range(N)]
cost = {}
for _ in range(M):
    a, b, c = (int(x) for x in input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    cost[a-1,b-1] = c
    cost[b-1,a-1] = c
del a, b, c, K
INF = 100000000
dist = [[INF for _ in range(N)] for _ in range(N)]
for i in range(N): dist[i][i] = 0 

for r in R:
    v = [r]
    found = {r}
    while len(v) !=0:
        for nv in graph[v[0]]:
            dist[r][nv] = dist[nv][r] = min(dist[r][nv], dist[r][v[0]]+cost[v[0],nv])
            if nv in found: continue
            found.add(nv)
            v.append(nv)
        v.pop(0)

def mindist(x, X):
    global dist
    result = 100000000
    Y = X.copy()
    Y.remove(x)
    if len(Y) == 0: return 0
    return min([dist[x][y]+mindist(y,Y) for y in Y])


ans = min([mindist(r, R) for r in R])
print(ans)

Submission status: Wrong Answer

Solution code:
N, M, K = (int(x) for x in input().split())
R = [int(x)-1 for x in input().split()]
graph = [[] for _ in range(N)]
cost = {}
for _ in range(M):
    a, b, c = (int(x) for x in input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    cost[a-1,b-1] = c
    cost[b-1,a-1] = c
del a, b, c, K
INF = 100000000
dist = [[INF for _ in range(N)] for _ in range(N)]
for i in range(N): dist[i][i] = 0 

for r in R:
    v = [r]
    found = {r}
    while len(v) !=0:
        for nv in graph[v[0]]:
            dist[r][nv] = dist[nv][r] = min(dist[r][nv], dist[r][v[0]]+cost[v[0],nv])
            if nv in found: continue
            found.add(nv)
            v.append(nv)
        v.pop(0)

def mindist(i, X):
    global dist
    result = 100000000
    Xcopy = X.copy()
    Xcopy.remove(i)
    if len(Xcopy) == 0: return 0
    for x in Xcopy: result = min(result, dist[i][x]+mindist(x,Xcopy))
    return result


ans = [mindist(r, R) for r in R]
ans.sort()
print(ans[0])

Submission status: Wrong Answer

Solution code:
N, M, K = (int(x) for x in input().split())
R = [int(x)-1 for x in input().split()]
graph = [[] for _ in range(N)]
cost = {}
for _ in range(M):
    a, b, c = (int(x) for x in input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    cost[a-1,b-1] = c
    cost[b-1,a-1] = c
del a, b, c, K
INF = 100000000
dist = [[INF for _ in range(N)] for _ in range(N)]
for i in range(N): dist[i][i] = 0 

for r in R:
    v = [r]
    found = {r}
    while len(v) !=0:
        for nv in graph[v[0]]:
            found.add(nv)
            dist[r][nv] = dist[nv][r] = min(dist[r][nv], dist[r][v[0]]+cost[v[0],nv])
            if nv in found: continue
            v.append(nv)
        v.pop(0)

def mindist(i, X):
    global dist
    result = 100000000
    Xcopy = X.copy()
    Xcopy.remove(i)
    if len(Xcopy) == 0: return 0
    for x in Xcopy: result = min(result, dist[i][x]+mindist(x,Xcopy))
    return result


ans = [mindist(r, R) for r in R]
ans.sort()
print(ans[0])

Submission status: Wrong Answer

Solution code:
N, M, K = (int(x) for x in input().split())
R = [int(x)-1 for x in input().split()]
graph = [[] for _ in range(N)]
cost = {}
for _ in range(M):
    a, b, c = (int(x) for x in input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    cost[a-1,b-1] = c
    cost[b-1,a-1] = c
del a, b, c, K
INF = 100000000
dist = [[INF for _ in range(N)] for _ in range(N)]
for i in range(N): dist[i][i] = 0 

for r in R:
    v = [r]
    seen = set()
    while len(v) !=0:
        for nv in graph[v[0]]:
            if nv in seen: continue
            dist[r][nv] = dist[nv][r] = min(dist[r][nv], dist[r][v[0]]+cost[v[0],nv])
            v.append(nv)
        seen.add(v[0])
        v.pop(0)

def mindist(i, X):
    global dist
    result = 100000000
    Xcopy = X.copy()
    Xcopy.remove(i)
    if len(Xcopy) == 0: return 0
    for x in Xcopy: result = min(result, dist[i][x]+mindist(x,Xcopy))
    return result


ans = [mindist(r, R) for r in R]
ans.sort()
print(ans[0])

Submission status: Wrong Answer

Solution code:
from itertools import permutations
n,m,r=map(int, input().split())
r_l=[int(i)-1 for i in input().split()]
town = [[0]*n for _ in range(n)]
for i in range(m):
    a,b,c=map(int, input().split())
    town[a-1][b-1]=c
    town[b-1][a-1]=c

for k in range(n):
    for i in range(n):
        for j in range(n):
            town[i][j] = min(town[i][j],town[i][k]+town[k][j])
res = float("INF")
for root in list(permutations(r_l)):
    tmp = 0
    for i in range(1,r):
        tmp += town[root[i]][root[i-1]]
    res = min(tmp,res)

print(res)

Submission status: Wrong Answer

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


def solve(N: int, M: int, R: int, r: "List[int]", A: "List[int]", B: "List[int]", C: "List[int]"):
    from scipy.sparse import coo_matrix
    from scipy.sparse.csgraph import floyd_warshall
    import numpy as np
    # coo_matrix((data, (i, j)), [shape=(M, N)])
    mat = floyd_warshall(coo_matrix((C, (A, B)), shape=(N+1, N+1), dtype=np.int32).tocsr())

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
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))
    print(solve(N, M, R, r, A, B, C))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Wrong Answer

Solution code:
from itertools import permutations

def warshall_floyd():
    '''
    すべての頂点間の最短距離を求める (重み付き有向グラフ)
    '''
    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])

    return dist


n, m, r = map(int, input().split())
city = list(map(int, input().split()))

dist = [[float('inf')] * n for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    dist[a-1][b-1] = c
    dist[b-1][a-1] = c
for i in range(n):
    dist[i][i] = 0

print(warshall_floyd())

Submission status: Wrong Answer

Solution code:
from itertools import permutations

def warshall_floyd():
    '''
    すべての頂点間の最短距離を求める (重み付き有向グラフ)
    '''
    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])

    return dist


n, m, r = map(int, input().split())
city = list(map(int, input().split()))

dist = [[float('inf')] * n for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    dist[a-1][b-1] = c
    dist[b-1][a-1] = c
for i in range(n):
    dist[i][i] = 0

print(warshall_floyd())

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

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

def make_permutation(l,R):
    if R == 0:
        perm_list.append(l)
    else:
        for a in r:
            if a not in l:
                make_permutation(l+[a],R-1)

def main():
    for _ in range(M):
        A, B, C = map(int, input().split())
        adj[A-1][B-1] = C
        adj[B-1][A-1] = C
    
    # 方針: Warshall-Floydで各頂点間の最短距離を求めてからrの順列全探索
    for i in range(N):
        for j in range(N):
            for k in range(N):
                adj[i][j] = min(adj[i][j], adj[i][k]+adj[k][j])

    make_permutation([],R)
    ans = INF
    for ps in perm_list:
        tmp = 0
        for i in range(R-1):
            tmp += adj[ps[i]-1][ps[i+1]-1]
        ans = min(ans,tmp)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from itertools import permutations as per
n,m,r = map(int,input().split())
v = list(map(int,input().split()))
for i in range(r):
    v[i] -= 1
INF = float("inf")
g = [[INF]*n for _ in range(n)]
for i in range(m):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    g[a][b] = c
    g[b][a] = c
for i in range(n): g[i][i] = 0
for i in range(n):
    for j in range(n):
        for k in range(n):
            g[i][j] = min(g[i][j],g[i][k]+g[k][j])

ans = INF
for l in per(range(r)):
    t = 0
    for i in range(r-1):
        t += g[v[l[i]]][v[l[i+1]]]
    ans = min(ans,t)
print(ans)

Submission status: Wrong Answer

Solution code:
n,m,r = map(int,input().split())
v = list(map(int,input().split()))
for i in range(r):
    v[i] -= 1
INF = float("inf")
g = [[INF]*n for _ in range(n)]
for i in range(m):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    g[a][b] = c
    g[b][a] = c
for i in range(n): g[i][i] = 0
for i in range(n):
    for j in range(n):
        for k in range(n):
            g[i][j] = min(g[i][j],g[i][k]+g[k][j])


dp = [[INF]*r for i in range(2**r)]
for i in range(r):
    dp[2**i][i] = 0


for i in range(1,2**r):
    for j in range(r):
        if dp[i][j] == INF:
            continue
        for k in range(r):
            nxt = i | 2**k
            dp[nxt][k] = min(dp[nxt][k],dp[i][j]+g[v[j]][v[k]])

print(min(dp[-1]))

Submission status: Wrong Answer

Solution code:
from itertools import permutations
INFTY = 10**8
N,M,R = map(int,input().split())
r = list(map(int,input().split()))
G = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b,c = map(int,input().split())
    G[a].append((b,c))
    G[b].append((a,c))
dist = [[INFTY for _ in range(N+1)] for _ in range(N+1)]
for i in range(1,N+1):
    dist[i][i] = 0
for i in range(1,N+1):
    for j,d in G[i]:
        dist[i][j] = d
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j])
dmin = 10**8
for i in range(R):
    for j in range(R):
        if i!=j:
            A = list(range(R))
            A.remove(i)
            A.remove(j)
            if len(A)>0:
                for x in permutations(A,R-2):
                    d = dist[r[i]][r[x[0]]]
                    for k in range(1,R-2):
                        d += dist[r[x[k]]][r[x[k-1]]]
                    d += dist[r[x[R-3]]][r[j]]
            else:
                d = dist[r[i]][r[j]]
            dmin = min(dmin,d)
print(dmin)