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:
n,m,R = map(int,input().split())
r = list(map(int,input().split()))
from itertools import permutations
import numpy as np
cost = np.ones((n,n))*float('inf')
for i in range(m):
    a,b,c = map(int,input().split())
    cost[a-1][b-1]=cost[b-1][a-1]=c

def main():

    def dijkstra(g,n,s):
        d = [float('inf')]*n
        U = [i for i in range(n)]
        d[s] = 0
        while len(U)>0:
            w = U[0]
            for u in U:
                if d[u]<d[w]:
                    w = u
            U.pop(U.index(w))
            for v in U:
                d[v] = min(d[v],d[w]+g[w][v])
        return d

    dis_dict = {}
    m = float('inf')
    for i in range(n):
        dis_dict[i] = dijkstra(cost,n,i)
    for j in permutations(r):
        l = 0
        for i in range(len(j)-1):
            s,t = j[i],j[i+1]
            l += dis_dict[s-1][t-1]
        if l<m:
            m = l
    print(m)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N,M,R=map(int,input().split())
r=list(map(int,input().split()))
d=[[10**15 for i in range(0,N+1)] for i in range(0,N+1)]
for i in range(0,M):
    a,b,c=map(int,input().split())
    d[a][b]=c
    d[b][a]=c

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

ans=10**15
def dfs(load,cost):
    global ans
    if len(load)==R:
        if ans>cost:
            ans=cost

    elif len(load)!=0:
        for city in r:
            if not city in load:
                a=list(load)[-1]
                b=set(list(load)+[city])
                dfs(b,cost+d[a][city])

    else:
        for city in r:
            dfs(set([city]),0)



dfs(set([]),0)

print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
from heapq import heappop, heappush

N,M,R=map(int,input().split())
town=list(map(int,input().split()))
INF=10**9
G=[[INF for i in range(N+1)] for j 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=[[INF*10 for i in range(N+1)] for j in range(R)]

for k in range(R):
    r=town[k]
    d[k][r]=0
    
    used=[False for i in range(N+1)]
    
    heap=[]
    heappush(heap,(d[k][r],r))
    
    while heap:
        d_u, u = heappop(heap)

        used[u] = True
        
        if d[k][u] < d_u:
            continue
        
        for v in range(N+1):
            if not(used[v]) and d_u + G[u][v] < d[k][v]:
                d[k][v] = d_u + G[u][v]
                heappush(heap,(d[k][v],v))

ans=INF

for i in range(R):
    Now=i
    until=[]
    for j in range(R):
        if i!=j:
            until.append(j)
    
    D=0
    while until:
        tmp=INF
        for j in range(len(until)):
            u=until[j]
            if d[Now][town[u]]<tmp:
                Next=u
                tmp=d[Now][town[u]]
                index=j
        until.pop(index)
        Now=Next
        D+=tmp
    ans=min(ans,D)
    
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools


def warshall_floyd(G):
    import copy
    ret = copy.deepcopy(G)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                ret[i][j] = min(ret[i][j], ret[i][k] + ret[k][j])
    return ret


N, M, R = map(int, input().split())
r = list(map(int, input().split()))
G = [[10 * 10] * N for _ in range(N)]
for _ in range(M):
    A, B, C = map(int, input().split())
    G[A - 1][B - 1] = C
    G[B - 1][A - 1] = C
W, ans = warshall_floyd(G), 10 ** 10
for p in itertools.permutations(r, R):
    ans = min(ans, sum([W[p[i] - 1][p[i + 1] - 1] for i in range(R - 1)]))
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

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


def warshall_floyd(G):
    import copy
    ret = copy.deepcopy(G)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                ret[i][j] = min(ret[i][j], ret[i][k] + ret[k][j])
    return ret


r = list(map(int, input().split()))
G = [[0] * N for _ in range(N)]
for _ in range(M):
    A, B, C = map(int, input().split())
    G[A - 1][B - 1] = C
    G[B - 1][A - 1] = C
W, ans = warshall_floyd(G), 10 ** 10
for p in itertools.permutations(r, R):
    ans = min(ans, sum([W[p[i] - 1][p[i + 1] - 1] for i in range(R - 1)]))
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools


def warshall_floyd(G):
    import copy
    ret = copy.deepcopy(G)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                ret[i][j] = min(ret[i][j], ret[i][k] + ret[k][j])
    return ret


N, M, R = map(int, input().split())
r = list(map(int, input().split()))
G = [[0] * N for _ in range(N)]
for _ in range(M):
    A, B, C = map(int, input().split())
    G[A - 1][B - 1] = C
    G[B - 1][A - 1] = C
W, ans = warshall_floyd(G), 10 ** 10
for p in itertools.permutations(r, R):
    ans = min(ans, sum([W[p[i] - 1][p[i + 1] - 1] for i in range(R - 1)]))
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
import sys
input = sys.stdin.readline

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

T = [[100000] * N for _ in range(N)]

for _ in range(M):
    A, B, C = list(map(int, input().split()))
    A -= 1
    B -= 1
    T[A][B] = T[B][A] = min(C, T[A][B])
for i in range(N):
    T[i][i] = 0

# T[j][i]: cost from j to i, O(V^3)
# T[j][i] = 0 if j == i


def warshall_floyd(T, V):
    for k in range(V):
        for j in range(V):
            for i in range(V):
                T[j][i] = min(T[j][i], T[j][k] + T[k][i])


warshall_floyd(T, N)


ans = float("inf")

for v in permutations(R):
    tmp = 0
    for i in range(len(v)-1):
        tmp += T[v[i]-1][v[i+1]-1]
    ans = min(ans, tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
import sys
input = sys.stdin.readline

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

T = [[100000] * N for _ in range(N)]
for i in range(N):
    T[i][i] = 0

for _ in range(M):
    A, B, C = list(map(int, input().split()))
    A -= 1
    B -= 1
    T[A][B] = T[B][A] = min(C, T[A][B])


# T[j][i]: cost from j to i, O(V^3)
# T[j][i] = 0 if j == i
def warshall_floyd(T, V):
    for k in range(V):
        for j in range(V):
            for i in range(V):
                T[j][i] = min(T[j][i], T[j][k] + T[k][i])


warshall_floyd(T, N)


ans = 100000 * len(R)

for v in permutations(R, len(R)):
    tmp = 0
    for i in range(len(v)-1):
        tmp += T[v[i]-1][v[i+1]-1]
    ans = min(ans, tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
import sys
input = sys.stdin.readline

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

T = [[100000] * N for _ in range(N)]
for i in range(N):
    T[i][i] = 0

for _ in range(M):
    A, B, C = list(map(int, input().split()))
    A -= 1
    B -= 1
    T[A][B] = T[B][A] = C


# T[j][i]: cost from j to i, O(V^3)
# T[j][i] = 0 if j == i
def warshall_floyd(T):
    for k in range(N):
        for j in range(N):
            for i in range(N):
                T[j][i] = min(T[j][i], T[j][k] + T[k][i])


warshall_floyd(T)


ans = 100000 * len(R)

for v in permutations(R, len(R)):
    tmp = 0
    for i in range(len(v)-1):
        tmp += T[v[i]-1][v[i+1]-1]
    ans = min(ans, tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

def warshall_floyd(g):
    for k in range(len(g)):
        for i in range(len(g)):
            for j in range(len(g)):
                graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])
    return g

n,m,r = map(int,input().split())
lst = list(map(int,input().split()))
graph = [[0]*n for _ in range(n)]
for _ in range(m):
    a,b,c = map(int,input().split())
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c
d = warshall_floyd(graph)
res = float('inf')

for l in itertools.permutations(lst):
    cnt = 0
    for i in range(1, len(l)):
        cnt += d[lst[i-1]-1][lst[i]-1]
    res = min(res, cnt)
print(res)

Submission status: Wrong Answer

Solution code:
n, m, r = map(int, input().split())
d = [[float('inf')]*n for _ in range(n)]
rs = list(map(int, input().split()))
for _ in range(m):
  a, b, t = map(int, input().split())
  a -= 1
  b -= 1
  d[a][b] = t
  d[b][a] = t
for i in range(n):
  d[i][i] = 0

def warshall_floyd(d):
  #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 

d = warshall_floyd(d)

ans = float('inf')
for i in range(n):
  tmp = 0
  for r in rs:
    tmp += d[i][r-1]
  ans = min(ans, tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
for i in range(R):
    r[i] -= 1
edge = [[] for i in range(N)]
for i in range(M):
    x, y, z = map(int, input().split())
    edge[x-1].append((z, y-1))
    edge[y-1].append((z, x-1))

MIN = 10**10
for i in range(R):
    ans = 0
    d = [float("inf")] * N
    used = [True] * N
    place = set(r)
    place.remove(r[i])
    d[r[i]] = 0
    used[r[i]] = False
    edgelist = []

    for e in edge[r[i]]:
        heapq.heappush(edgelist, e)

    while place != set():
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        if v in place:
            place.remove(v)
            ans += d[v]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist, (e[0]+d[v], e[1]))
    MIN = min(ans, MIN)
    
print(MIN)

Submission status: Wrong Answer

Solution code:
from itertools import permutations

n, m, r = map(int, input().split())
A = list(map(int, input().split()))
d = [[1e9]*n for i in range(n)]
for i in range(m):
        a, b, c = map(int, input().split())
        d[a-1][b-1] = d[b-1][a-1] = c

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


ans = 1e11
for x in permutations(A):
        l = 0
        for i in range(r-1):
                l += d[x[i]-1][x[i+1]-1]
        ans = min(ans, l)
print(ans)

Submission status: Wrong Answer

Solution code:
# Author: cr4zjh0bp
# Created: Tue Mar 17 19:50:06 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from itertools import permutations

n, m, R = na()
r = na()
abc = nan(m)
adj = [[0] * n for _ in range(n)]
for i in range(m):
    a, b, c = abc[i]
    a -= 1
    b -= 1
    adj[a][b] = c

dist = [[inf] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if i == j:
            dist[i][j] = 0
        elif adj[i][j]:
            dist[i][j] = adj[i][j]

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

ans = inf
for p in permutations(r):
    res = 0
    for i in range(R - 1):
        f, t = p[i] - 1, p[i + 1] - 1
        res += dist[f][t]
    ans = min(ans, res)

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations as perm

n, m, r = map(int, input().split())
r = list(map(lambda x: int(x) - 1, input().split()))
d = [[10 ** 6] * n for _ in range(n)]
for i in range(m):
    abc = tuple(map(int, input().split()))
    a = abc[0] - 1
    b = abc[1] - 1
    c = abc[2]
    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])
            d[j][i] = d[i][j]

ans = 10 ** 9
for arr in perm(r):
    rep = 0
    for i in range(len(arr) - 1):
        rep += d[arr[i]][arr[i + 1]]
    ans = min(ans, rep)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations as perm

n, m, r = map(int, input().split())
r = list(map(lambda x: int(x) - 1, input().split()))
d = [[10 ** 5 + 1] * n for _ in range(n)]
for i in range(m):
    abc = tuple(map(int, input().split()))
    a = abc[0] - 1
    b = abc[1] - 1
    c = abc[2]
    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])
            d[j][i] = d[i][j]

ans = 10 ** 9
for arr in perm(r):
    rep = 0
    for i in range(len(arr) - 1):
        rep += d[arr[i]][arr[i + 1]]
    ans = min(ans, rep)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations as perm

n, m, r = map(int, input().split())
r = list(map(lambda x: int(x) - 1, input().split()))
d = [[10 ** 5] * n for _ in range(n)]
for i in range(m):
    abc = tuple(map(int, input().split()))
    a = abc[0] - 1
    b = abc[1] - 1
    c = abc[2]
    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])
            d[j][i] = d[i][j]

ans = 10 ** 9
for arr in perm(r, len(r)):
    rep = 0
    for i in range(len(arr) - 1):
        rep += d[arr[i]][arr[i + 1]]
    ans = min(ans, rep)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations as perm

n, m, r = map(int, input().split())
r = list(map(lambda x: int(x) - 1, input().split()))
d = [[10 ** 5] * n for _ in range(n)]
for i in range(m):
    abc = tuple(map(int, input().split()))
    a = abc[0] - 1
    b = abc[1] - 1
    c = abc[2]
    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])
            d[j][i] = d[i][j]

ans = 8 * (10 ** 5)
for arr in perm(r, len(r)):
    rep = 0
    for i in range(len(arr) - 1):
        rep += d[arr[i]][arr[i + 1]]
    ans = min(ans, rep)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
N, M, R, *L = map(int, open(0).read().split())
city = L[:R]
inf = L[R:]
dist = [[10**10]*N for i in range(N)]
for x,y,c in zip(*[iter(inf)]*3):
  dist[x-1][y-1] = c
  dist[y-1][x-1] = c
for i in range(N):
  dist[i][i] = 0

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

ans = 10**10
for m in permutations(city):
  n = 0
  for i in range(R-1):
    n += dist[m[i]-1][m[i+1]-1]
  ans = min(ans,n)
  print(n,m)
print(ans)

Submission status: Wrong Answer

Solution code:
from subprocess import call
call(('pypy3','-c',"""N,M,R=map(int,input().split())
r=list(map(int,input().split()))
A=[list(map(int,input().split())) for i in range(M)]
d=[[float("inf")]*N for i in range(N)]

for a,b,c in A:
  d[a-1][b-1]=c
  d[b-1][a-1]=c 
  
for k in range(N):
  for i in range(N):
    for j in range(N):
      d[i][j]=min(d[i][j],d[i][k]+d[k][j])
      
import itertools 
ans=10**5*8
for i in itertools.permutations(range(R),R):
  D=0
  for j in range(R-1):
    D+=d[r[i[j]]-1][r[i[j+1]]-1]
  ans=min(D,ans)
print(ans)
"""))

Submission status: Wrong Answer

Solution code:
n, m, R = map(int, input().split())
r = tuple(map(int, input().split()))
inf = 10**10
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append([b, c])
    graph[b].append([a, c])


def dfs(visited, r_num, length):
    if r_num == R:
        return length
    now = visited[-1]
    ret = []
    for i, v in graph[now]:
        if i in visited:
            continue
        if i in r:
            ret.append(dfs(visited + [i], r_num + 1, length + v))
            continue
        ret.append(dfs(visited + [i], r_num, length + v))

    if not ret:
        return inf

    return min(ret)


ans = inf
for start in range(1, n+1):
    if start in r:
        ans = min(ans, dfs([start], 1, 0))
    else:
        ans = min(ans, dfs([start], 0, 0))
print(ans)

Submission status: Wrong Answer

Solution code:
n, m, R = map(int, input().split())
r = tuple(map(int, input().split()))
inf = 10**10
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append([b, c])
    graph[b].append([a, c])


def dfs(visited, r_num, length):
    if r_num == R:
        return length
    now = visited[-1]
    ret = []
    for i, v in graph[now]:
        if i in visited:
            continue
        if i in r:
            ret.append(dfs(visited + [i], r_num + 1, length + v))
            continue
        ret.append(dfs(visited + [i], r_num, length + v))

    if not ret:
        return inf

    return min(ret)


ans = inf
for start in range(1, n+1):
    ans = min(ans, dfs([start], 1, 0))
print(ans)

Submission status: Wrong Answer

Solution code:
n, m, R = map(int, input().split())
r = list(map(int, input().split()))
inf = 10**10
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append([b, c])
    graph[b].append([a, c])


def dfs(visited, r_num, length):
    if r_num == R:
        return length
    now = visited[-1]
    ret = []
    for i, v in graph[now]:
        if i in visited:
            continue

        if i in r:
            ret.append(dfs(visited + [i], r_num + 1, length + v))
            continue
        ret.append(dfs(visited + [i], r_num, length + v))

    if not ret:
        return inf

    return min(ret)


ans = inf
for start in r:
    ans = min(ans, dfs([start], 1, 0))
print(ans)

Submission status: Wrong Answer

Solution code:
n, m, R = map(int, input().split())
r = list(map(int, input().split()))
inf = 10**10
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append([b, c])
    graph[b].append([a, c])


def dfs(visited, r_num, length):
    if r_num == len(r):
        return length
    now = visited[-1]
    ret = []
    for i, v in graph[now]:
        if i in visited:
            continue

        if i in r:
            ret.append(dfs(visited + [i], r_num + 1, length + v))
            continue
        ret.append(dfs(visited + [i], r_num, length + v))

    if not ret:
        return inf

    return min(ret)


ans = inf
for start in r:
    ans = min(ans, dfs([start], 1, 0))
print(ans)

Submission status: Wrong Answer

Solution code:
n, m, R = map(int, input().split())
r = list(map(int, input().split()))
graph = [[] for _ in range(n+1)]
inf = 10**8
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append([b, c])
    graph[b].append([a, c])


def dfs(visited, r_num, length):
    if r_num == len(r):
        return length
    now = visited[-1]
    ret = []
    for i, v in graph[now]:
        if i in visited:
            pass
        else:
            if i in r:
                ret.append(dfs(visited + [i], r_num + 1, length + v))
            else:
                ret.append(dfs(visited + [i], r_num, length + v))
    if not ret:
        return inf

    return min(ret)


ans = inf
for start in r:
    ans = min(ans, dfs([start], 1, 0))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, csgraph_from_dense
import itertools

input = sys.stdin.readline


def main():
    N, M, R = [int(x) for x in input().split()]
    r = [int(x) - 1 for x in input().split()]
    ABC = [[int(x) for x in input().split()] for _ in range(M)]

    EDGE = [[10 ** 9] * N for j in range(N)]

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

    G = csgraph_from_dense(EDGE, null_value=10 ** 9)

    d = floyd_warshall(G)

    ans = float("inf")
    c = r[0]
    for a in itertools.permutations(r[1:]):
        tmp = 0
        for n in a:
            tmp += int(d[c][n])
            c = n
        ans = min(ans, tmp)
        c = r[0]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

#保存
import heapq
import sys
import itertools
 
sys.setrecursionlimit(10**7)

def bfs(cost,node):
    root[node]=min(root[node],cost)
    for next_c,next_n in way[node]:
        if root[next_n]==10**9:
            heapq.heappush(q,[cost+next_c,next_n])
    return
    
N,M,R=map(int,input().split())
r=list(map(int,input().split()))

way=[[] for i in range(N)]

for _ in range(M):
    A,B,C=map(int,input().split())
    way[A-1].append([C,B-1])
    way[B-1].append([C,A-1])

root=[10**9]*N

q=[[0,0]]
heapq.heapify(q)#costとnode

#print(q)
while q:
    temp=heapq.heappop(q)
    #print(temp)
    bfs(temp[0],temp[1])

print(root)

ans=10**9
for order in itertools.permutations(r):
    temp=0
    for i in range(len(order)-1):
        #print("YES")
        #print(order[i]-1,order[i+1]-1)
        #print(root[order[i]-1][0])
        temp+=abs(root[order[i+1]-1]-root[order[i]-1])
    ans=min(ans,temp)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations


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


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

d = warshall_floyd(d, N)

ans = float('inf')
for p in permutations(r):
    total = 0
    for i in range(1, len(p)):
        total += d[p[i-1]-1][p[i]-1]
    ans = min(ans, total)
print(ans)

Submission status: Wrong Answer

Solution code:
def warshall_floyd(d):
    #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
 
##############################
n,w,r = map(int,input().split()) #n:頂点数　w:辺の数
t = list(map(int,input().split()))
 
d = [[float("inf")]*n for i in range(n)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(w):
    x,y,z = map(int,input().split())
    d[x-1][y-1] = z
    d[y-1][x-1] = z
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
res = warshall_floyd(d)
 
print(max([res[t[0]-1][i-1] for i in t]))

Submission status: Wrong Answer

Solution code:
N,M,R=map(int, input().split())
r=list(map(int, input().split()))
dp=[[10**9]*N for _ in range(N)]
for _ in range(M):
    A,B,C=map(int, input().split())
    A-=1
    B-=1
    dp[A][B]=C
    dp[B][A]=C
for z in range(N):
    for x in range(N):
        for y in range(N):
            dp[x][y]=min(dp[x][y], dp[x][z]+dp[z][y])

import itertools
ans=10**9
for p in itertools.permutations(range(R)):
    t=0
    for i in range(R-1):
        t+=dp[p[i]-1][p[i+1]-1]
    ans=min(ans,t)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n,m,r = map(int,readline().split())

lst1 = [[float("inf")]*n for _ in range(n)]

lst2 = list(map(int,readline().split()))
for i in range(len(lst2)):
    lst2[i] -= 1

for i in range(m):
    x,y,w = map(int,readline().split())
    lst1[x-1][y-1] = w
    lst1[y-1][x-1] = w

def warshall_floyd(d): #隣接行列を入れる
    #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

lst1 = warshall_floyd(lst1)

ans = 10**12
for i in list(itertools.permutations(lst2)):
    res = 0
    before = i[0]
    for j in i[1:]:
        res += lst1[before][j]

    ans = min(res,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n,m,r = map(int,readline().split())

lst1 = [[float("inf")]*n for _ in range(n)]

lst2 = list(map(int,readline().split()))
for i in range(len(lst2)):
    lst2[i] -= 1

for i in range(m):
    x,y,w = map(int,readline().split())
    lst1[x-1][y-1] = w
    lst1[y-1][x-1] = w

def warshall_floyd(d): #隣接行列を入れる
    #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

lst1 = warshall_floyd(lst1)

ans = 10**9
for i in list(itertools.permutations(lst2)):
    res = 0
    before = i[0]
    for j in i[1:]:
        res += lst1[before][j]

    ans = min(res,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
from scipy.sparse.csgraph import floyd_warshall
n,m,r=map(int,input().split())
vis=list(map(int,input().split()))
INF=10**6
path=[[INF]*n for i in range(n)]
for i in range(m):
  a,b,c=map(int,input().split())
  path[a-1][b-1]=c
  path[b-1][a-1]=c
path=floyd_warshall(path)
ans=10**9
for root in permutations(vis):
  cnt=0
  for j in range(1,r):
    cnt+=path[root[j-1]-1][root[j]-1]
  ans=min(ans,cnt)
print(int(ans))

Submission status: Wrong Answer

Solution code:
from itertools import permutations
from scipy.sparse.csgraph import floyd_warshall
def warshallFloyd():
    for i in range(N):
        for j in range(N):
            if dp[j][i] == INF: continue
            for k in range(N):
                if dp[i][k] == INF: continue
                dp[j][k] = min(dp[j][k], dp[j][i] + dp[i][k])
    return

INF = 10 ** 18
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
dp = [[INF for _ in range(N)] for _ in range(N)]
ansF = False
for i in range(N):
    for j in range(N):
        if i == j:
            dp[i][j] = 0

for i in range(M):
    a, b, c = map(int, input().split())
    dp[a - 1][b - 1] = c
    dp[b - 1][a - 1] = c

wf = floyd_warshall(dp)
ans = INF
for i in permutations(r):
    tmp = 0
    for j in range(1, len(i)):
        tmp += wf[i[j - 1] - 1][i[j] - 1]
    ans = min(ans, tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
m = [[10**5+1]*N for i in range(N)]

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

for i in range(N):
  m[i][i] = 0

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

ans = 10**10
for l in itertools.permutations(r):
  cost = 0
  for i in range(1, R):
    cost += m[l[i-1]-1][l[i]-1]
  ans = min(ans, cost)

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
m = [[10**5+1]*N for i in range(N)]

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

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

ans = float("inf")
for l in itertools.permutations(r):
  tans = 0
  for i in range(1, R):
    tans += m[l[i-1]-1][l[i]-1]
  ans = min(ans, tans)

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
m = [[10**5+1]*N for i in range(N)]

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

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

ans = 10**10
for l in itertools.permutations(r):
  tans = 0
  for i in range(1, R):
    tans += m[l[i-1]-1][l[i]-1]
  ans = min(ans, tans)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import *
from itertools import *
import copy
from heapq import *


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

data=[[] for i in range(N+1)]
nagasa={}
for a,b,c in ABC:
    data[a].append(b)
    data[b].append(a)
    A,B=min(a,b),max(a,b)
    nagasa.update({str(A)+" "+str(B):c})
mokutekiti=[[100000*200+1 for i in range(R)] for m in range(R)]
for r1i in range(R-1):
    for r2i in range(r1i+1,R):
        r1=Rlst[r1i]
        r2=Rlst[r2i]
        visited=set([r1])
        stack=[0]
        heapify(stack)
        dic={0:[r1]}
        while stack:
            m=heappop(stack)
            #if not m in visited:
            #visited.add(m)
            a=dic[m].pop()
            if not a in visited:
                visited.add(a)
                for b in data[a]:
                    if not b in visited or b==r2:
                        A,B=min(a,b),max(a,b)
                        tempm=m+nagasa[str(A)+" "+str(B)]
                        if b==r2:
                            if mokutekiti[r1i][r2i]>tempm:
                                mokutekiti[r1i][r2i]=tempm
                                mokutekiti[r2i][r1i]=tempm
                        else:
                            heappush(stack,tempm)
                            if tempm in dic:
                                dic[tempm].append(b)
                            else:
                                dic.update({tempm:[b]})



value=[]
for lst in permutations([i for i in range(R)],R):
    nagasa=0
    for i in range(R-1):
        nagasa+=mokutekiti[lst[i]][lst[i+1]]
    value.append(nagasa)
print(min(value))