Problem:


Score : 400 points

Problem Statement

There are N towns in the State of Atcoder, connected by M bidirectional roads.

The i-th road connects Town A_i and B_i and has a length of C_i.

Joisino is visiting R towns in the state, r_1,r_2,..,r_R (not necessarily in this order).

She will fly to the first town she visits, and fly back from the last town she visits, but for the rest of the trip she will have to travel by road.

If she visits the towns in the order that minimizes the distance traveled by road, what will that distance be?

Constraints

2≤N≤200

1≤M≤N×(N-1)/2

2≤R≤min(8,N) (min(8,N) is the smaller of 8 and N.)

r_i≠r_j (i≠j)

1≤A_i,B_i≤N, A_i≠B_i

(A_i,B_i)≠(A_j,B_j),(A_i,B_i)≠(B_j,A_j) (i≠j)

1≤C_i≤100000

Every town can be reached from every town by road.

All input values are integers.

Input

Input is given from Standard Input in the following format:

N M R
r_1 ... r_R
A_1 B_1 C_1
:
A_M B_M C_M

Output

Print the distance traveled by road if Joisino visits the towns in the order that minimizes it.

Sample Input 1

3 3 3
1 2 3
1 2 1
2 3 1
3 1 4

Sample Output 1

2

For example, if she visits the towns in the order of 1, 2, 3, the distance traveled will be 2, which is the minimum possible.

Sample Input 2

3 3 2
1 3
2 3 2
1 3 6
1 2 2

Sample Output 2

4

The shortest distance between Towns 1 and 3 is 4. Thus, whether she visits Town 1 or 3 first, the distance traveled will be 4.

Sample Input 3

4 6 3
2 3 4
1 2 4
2 3 3
4 3 1
1 4 1
4 2 2
3 1 6

Sample Output 3

3



Sample input:
3 3 3
1 2 3
1 2 1
2 3 1
3 1 4


Sample output:
2

Submission status: Wrong Answer

Solution code:
import itertools
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson

N,M,R = map(int, input().split())
r_list = np.array(list(map(int, input().split()))) -1 

nodes = np.full((N,N), np.inf) 
for i in range(M):
    a,b,c = map(int, input().split())
    nodes[a-1,b-1] = nodes[b-1,a-1] = c
print(nodes)
min_ds = shortest_path(nodes)
res = 10**9
for cmb in itertools.permutations(r_list):
    prev = cmb[0]
    tmpres = 0
    for to in cmb[1:]:
        tmpres += min_ds[prev,to]
        prev = to
    res = min(res, tmpres)

print(int(res))

Submission status: Wrong Answer

Solution code:
import itertools
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson

N,M,R = map(int, input().split())
r_list = np.array(list(map(int, input().split()))) -1 

nodes = np.full((N,N), np.inf) 
for i in range(M):
    a,b,c = map(int, input().split())
    nodes[a-1,b-1] = nodes[b-1,a-1] = c

min_ds = shortest_path(nodes)
res = 10*9
for cmb in itertools.permutations(r_list):
    prev = cmb[0]
    tmpres = 0
    for to in cmb[1:]:
        tmpres += min_ds[prev,to]
        prev = to
    res = min(res, tmpres)

print(int(res))

Submission status: Wrong Answer

Solution code:
import itertools
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson

N,M,R = map(int, input().split())
r_list = np.array(list(map(int, input().split()))) -1 

nodes = np.zeros((N,N), dtype=np.int64)
for i in range(M):
    a,b,c = map(int, input().split())
    nodes[a-1,b-1] = nodes[b-1,a-1] = c

min_ds = shortest_path(nodes)
res = 10*9
for cmb in itertools.permutations(r_list):
    prev = cmb[0]
    tmpres = 0
    for to in cmb[1:]:
        tmpres += min_ds[prev,to]
        prev = to
    res = min(res, tmpres)

print(int(res))

Submission status: Wrong Answer

Solution code:
import itertools
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
N,M,R = map(int, input().split())
r_list = np.array(list(map(int, input().split()))) -1 

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

min_ds = shortest_path(nodes)
res = 10*9
for cmb in itertools.permutations(r_list):
    prev = cmb[0]
    tmpres = 0
    for to in cmb[1:]:
        tmpres += min_ds[prev,to]
        prev = to
    res = min(res, tmpres)
print(int(res))

Submission status: Wrong Answer

Solution code:
INF=10**18
def rec(bit,v):
  if dp[bit][v]!=-1:return dp[bit][v]
  if bit==(1<<r)-1:
    dp[bit][v]=0
    return dp[bit][v]
  res=INF
  for u in range(r):
    if not ((bit>>u) & 1):
      res=min(res,rec(bit|1<<u,u)+dist[u][v])
  dp[bit][v]=res
  return dp[bit][v]

n,m,r=map(int,input().split())
dist_n=[[INF for _ in range(n+1)]for _ in range(n+1)]
dp=[[-1 for _ in range(r+1)]for _ in  range((1<<r)+1)]
r_t=list(map(int,input().split()))
for i in range(n+1):
  dist_n[i][i]=0
for _ in range(m):
  a,b,c=map(int,input().split())
  dist_n[a][b]=c
  dist_n[b][a]=c
for k in range(n+1):
  for i in range(n+1):
    for j in range(n+1):
      dist_n[i][j]=min(dist_n[i][j],dist_n[i][k]+dist_n[k][j])
dist=[[0 for _ in range(r)]for _ in range(r)]
for i in range(r):
  for j in range(r):
    dist[i][j]=dist_n[r_t[i]][r_t[j]]
res=INF
for v in range(r):
  res=min(res,rec((1<<v)-1,v))
print(rec(0,0))

Submission status: Wrong Answer

Solution code:
INF=10**18
def rec(bit,v):
  if dp[bit][v]!=-1:return dp[bit][v]
  if bit==(1<<r)-1:
    dp[bit][v]=0
    return dp[bit][v]
  res=INF
  for u in range(r):
    if not ((bit>>u) & 1):
      res=min(res,rec(bit|1<<u,u)+dist[u][v])
  dp[bit][v]=res
  return dp[bit][v]

n,m,r=map(int,input().split())
dist_n=[[INF for _ in range(n+1)]for _ in range(n+1)]
dp=[[-1 for _ in range(r+1)]for _ in  range((1<<r)+1)]
r_t=list(map(int,input().split()))
for i in range(n):
  dist_n[i][i]=0
for _ in range(m):
  a,b,c=map(int,input().split())
  dist_n[a][b]=c
  dist_n[b][a]=c
for k in range(n+1):
  for i in range(n+1):
    for j in range(n+1):
      dist_n[i][j]=min(dist_n[i][j],dist_n[i][k]+dist_n[k][j])
dist=[[0 for _ in range(r)]for _ in range(r)]
for i in range(r):
  for j in range(r):
    dist[i][j]=dist_n[r_t[i]][r_t[j]]
res=INF
for v in range(r):
  res=min(res,rec((1<<v)-1,v))
print(rec(0,0))

Submission status: Wrong Answer

Solution code:
INF=10**18
def rec(bit,v):
  if dp[bit][v]!=-1:return dp[bit][v]
  if bit==(1<<r)-1:
    dp[bit][v]=0
    return dp[bit][v]
  res=INF
  for u in range(r):
    if not ((bit>>u) & 1):
      res=min(res,rec(bit|1<<u,u)+dist[r_t[u]][r_t[v]])
  dp[bit][v]=res
  return dp[bit][v]

n,m,r=map(int,input().split())
dist=[[INF for _ in range(n+1)]for _ in range(n+1)]
dp=[[-1 for _ in range(r+1)]for _ in  range((1<<r)+1)]
r_t=list(map(int,input().split()))
for i in range(n):
  dist[i][i]=0
for _ in range(m):
  a,b,c=map(int,input().split())
  dist[a][b]=c
  dist[b][a]=c
for k in range(n+1):
  for i in range(n+1):
    for j in range(n+1):
      dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])
res=INF
for v in range(r):
  res=min(res,rec((1<<v)-1,v))
print(rec(0,0))

Submission status: Wrong Answer

Solution code:
n, m, r = map(int, input().split())
R = tuple(map(lambda x: int(x), input().split()))
INF = 10**9
dp = [[INF]*(n+1) for _ in range(n+1)]

for _ in range(m):
    a, b, c = map(int, input().split())

    dp[a][b] = c
    dp[b][a] = c

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

from itertools import permutations
ans = INF
for p in permutations(R):
    dist = 0
    for i in range(r-1):
        dist += dp[p[i]][p[i+1]]
    ans = min(ans, dist)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

INF = 10**10
N, M, R = map(int, input().split())
*r, = map(int, input().split())
r = [v-1 for v in r]

g = [[INF]*N for _ in range(N)]
for i in range(N):
    g[i][i] = 0

for m 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):
    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 rs in itertools.permutations(r):
    cost = 0
    for i in range(len(rs)-1):
        cost += g[rs[i]][rs[i+1]]
    if cost < ans:
        ans = cost

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools


N, M, R = map(int, input().split())
*r, = map(int, input().split())
r = [v-1 for v in r]

g = [[float('inf') for __ in range(N)] for _ in range(N)]
for i in range(N):
    g[i][i] = 0

for m 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):
    for j in range(N):
        for k in range(N):
            g[i][j] = min(g[i][j], g[i][k]+g[k][j])

ans = float('inf')
for rs in itertools.permutations(r):
    cost = 0
    for i in range(len(rs)-1):
        cost += g[rs[i]][rs[i+1]]
    if cost < ans:
        ans = cost

print(ans)

Submission status: Wrong Answer

Solution code:
N,M,r = map(int,input().split())
R = list(map(int,input().split()))
g = [[float('inf ')]*(N+1) for _ in range(N+1)]
for i in range(N+1):
    g[i][i] = 0
for _ in range(M):
    a,b,c = map(int,input().split())
    g[a][b]=c
    g[b][a]=c
for i in range(1,N+1):
    for j in range(1,N+1):
        for k in range(1,N+1):
            g[i][j] = min(g[i][j],g[i][k]+g[k][j])
from itertools import permutations
ans = float('inf')
for li in permutations(R):
    li = list(li)
    tmp=0
    for i in range(len(li)-1):
        tmp += g[li[i]][li[i+1]]
    ans = min(ans,tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
N,M,r = map(int,input().split())
R = list(map(int,input().split()))
g = [[float('inf ')]*(N+1) for _ in range(N+1)]
for i in range(N+1):
    g[i][i] = 0
for _ in range(M):
    a,b,c = map(int,input().split())
    g[a][b]=c
    g[b][a]=c
for i in range(N+1):
    for j in range(N+1):
        for k in range(N+1):
            g[i][j] = min(g[i][j],g[i][k]+g[k][j])
from itertools import permutations
ans = float('inf')
for li in permutations(R):
    li = list(li)
    tmp=0
    for i in range(len(li)-1):
        tmp += g[li[i]][li[i+1]]
    ans = min(ans,tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools


N, M, R = map(int, input().split())
*r, = map(int, input().split())
r = [v-1 for v in r]

g = [[float('inf')]*N for _ in range(N)]
for i in range(N):
    g[i][i] = 0

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

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 = float('inf')
for rs in itertools.permutations(r, R):
    cost = 0
    for i in range(R-1):
        cost += g[rs[i]][rs[i+1]]
    if cost < ans:
        ans = cost

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools


def FloydWarshall(n, dp):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])
    return dp


N, M, R = map(int, input().split())
*r, = map(int, input().split())
r = [v-1 for v in r]

g = [[10**10]*N for _ in range(N)]
for i in range(N):
    g[i][i] = 0

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

FloydWarshall(N, g)

ans = 10**10
for rs in itertools.permutations(r, R):
    cost = 0
    for i in range(R-1):
        cost += g[rs[i]][rs[i+1]]
    if cost < ans:
        ans = cost

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools


def FloydWarshall(n, dp):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])
    return dp


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

g = [[float('inf')]*N for _ in range(N)]
for i in range(N):
    g[i][i] = 0

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

FloydWarshall(N, g)

ans = float('inf')
for rs in itertools.permutations(r, len(r)):
    cost = 0
    for i in range(len(r)-1):
        a, b = rs[i]-1, rs[i+1]-1
        cost += g[a][b]
    if cost < ans:
        ans = cost

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools


def FloydWarshall(n, dp):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])
    return dp


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

g = [[float('inf')]*N for _ in range(N)]
for m in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    g[a][b] = c
    g[b][a] = c

FloydWarshall(N, g)

ans = float('inf')
for rs in itertools.permutations(r, len(r)):
    cost = 0
    for i in range(len(r)-1):
        a, b = rs[i]-1, rs[i+1]-1
        cost += g[a][b]
    if cost < ans:
        ans = cost
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

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

# Warshall-Floyd
for k in range(N):
    for i in range(N):
        for j in range(N):
            A[i][j] = min(A[i][j], A[i][k] + A[k][j])

res = 1000000000
for perm in itertools.permutations([x-1 for x in r]):
    cost = 0
    for i in range(R-1):
        cost += A[perm[i]][perm[i+1]]
    if cost < res:
        res = cost

print(res)

Submission status: Wrong Answer

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

for i in range(n):
    d[i][i] = 0

def warshall_floyd(d):
    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 = 0
visited = [rs[-1]]
rs.pop()
while rs:
    dmin = float('inf')
    for i in visited:
        for j in rs:
            if d[i][j] < dmin:
                index = j
                dmin = d[i][j]
    ans += dmin
    rs.remove(index)
    visited.append(index)
print(ans)

Submission status: Wrong Answer

Solution code:
N,M,R = map(int,input().split())
R = list(map(int,input().split()))
dp = [[float("INF")]*(N+1) for _ in range(N+1)]
for i in range(N+1):
    dp[i][i] = 0

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

for i in range(1,N+1):
    for j in range(1,N+1):
        for k in range(1,N+1):
            dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j])
#dp[j][i],dp[i][k]が最適に更新されていないタイミングで回しても意味なくね？


candidate = []
def dfs (r,cost,path=set()):
    path.add(r)
    if len(path) == len(R):
        candidate.append(cost)
    else:
        for nx in R:
            if nx not in path:
                dfs(nx,cost+dp[r][nx],path)
    path.remove(r)

for r in R:
    dfs(r,0)
print(min(candidate))

Submission status: Wrong Answer

Solution code:
N,M,R = map(int,input().split())
R = list(map(int,input().split()))
dp = [[float("INF")]*(N+1) for _ in range(N+1)]
for i in range(N+1):
    dp[i][i] = 0

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

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

candidate = []
def dfs (r,cost,path=set()):
    path.add(r)
    if len(path) == len(R):
        candidate.append(cost)
    else:
        for nx in R:
            if nx not in path:
                dfs(nx,cost+dp[r][nx],path)
    path.remove(r)

for r in R:
    dfs(r,0)
print(min(candidate))

Submission status: Wrong Answer

Solution code:
def main():
    from itertools import permutations

    n, m, r, *x = map(int, open(0).read().split())
    to = x[:r]

    dis = [[10 ** 7] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        dis[i][i] = 0

    for a, b, c in zip(*[iter(x[r:])] * 3):
        dis[a][b] = c
        dis[b][a] = c

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

    ans = 10 ** 7
    for p in permutations(to):
        tmp = 0
        nw = p[0]
        for nx in p[1:]:
            tmp += dis[nw][nx]
            nw = nx

        ans = min(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    from itertools import permutations

    n, m, r, *x = map(int, open(0).read().split())
    to = x[:r]

    dis = [[10 ** 6 * r + 1] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        dis[i][i] = 0

    for a, b, c in zip(*[iter(x[r:])] * 3):
        dis[a][b] = c
        dis[b][a] = c

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

    ans = 10 ** 6 * r + 1
    for p in permutations(to):
        tmp = 0
        nw = p[0]
        for nx in p[1:]:
            tmp += dis[nw][nx]
            nw = nx

        ans = min(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from itertools import permutations
MAX = 10 ** 9
def warshall_floyd(n, dist):
    for k in range(n):
        for i in range(n-1):
            for j in range(i, n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
E = [[MAX] * N for _ in range(N)]
for i in range(N):
    E[i][i] = 0
for i in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    E[a][b] = c
    E[b][a] = c
E = warshall_floyd(N, E)
res = MAX
for p in permutations(r):
    tmp = 0
    for i in range(R-1):
        tmp += E[p[i]-1][p[i+1]-1]
    res = min(res, tmp)
print(res)

Submission status: Wrong Answer

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


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')

from itertools import permutations

def main():
	n,m,R=MI()
	r=LI()

	G=[[10**9]*(n+1) for _ in range(n+1)]
	for i in range(n+1):
		G[i][i]=0



	for _ in range(m):
		a,b,c=MI()
		G[a][b]=min(G[a][b],c)
		G[b][a]=min(G[b][a],c)
	#print(G)

	for i in range(n+1):
		for j in range(n+1):
			for k in range(n+1):
				G[i][j]=min(G[i][j],G[i][k]+G[k][j])
	#print(G)

	ans=10**9
	for i in permutations(r,R):
		#print(i)
		ret=0
		for j in range(R-1):
			ret+=G[i[j]][i[j+1]]
		#print(ret)
		ans=min(ans,ret)
	print(ans)





if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')

from itertools import permutations

def main():
	n,m,R=MI()
	r=LI()

	G=[[10**9]*(n+1) for _ in range(n+1)]
	for _ in range(m):
		a,b,c=MI()
		G[a][b]=c
		G[b][a]=c
	#print(G)

	for i in range(n+1):
		for j in range(n+1):
			for k in range(n+1):
				G[i][j]=min(G[i][j],G[i][k]+G[k][j])
	#print(G)

	ans=10**9
	for i in permutations(r,R):
		#print(i)
		ret=0
		for j in range(R-1):
			ret+=G[i[j]][i[j+1]]
		ans=min(ans,ret)
	print(ans)





if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

d = [[10**7 for j in range(n)] for i in range(n)]
for i in range(m):
  a, b, c = map(int, input().split())
  a -= 1
  b -= 1
  d[a][b] = c
  d[b][a] = c

for i in range(n):
  d[i][i] = 0

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

# print (d)
ans = 10**7
for i in itertools.permutations(r):
  x = i
  k = 0
  for j in range(R-1):
    a,b = x[j+1],x[j]
    a -= 1
    b -= 1
    k += d[b][a]
  ans = min(ans,k)
print (ans)

Submission status: Wrong Answer

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

d = [[10**7 for j in range(n)] for i in range(n)]
for i in range(m):
  a, b, c = map(int, input().split())
  a -= 1
  b -= 1
  d[a][b] = c
  d[b][a] = c

for i in range(n):
  d[i][i] = 0

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

# print (d)
ans = 10**7
for i in itertools.permutations(r):
  x = i
  k = 0
  for j in range(R-1):
    a,b = x[j+1],x[j]
    a -= 1
    b -= 1
    k += d[a][b]
  ans = min(ans,k)
print (ans)

Submission status: Wrong Answer

Solution code:
import heapq

def dijkstra(N, G, s):
    INF = 10**40
    d = [INF] * N
    d[s] = 0
    q = [(0, s)]
    while q:
        c, v = heapq.heappop(q)
        if d[v] < c:
            continue
        for t, co in G[v]:
            if d[v] + co < d[t]:
                d[t] = d[v] + co
                heapq.heappush(q, (d[t], t))
    return d


def main():
    N, M, _ = map(int, input().split())
    R = list(map(int, input().split()))
    R = [r - 1 for r in R]
    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a - 1].append((b - 1, c))
        G[b - 1].append((a - 1, c))
    RM = []
    for r in R:
        d = dijkstra(N, G, r)
        RM.append([d[rr] for rr in R])
    INF = 10 ** 40
    dp = [INF] * (2 ** len(R))
    last = [-1] * (2 ** len(R))
    for i in range(len(R)):
        dp[1 << i] = 0
        last[1 << i] = i

    for i in range(1, 2 ** len(R)):
        if dp[i] == INF:
            continue
        for j in range(len(R)):
            if i & (1 << j):
                continue
            if dp[i | 1 << j] > dp[i] + RM[last[i]][j]:
                dp[i | 1 << j] = dp[i] + RM[last[i]][j]
                last[i | 1 << j] = j
    return dp[-1]

print(main())

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter
from collections import deque
import heapq
import math
import fractions
import bisect
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))



n,m,r=mp()
l=lmp()
d = [[float("inf")]*(n+1) for i in range(n+1)] 
for i in range(m):
    x,y,z = map(int,input().split())
    d[x][y] = z
    d[y][x] = z
for i in range(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])

ans=0
for i in range(r-1):
    ans+=d[l[i]][l[i+1]]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter
from collections import deque
import heapq
import math
import fractions
import bisect
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))



n,m,r=mp()
l=lmp()
d = [[float("inf")]*(n+1) for i in range(n+1)] 
for i in range(m):
    x,y,z = map(int,input().split())
    d[x][y] = z
    d[y][x] = z
for i in range(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=0
for i in range(r-1):
    ans+=d[l[i]][l[i+1]]
print(ans)

Submission status: Wrong Answer

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

from collections import defaultdict
V = defaultdict(list)
 
for _ in range(m):
    a, b,c = map(int, input().split())
    V[a].append([b,c])
    V[b].append([a,c])
    
def dfs(source):
    dist = [-1]*(n+1)
    dist[source] = 0
    q = [source]
    while q:
        a = q.pop()
        ii = -1
        for b in V[a]:
            ii = ii+1
            if dist[b[0]]!=-1:
                dist[b[0]] = min(dist[b[0]],dist[a] + V[a][ii][1])
                continue
            dist[b[0]] = dist[a] + V[a][ii][1]
            q.append(b[0])
    return dist
da=[]
for __ in al:
    da.append(dfs(__))

import itertools
zz = list(itertools.permutations(al))
yy = list(itertools.permutations(range(r)))

res = 10*9
for k,l in zip (zz,yy):
    temp = 0
    for m in range(r-1):
        temp += da[l[m]][(k[m+1])]
    res = min(res,temp)
print(res)

Submission status: Wrong Answer

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

from collections import defaultdict
V = defaultdict(list)
 
for _ in range(m):
    a, b,c = map(int, input().split())
    V[a].append([b,c])
    V[b].append([a,c])
    
def dfs(source):
    dist = [-1]*(n+1)
    dist[source] = 0
    q = [source]
    while q:
        a = q.pop()
        ii = -1
        for b in V[a]:
            ii = ii+1
            if dist[b[0]]!=-1:
                dist[b[0]] = min(dist[b[0]],dist[a] + V[a][ii][1])
                continue
            dist[b[0]] = dist[a] + V[a][ii][1]
            q.append(b[0])

    return dist

res = 10*9
for k in al:
    temp = 0
    for l in al:
        temp += dfs(k)[l]
    res = min(res,temp)
print(res)

Submission status: Wrong Answer

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

from collections import defaultdict
V = defaultdict(list)
 
for _ in range(m):
    a, b,c = map(int, input().split())
    V[a].append([b,c])
    V[b].append([a,c])
    
def dfs(source):
    dist = [-1]*(n+1)
    dist[source] = 0
    q = [source]
    ju = 1
    while q:
        a = q.pop()
        ii = -1
        for b in V[a]:
            ii = ii+1
            if dist[b[0]]!=-1:
                dist[b[0]] = min(dist[b[0]],dist[a] + V[a][ii][1])
                continue
            dist[b[0]] = dist[a] + V[a][ii][1]
            q.append(b[0])
        for j in range(r):
            ju *= dist[j]
    return dist

res = 10*9
for k in al:
    temp = 0
    for l in al:
        temp += dfs(k)[l]
    res = min(res,temp)
print(res)

Submission status: Wrong Answer

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

from collections import defaultdict
V = defaultdict(list)
 
for _ in range(m):
    a, b,c = map(int, input().split())
    V[a].append([b,c])
    V[b].append([a,c])
    
def dfs(source):
    dist = [-1]*(n+1)
    dist[source] = 0
    q = [source]
    ju = 1
    while q:
        a = q.pop()
        ii = -1
        for b in V[a]:
            ii = ii+1
            if dist[b[0]]!=-1:
                dist[b[0]] = min(dist[b[0]],dist[a] + V[a][ii][1])
                continue
            dist[b[0]] = dist[a] + V[a][ii][1]
            q.append(b[0])
        for j in range(r):
            ju *= dist[j]
        if ju != 0:
            break
    return dist

res = 10*9
for k in al:
    temp = 0
    for l in al:
        temp += dfs(k)[l]
    res = min(res,temp)
print(res)

Submission status: Wrong Answer

Solution code:
from itertools import groupby, accumulate, product, permutations, combinations
def solve():
    ans = float('inf')
    N, M, R = map(int, input().split())
    r = list(map(int, input().split()))
    d = [[0]*N for _ in range(N)]
    for i in range(M):
        a,b,c = map(int, input().split())
        d[a-1][b-1] = c
        d[b-1][a-1] = c
    for i in range(N):
        d[i][i] = 0 #自身への最短経路は0
    #三重ループ
    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])
    for p in permutations(r,R):
        cnt = 0
        for i in range(R-1):
            if d[p[i]-1][p[i+1]-1]>0:
                cnt += d[p[i]-1][p[i+1]-1]
            else:
                break
        else:
            ans = min(ans,cnt)
    return ans
print(solve())

Submission status: Wrong Answer

Solution code:
N,M,R= list(map(int,input().split()))
towns = list(map(int,input().split()))
for i in range(R):
    towns[i] += -1

G = [[] for i in range(N)]
for i in range(M):
    A,B,C = list(map(int,input().split()))
    G[A-1].append([C,B-1]) #重み、向かう先の順番
    G[B-1].append([C,A-1])

dists = [[100000*200]*N for i in range(R)]

import heapq

for i in range(R):
    town = towns[i]
    dist = dists[i]
    dist[town] = 0
    used = [0]*N
    used[town] = 1

    nextlist = []
    for next in G[town]:
        heapq.heappush(nextlist,next)

    while len(nextlist):
        minnext = heapq.heappop(nextlist)
        if used[minnext[1]]==1:
            continue
        v = minnext[1]
        dist[v] = minnext[0]
        used[v] = 1
        for next in G[v]:
            if used[next[1]]==0:
                heapq.heappush(nextlist,[next[0]+dist[v],next[1]])

from itertools import permutations
townorders = list(permutations(towns))

out = 100000*200
for townorder in townorders:
    cand = 0
    for i in range(R-1):
        now = townorder[i]
        nowind = towns.index(now)
        next = townorder[i+1]
        cand += dists[nowind][next]
    if cand<out:
        out=cand
print(out)

Submission status: Wrong Answer

Solution code:
from itertools import permutations

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

d = [[1000000000] * (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

result = 1000000000
for p in permutations(r):
    t = 0
    for i in range(R - 1):
        t += d[p[i]][p[i + 1]]
    result = min(result, t)
print(result)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
n,m,r = map(int,input().split())
rl = list(map(int,input().split()))
d = [[10**8]*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] = min(d[a-1][b-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])
m = 10**9
for i in permutations(rl):
  c = 0
  for j in range(1,r):
    c += d[i[j-1]-1][i[j]-1]
  m = min(m,c)
print(m)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
n,m,r = map(int,input().split())
rl = list(map(int,input().split()))
d = [[10**8]*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])
m = 10**9
for i in permutations(rl):
  c = 0
  for j in range(1,r):
    c += d[i[j-1]-1][i[j]-1]
  m = min(m,c)
print(m)