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,k1=map(int,input().split())
mat=[[10**9 for j in range(n)]for i in range(n)]
r=[int(i)-1 for i in input().split()]
for i in range(m):
    a,b,c=map(int,input().split())
    mat[a-1][b-1]=c 
    mat[b-1][a-1]=c
for i in range(n):
    mat[i][i]=0 
dp=[[10**9 for j in range(n)]for i in range(n)]
for i in range(n):
    dp[i][i]=0 
for k in range(n):
    for i in range(n):
        for j in range(n):
            if mat[k][j]==10**9:
                continue 
            dp[i][j]=min(dp[i][j],dp[i][k]+mat[k][j])
            dp[j][i]=dp[i][j]
#print(dp)\
mini=10**100 
#print(dp[2][3]+dp[3][1])
from itertools import permutations
for i in permutations(r) : 
    ans=0 
   # print(i)
    for j in range(1,k1): 
        ans+=dp[i[j-1]][i[j]]
    #print(i,ans)
    mini=min(mini,ans)
print(mini)

Submission status: Wrong Answer

Solution code:
n,m,k1=map(int,input().split())
mat=[[10**9 for j in range(n)]for i in range(n)]
r=[int(i)-1 for i in input().split()]
for i in range(m):
    a,b,c=map(int,input().split())
    mat[a-1][b-1]=c 
    mat[b-1][a-1]=c
for i in range(n):
    mat[i][i]=0 
dp=[[10**9 for j in range(n)]for i in range(n)]
for i in range(n):
    dp[i][i]=0 
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]+mat[k][j])
            dp[j][i]=dp[i][j]
#print(dp)\
mini=10**100 
#print(dp[2][3]+dp[3][1])
from itertools import permutations
for i in permutations(r) : 
    ans=0 
   # print(i)
    for j in range(1,k1): 
        ans+=dp[i[j-1]][i[j]]
    #print(i,ans)
    mini=min(mini,ans)
print(mini)

Submission status: Wrong Answer

Solution code:
import itertools
n,m,R = map(int,input().split())
r = list(map(int,input().split()))
cost = [[-1]*n for i in range(n)]
for i in range(m):
    a,b,c = map(int,input().split())
    cost[a-1][b-1] = c
    cost[b-1][a-1] = c

for k in range(n):
    for i in range(n):
        for j in range(n):
            if cost[i][k] != -1 and cost[k][j] != -1:
                cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j])

ans = -1
for p in itertools.permutations(r):
    c = 0
    for i in range(R-1):
        c += cost[p[i]-1][p[i+1]-1]
    if ans == -1:
        ans = c
    else:
        ans = min(c, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
n,m,R = map(int,input().split())
r = list(map(int,input().split()))
cost = [[1000000]*n for i in range(n)]
for i in range(m):
    a,b,c = map(int,input().split())
    cost[a-1][b-1] = c
    cost[b-1][a-1] = c

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

ans = 1000000000
for p in itertools.permutations(r):
    c = 0
    for i in range(R-1):
        c += cost[p[i]-1][p[i+1]-1]
    ans = min(c, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
n,m,R = map(int,input().split())
r = list(map(int,input().split()))
cost = [[1000000]*n for i in range(n)]
for i in range(m):
    a,b,c = map(int,input().split())
    cost[a-1][b-1] = c
    cost[b-1][a-1] = c

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

ans = 10000000
for p in itertools.permutations(r):
    c = 0
    for i in range(R-1):
        c += cost[p[i]-1][p[i+1]-1]
    ans = min(c, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
n,m,R = map(int,input().split())
r = list(map(int,input().split()))
cost = {}
for i in range(m):
  a,b,c = map(int,input().split())
  cost[(a,b)] = c

ans = 1000000
for p in itertools.permutations(r):
  c = 0
  path_exist = True
  for i in range(len(r)-1):
    if not (p[i], p[i+1]) in cost:
      path_exist = False
      break
    c += cost[(p[i], p[i+1])]
  if path_exist:
    ans = min(c, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
# ABC073D - joisino's travel
from heapq import heapify, heappop, heappush
from itertools import permutations


def dijkstra(G: "Array[Array[int]]", size: int, start: int) -> list:
    dist = [float("inf")] * size
    searched = [0] * size
    queue = [(start, 0)]
    heapify(queue)
    while queue:
        v, cost = heappop(queue)
        if searched[v] or cost > dist[v]:
            continue
        dist[v] = cost
        searched[v] = 1
        for u, next_cost in G[v]:
            if cost + next_cost < dist[u]:
                dist[u] = cost + next_cost
                heappush(queue, (u, cost + next_cost))
    return dist


def main():
    global G, N
    N, M, R, *RABC = map(int, open(0).read().split())
    visit, ABC = RABC[:R], RABC[R:]
    G = [[] for _ in range(N + 1)]
    for v, u, c in zip(*[iter(ABC)] * 3):
        G[v].append((u, c)), G[u].append((v, c))
    dist = {v: dijkstra(G, N + 1, v) for v in visit}
    ans = float("inf")
    for perm in permutations(visit):
        cur = sum(dist[v][u] for v, u in zip(perm, perm[1:]))
        ans = min(ans, cur)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def dfs(c, l, d):
    if c == r:
        if ans[0] > d: ans[0] = d
        return
    for i in range(r):
        if seen[i]: continue
        seen[i] = True
        if l == -1:
            dfs(c + 1, R[i], 0)
        else:
            dfs(c + 1, R[i], d + dp[l][R[i]])
        seen[i] = False

n, m, r = map(int, input().split())
R = [i - 1 for i in map(int, input().split())]
dp = [[float("Inf") if i != j else 0 for i in range(n)] for j in range(n)]
for i in range(m):
    x, y, z = map(int, input().split())
    dp[x - 1][y - 1] = z
    dp[y - 1][x - 1] = z
for k in range(n):
    for j in range(n):
        for i in range(n):
            print(i,k,j)
            if dp[i][j] > dp[i][k] + dp[k][j]:
                dp[i][j] = dp[i][k] + dp[k][j]
seen = [False] * r
ans = [float("Inf")]
dfs(0, -1, 0)
print(*ans)

Submission status: Wrong Answer

Solution code:
def dfs(c, l, d):
    if c == r:
        if ans[0] > d: ans[0] = d
        return
    for i in range(r):
        if seen[i]: continue
        seen[i] = True
        if l == -1:
            dfs(c + 1, R[i], 0)
        else:
            dfs(c + 1, R[i], d + dp[l][R[i]])
        seen[i] = False

n, m, r = map(int, input().split())
R = [i - 1 for i in map(int, input().split())]
dp = [[float("Inf") if i != j else 0 for i in range(n)] for j in range(n)]
for i in range(m):
    x, y, z = map(int, input().split())
    dp[x - 1][y - 1] = z
    dp[y - 1][x - 1] = z
for k in range(n):
    for i in range(n):
        for j in range(n):
            if dp[i][j] > dp[i][k] + dp[k][j]:
                dp[i][j] = dp[i][k] + dp[k][j]
print(dp)
seen = [False] * r
ans = [float("Inf")]
dfs(0, -1, 0)
print(*ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(500000)

def dfs(c,l,d):
    if c == 0:
        ans[0] = min(ans[0],d)
        return
    for i in range(r):
        if seen[i]:continue
        seen[i] = True
        if l == -1:dfs(c-1,i,0)
        else:dfs(c-1,i,d+dp[R[l]-1][R[i]-1])
        seen[i] = False

n,m,r = map(int,input().split())
R = list(map(int,input().split()))
dp = [[0 if i == j else float("Inf") for i in range(n)] for j in range(n)]
for i in range(m):
    x,y,z = map(int,input().split())
    dp[x-1][y-1] = z
    dp[y-1][x-1] = z
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])
ans = [float("Inf")]
seen = [False]*r
dfs(r,-1,0)
print(*ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(500000)

def dfs(t, l, d):
    if t == r:
        if ans[0] > d: ans[0] = d
        return
    for i in range(r):
        if seen[i]: continue
        seen[i] = True
        if l == -1:
            dfs(t + 1, R[i], 0)
        else:
            dfs(t + 1, R[i], d + dp[l][R[i]])
        seen[i] = False

n, m, r = map(int, input().split())
R = [i - 1 for i in map(int, input().split())]
dp = [[float("Inf") if i != j else 0 for i in range(n)] for j in range(n)]
for i in range(m):
    x, y, z = map(int, input().split())
    dp[x - 1][y - 1] = z
    dp[y - 1][x - 1] = z
for i in range(n):
    for j in range(n):
        for k in range(n):
            if dp[i][j] > dp[i][k] + dp[k][j]:
                dp[i][j] = dp[i][k] + dp[k][j]
seen = [False] * r
ans = [float("Inf")]
dfs(0, -1, 0)
print(*ans)

Submission status: Wrong Answer

Solution code:
def dfs(t, l, d):
    if t == r:
        if ans[0] > d: ans[0] = d
        return
    for i in range(r):
        if seen[i]: continue
        seen[i] = True
        if l == -1:
            dfs(t + 1, R[i], 0)
        else:
            dfs(t + 1, R[i], d + dp[l][R[i]])
        seen[i] = False


n, m, r = map(int, input().split())
R = [i - 1 for i in map(int, input().split())]
dp = [[float("Inf") if i != j else 0 for i in range(n)] for j in range(n)]
for i in range(m):
    x, y, z = map(int, input().split())
    dp[x - 1][y - 1] = z
    dp[y - 1][x - 1] = z
for i in range(n):
    for j in range(n):
        for k in range(n):
            if dp[i][j] > dp[i][k] + dp[k][j]:
                dp[i][j] = dp[i][k] + dp[k][j]
seen = [False] * r
ans = [float("Inf")]
dfs(0, -1, 0)
print(*ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(500000)

def dfs(c,l,d):
    if c == 0:
        ans[0] = min(ans[0],d)
        return
    for i in range(r):
        if seen[i]:continue
        seen[i] = True
        if l == -1:dfs(c-1,i,0)
        else:dfs(c-1,i,d+dp[R[l]-1][R[i]-1])
        seen[i] = False

n,m,r = map(int,input().split())
R = list(map(int,input().split()))
dp = [[0]*n for _ in range(n)]
for i in range(m):
    x,y,z = map(int,input().split())
    dp[x-1][y-1] = z
    dp[y-1][x-1] = z
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])
ans = [float("Inf")]
seen = [False]*r
dfs(r,-1,0)
print(*ans)

Submission status: Wrong Answer

Solution code:
def dfs(c,l,d):
    if c == 0:
        ans[0] = min(ans[0],d)
        return
    for i in range(r):
        if seen[i]:continue
        seen[i] = True
        if l == -1:dfs(c-1,i,0)
        else:dfs(c-1,i,d+dp[R[l]-1][R[i]-1])
        seen[i] = False

n,m,r = map(int,input().split())
R = list(map(int,input().split()))
dp = [[0]*n for _ in range(n)]
for i in range(m):
    x,y,z = map(int,input().split())
    dp[x-1][y-1] = z
    dp[y-1][x-1] = z
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])
ans = [float("Inf")]
seen = [False]*r
dfs(r,-1,0)
print(*ans)

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

    '''
    Warshall-Floyd
    input:  c[|V|][|V|]
            input example to from cost
            (c[i][i] == 0)
    Output: Minimun cost of all paths in the inputed graph 
    '''
    V = N
    INF = 1000000
    d = [[INF] * (N+1) for i in range(N+1)]

    for i in range(1, N+1):
        d[i][i] = 0
 
    for i in range(M):
        d[A[i]][B[i]] = C[i]
        d[B[i]][A[i]] = C[i]

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


    ans = INF

    from itertools import permutations
    for i in permutations(r,len(r)):
        ta = 0
        for x in range(R-1):
            ta += d[i[x]][i[x+1]]
        
        ans = min(ans, ta)
    print(ans)

    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    R = int(next(tokens))  # type: int
    r = [int(next(tokens)) for _ in range(R)]  # type: "List[int]"
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    C = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    solve(N, M, R, r, A, B, C)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import itertools
import sys 
input = sys.stdin.readline
def solve():
  n,m,R = (int(i) for i in input().split())
  r = list(int(i) for i in input().split())
  d = [[0]*n for _ in range(n)]
  for i in range(m):
    a,b,c = (int(i) for i in input().split())
    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):
        if d[i][j] > d[i][k] + d[k][j]:
          d[i][j] = d[i][k] + d[k][j]

  perm = list(itertools.permutations(range(R)))
  cost = float("Inf")
  
  for i in range(len(perm)):
    root = perm[i]
    tempcost = 0
    for j in range(R-1):
      na = r[root[j]]-1
      nb = r[root[j+1]]-1
      tempcost += d[na][nb]
    cost = min(tempcost,cost)
  print(cost)
solve()

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
#ts=time.time()
#sys.setrecursionlimit(10**6)
input=sys.stdin.readline
show_flg=False
#show_flg=True

n,m,R=MI()
r=LI_()
g=[[] for _ in range(n)]
for i in range(m):
    a,b,c=LI_()
    g[a].append((b,c+1))
    g[b].append((a,c+1))

show(g)
inf=float('inf')
def wf(e):
    n=len(e)
    d=[[inf]*n for _ in range(n)]
    for a in range(n):
        for b,c in g[a]:
            d[a][b]=c
            d[b][a]=c
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j]>d[i][k]+d[j][k]:
                    d[i][j]=d[i][k]+d[j][k]
    
    return d

ans=inf
md=wf(g)
dists=[]
def search(st,d,ls):
    if len(ls)==1:
        dists.append(d+md[st][ls[0]])
        return
    for gl in ls:
        search(gl,d+md[st][gl],[i for i in ls if i!=gl])
    return

for i in r:search(i,0,r)
print(min(dists))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce



sys.setrecursionlimit(2147483647)
INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m, r = LI()
graph = [[INF] * n for _ in range(n)]
L = LI()
for u, v, c in LIR(m):
    graph[u - 1][v - 1] = c
    graph[v - 1][u - 1] = c

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


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



ans = INF
for i in permutations(range(r)):
    ret = 0
    for j in range(r - 1):
        ret += graph[i[j]-1][i[j+1]-1]
    ans = min(ans, ret)


print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import itertools

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def S(): return(sys.stdin.readline()[:-1])
def IR(n): return([I() for _ in range(n)])

def main():
    N,M,R = LI()
    rs = [int(x) -1 for x in sys.stdin.readline().split()]
    D = [[10**10]*N for _ in range(N)]
    for _ in range(M):
        A,B,C = LI()
        D[A-1][B-1] = C
        D[B-1][A-1] = C
    for i in range(N):
        D[i][i] = 0

    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 = 10**11
    for trs in itertools.permutations(rs):
        tans = 0
        for i in range(R-1):
            tans += D[trs[i]][trs[i+1]]
        ans = min(ans,tans)
    
    return(ans)

if __name__ == "__main__":
    print(main())

Submission status: Wrong Answer

Solution code:
import sys
import heapq
import bisect
import itertools

mod = 10**9+7
dd = ((-1,0),(1,0),(0,-1),(0,1))

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def S(): return(sys.stdin.readline()[:-1])
def IR(n): return([I() for _ in range(n)])

def GCD(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def LCM(a,b):
    return a * b // GCD(a,b)

def Eratosthenes(N):
    r = [True]*(N+1)
    r[0] = False
    r[1] = False
    i = 2
    while i*i<=N:
        if r[i]: 
            j = i
            while i*j<=N:
                prime[i*j]=False
                j+=1
        i+=1
    return(r)

def main():
    N,M,R = LI()
    rs = LI()
    D = [[10**10]*N for _ in range(N)]
    for _ in range(M):
        A,B,C = LI()
        D[A-1][B-1] = C
        D[B-1][A-1] = C
    for i in range(N):
        D[i][i] = 0

    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 = 10**11
    for trs in itertools.permutations(rs):
        tans = 0
        for i in range(R-1):
            tans += D[trs[i]-1][trs[i+1]-1]
        ans = min(ans,tans)
    
    return(ans)

if __name__ == "__main__":
    print(main())

Submission status: Wrong Answer

Solution code:
from itertools import permutations

def WarshallFloyd(M):
    N = len(M)
    for k in range(N):
        for j in range(N):
            for i in range(N):
                M[i][j] = min(M[i][j], M[i][k] + M[k][j])
    return M

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

E = WarshallFloyd(E)
ans = min(sum(E[p[i]][p[i + 1]] for i in range(K - 1)) for p in permutations(R))
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools
import heapq
in_=list(map(int,input().split()))
N,M,R=in_[0],in_[1],in_[2]
r=list(map(int,input().split()))
all_paths=np.zeros((N,N))
min_paths=np.zeros((N,N))
for i in range(M):
  in_=list(map(int,input().split()))
  A,B,c=in_[0],in_[1],in_[2]
  all_paths[A-1,B-1]=c
  all_paths[B-1,A-1]=c
def indexv(j,l):
  boo=-1
  for i in range(len(l)):
    if l[i][1]==j:
      boo=i
      break
  return boo
def min_path(i,j):
  if i==j:
    return 0
  if not min_paths[i,j]==0:
    return min_paths[i,j]
  q=[]
  #一本目のpathの追加
  for k in range(N):
    if k==i:continue
    if not min_paths[i,k]==0:
      heapq.heappush(q,(min_paths[i,k],k))
      continue
    c=all_paths[i,k]
    if not c==0:
      heapq.heappush(q,(all_paths[i,k],k))
  while len(q)>0:
    v=heapq.heappop(q)
    min_paths[i,v[1]]=v[0]
    min_paths[v[1],i]=v[0]
    if v[1]==j:
      break
    for k in range(N):
      if k==i:continue
      if not min_paths[v[1],k]==0:
        index=indexv(k,q)
        if index==-1:
          heapq.heappush(q,(min_paths[i,v[1]]+min_paths[v[1],k],k))
        else:
          if q[index][0]>min_paths[i,v[1]]+min_paths[v[1],k]:
            q[index]=(min_paths[i,v[1]]+min_paths[v[1],k],k)
        continue
      c=all_paths[v[1],k]
      if not c==0:
        index=indexv(k,q)
        if index==-1:
      	  heapq.heappush(q,(min_paths[i,v[1]]+c,k))
        else:
          if q[index][0]>min_paths[i,v[1]]+c:
            q[index]=(min_paths[i,v[1]]+c,k)
  return min_paths[i,j]

for i in range(R-1):
  for j in range(i+1,R):
    min_path(r[i]-1,r[j]-1)
  min_paths[:,r[i]-1]=min_paths[r[i]-1,:].T

min_cost=float('inf')
for path in list(itertools.permutations(range(R))):
  cost=0
  for i in range(len(path)-1):
    cost=cost+min_paths[r[path[i]]-1,r[path[i+1]]-1]
  if cost<min_cost:
    min_cost=cost
print(int(min_cost))

Submission status: Wrong Answer

Solution code:
N, M, R = map(int, input().split())
rs = list(map(int, input().split()))
D = [[100000*200]*N for i in range(N)]
for i in range(N):
  D[i][i] = 0
for i in range(M):
  A, B, C = map(int, input().split())
  A, B = A-1, B-1
  D[A][B] = C
  D[B][A] = C
for k in range(N):
  for i in range(N):
    for j in range(N):
      D[i][j] = min(D[i][j], D[i][k]+D[k][j])
#print(D)
r = 100000*200
for i in range(R):
  rs[i] -= 1
import itertools
for rs2 in itertools.permutations(rs):
  r2 = 0
  for i in range(1, R):
    r2 += D[rs2[i-1]][rs2[i]]
  r = min(r, r2)
print(r)

Submission status: Wrong Answer

Solution code:
from itertools import permutations as p
def wf(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
n,m,r=map(int,input().split())
d=[[10**6]*n for i in range(n)] 
rl=list(map(int,input().split()))
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
dl=wf(d)
pl=list(p(rl))
x=[]
for i in pl:
  t=0
  for j in range(r-1):
    t+=d[i[j]-1][i[j+1]-1]
  x.append(t)
print(min(x))

Submission status: Wrong Answer

Solution code:
import itertools

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

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

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

ans = float('inf')
k = list(itertools.permutations(r))
for i in k:
	sumDist = 0
	for j in range(len(i) - 1):
		sumDist += dist[i[j]][i[j+1]]
	ans = min(ans, sumDist)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys,itertools
input=sys.stdin.readline
INF=float('inf')
n,m,r=map(int,input().split())
R=list(map(int,input().split()))
distance=[[INF]*n for _ in range(n)]
for _ in range(m):
   a,b,c=map(int,input().split())
   distance[a-1][b-1]=c
   distance[b-1][a-1]=c

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

ans=INF
for j in itertools.permutations(range(r)):
   cnt=0
   for k in range(r-1):
      cnt+=distance[j[k]-1][j[k+1]-1]
   ans=min(ans,cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque
from itertools import permutations
inf = float('inf')

def min_dis_dfs(graph, start_node, end_node):
  global dis_dict
  stack = deque()
  stack.append([start_node,0])
  done = []
  min_dis = inf
  
  while len(stack) > 0:
    prv_node, prv_dis = stack.pop()
    #print('#'*20)
    #print("prv_node:{}, prv_dis:{}".format(prv_node, prv_dis))
    for node, dis in graph[prv_node]:
      if node not in done:
        if node == end_node:
          if min_dis > prv_dis + dis:min_dis=prv_dis + dis
        else:
          done.append(node)
          stack.append([node,prv_dis + dis])
      #print('node:{}, min_dis:{}, dis:{}'.format(node, min_dis, dis))c
  if start_node > end_node:dis_key = str(start_node) + '-' + str(end_node)
  else:dis_key = str(end_node) + '-' + str(start_node)
  dis_dict[dis_key] = min_dis
  return min_dis
  
n,m,r =map(int,input().split())
rlist = [int(a)-1 for a in input().split()]
graph = defaultdict(list)
dis_dict = {}

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

ans = inf
for r_case in permutations(rlist, r):
  dis = 0
  for i in range(r-1):
    if r_case[i] > r_case[i+1]:dis_key = str(r_case[i]) + '-' + str(r_case[i+1])
    else:dis_key = str(r_case[i+1]) + '-' + str(r_case[i])
    
    if dis_key in dis_dict:dis += dis_dict[dis_key]
    else:dis += min_dis_dfs(graph, r_case[i], r_case[i+1])
  if ans > dis:ans = dis
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque
from itertools import permutations
inf = float('inf')

def min_dis_dfs(graph, start_node, end_node):
  global dis_dict
  stack = deque()
  stack.append([start_node,0])
  done = []
  min_dis = inf
  
  while len(stack) > 0:
    prv_node, prv_dis = stack.pop()
    #print('#'*20)
    #print("prv_node:{}, prv_dis:{}".format(prv_node, prv_dis))
    for node, dis in graph[prv_node]:
      if node not in done:
        if node == end_node:
          if min_dis > prv_dis + dis:min_dis=prv_dis + dis
        else:
          done.append(node)
          stack.append([node,prv_dis + dis])
      #print('node:{}, min_dis:{}, dis:{}'.format(node, min_dis, dis))
  
  if start_node > end_node:dis_key = str(start_node) + '-' + str(end_node)
  else:dis_key = str(end_node) + '-' + str(start_node)
  dis_dict[dis_key] = min_dis
  return min_dis
  
n,m,r =map(int,input().split())
rlist = [int(r)-1 for r in input().split()]
graph = defaultdict(list)
dis_dict = {}

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

ans = inf
for r_case in permutations(rlist, r):
  dis = 0
  for i in range(r-1):
    if r_case[i] > r_case[i+1]:dis_key = str(r_case[i]) + '-' + str(r_case[i+1])
    else:dis_key = str(r_case[i+1]) + '-' + str(r_case[i])
    
    if dis_key in dis_dict:dis += dis_dict[dis_key]
    else:dis += min_dis_dfs(graph, r_case[i], r_case[i+1])
  if ans > dis:ans = dis
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque
from itertools import permutations
inf = float('inf')

def min_dis_dfs(graph, start_node, end_node):
  global dis_dict
  stack = deque()
  stack.append([start_node,0])
  done = []
  min_dis = inf
  
  while len(stack) > 0:
    prv_node, prv_dis = stack.pop()
    #print('#'*20)
    #print("prv_node:{}, prv_dis:{}".format(prv_node, prv_dis))
    for node, dis in graph[prv_node]:
      if node not in done:
        if node == end_node and min_dis > prv_dis + dis:min_dis=prv_dis + dis
        else:
          done.append(node)
          stack.append([node,prv_dis + dis])
      #print('node:{}, min_dis:{}, dis:{}'.format(node, min_dis, dis))
  
  if start_node > end_node:dis_key = str(start_node) + '-' + str(end_node)
  else:dis_key = str(end_node) + '-' + str(start_node)
  dis_dict[dis_key] = min_dis
  return min_dis
  
n,m,r =map(int,input().split())
rlist = [int(r)-1 for r in input().split()]
graph = defaultdict(list)
dis_dict = {}

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

ans = inf
for r_case in permutations(rlist, r):
  dis = 0
  for i in range(r-1):
    if r_case[i] > r_case[i+1]:dis_key = str(r_case[i]) + '-' + str(r_case[i+1])
    else:dis_key = str(r_case[i+1]) + '-' + str(r_case[i])
    
    if dis_key in dis_dict:dis += dis_dict[dis_key]
    else:dis += min_dis_dfs(graph, r_case[i], r_case[i+1])
  if ans > dis:ans = dis
print(ans)

Submission status: Wrong Answer

Solution code:
import sys,heapq,itertools
input=sys.stdin.readline
heappush=heapq.heappush
heappop=heapq.heappop
INF=float('inf')
n,m,r=map(int,input().split())
R=list(map(int,input().split()))
Map=[[] for _ in range(n)]
for _ in range(m):
   a,b,c=map(int,input().split())
   Map[a-1].append((b-1,c))
   Map[b-1].append((a-1,c))

def dijkstra(n,graph,start):
    Q=[]
    distance=[]
    dappend=distance.append
    for i in range(n):
        dappend([INF,i])
    distance[start][0]=0
    for i in distance:
        heappush(Q,i)
    while Q!=[]:
        q=heappop(Q)
        for v,vl in graph[q[1]]:
            alt=vl+q[0]
            if alt<distance[v][0]:
                distance[v][0]=alt
                heappush(Q,[alt,v])
    return distance

distance=[]
for i in range(n):
   distance.append(dijkstra(n,Map,i))

ans=INF
for j in itertools.permutations(range(r)):
   cnt=0
   for k in range(r-1):
      cnt+=distance[j[k]-1][j[k+1]-1][0]
   ans=min(ans,cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations

n,m,R=map(int,input().split())
r=list(map(int,input().split()))
s=[[0]*n for i in range(n)]
for i in range(m):
    a, b, c = list(map(int, input().split()))
    a, b = a-1, b-1
    s[a][b] = c
    s[b][a] = c
for k in range(n):
    for i in range(n):
        for j in range(n):
            if s[i][j]>s[k][j]+s[i][k]:
                s[i][j]=s[k][j]+s[i][k]
ans=float('inf')
for i in permutations(r):
    an=0
    for j in range(R-1):
        an+=s[i[j]-1][i[j+1]-1]
    ans=min(ans,an)
print(int(ans))

Submission status: Wrong Answer

Solution code:
import itertools

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