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 sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**8
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,M,R = LI()
    r = _LI()
    root = [[] for _ in range(N)]
    for _ in range(M):
        a,b,c = LI()
        root[a-1].append((b-1,c))
        root[b-1].append((a-1,c))

    memo = [[0] * N for _ in range(N)]

    min_r = INF
    for x in itertools.permutations(r):
        it = 0
        s = x[0]
        for t in x[1:]:
            if memo[s][t]:
                it += memo[s][t]
            else:
                node = [INF] * N
                q = collections.deque()
                q.append((s,0))
                while q:
                    u,l = q.popleft()
                    if node[u] <= l: continue
                    node[u] = l
                    for v,m in root[u]:
                        if node[v] > l + m:
                            node[v] = l + m
                            q.append((v,l+m))
                memo[s][t] = node[t]
                memo[t][s] = node[t]
                it += node[t]
            s = t
        min_r = min(min_r,it)
    print(min_r)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**8
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,M,R = LI()
    r = _LI()
    root = [[] for _ in range(N)]
    for _ in range(M):
        a,b,c = LI()
        root[a-1].append((b-1,c))
        root[b-1].append((a-1,c))

    memo = [[0] * N for _ in range(N)]

    min_r = INF
    for x in itertools.permutations(r):
        it = 0
        s = x[0]
        for t in x[1:]:
            if memo[s][t]:
                it += memo[s][t]
            else:
                node = [INF] * N
                q = [(s,0)]
                while q:
                    u,l = q.pop()
                    node[u] = l
                    for v,m in root[u]:
                        if node[v] > l + m:
                            q.append((v,l+m))
                memo[s][t] = node[t]
                memo[t][s] = node[t]
                it += node[t]
            s = t
        min_r = min(min_r,it)
    print(min_r)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from itertools import permutations


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

graph = [[0 for _ in range(n)] for _ in range(n)]

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

# ワーシャルフロイド

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

min_dist = 10**10
for route in permutations(towns, r):
    dist = 0
    for i in range(r-1):
        a = route[i] - 1
        b = route[i+1] - 1
        dist += graph[a][b]
    if dist < min_dist:
        min_dist = dist

print(min_dist)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
INF = float("inf")

n, m, r = map(int, input().split())
r = list(map(lambda x: int(x)-1, input().split()))
g = [[0] * n for _ in range(n)]
abc = [tuple(map(int, input().split())) for _ in range(m)]
for a, b, c in abc:
    a -= 1; b -= 1
    g[a][b] = c
    g[b][a] = c

def warshall_floyd(d, n):
    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(g, n)
ans = INF

for route in permutations(r):
    res = 0
    for i in range(1, len(r)):
        res += d[route[i-1]][route[i]]
    ans = min(ans, res)

print(ans)

Submission status: Wrong Answer

Solution code:
INF = 10**18
n,m,R = map(int,input().split())
r=list(map(int,input().split()))
for i in range(R):
    r[i]-=1
d = [[INF]*n for i in range(n)] 
# 入力
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 i in range(n):
    d[i][i] = 0

def FW():
    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])
FW()
from itertools import permutations, combinations
ans=INF
for v in permutations(r):
    tmp=0
    for i in range(R-1):
        tmp+=d[v[i]][v[i+1]]
    ans=min(ans,tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
INF = 10**10
n,m,R = map(int,input().split())
r=list(map(int,input().split()))
for i in range(R):
    r[i]-=1
d = [[INF]*n for i in range(n)] 
# 入力
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 i in range(n):
    d[i][i] = 0

def FW():
    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])
FW()
from itertools import permutations, combinations

ans=INF
for v in permutations(r):
    tmp=0
    for i in range(R-1):
        tmp+=d[v[i]][v[i+1]]
    ans=min(ans,tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
INF = 10**10
n,m,R = map(int,input().split())
r=list(map(int,input().split()))
for i in range(R):
	r[i]-=1
d = [[INF]*n for i in range(n)] 
# 入力
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 i in range(n):
    d[i][i] = 0

def FW():
    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])
FW()

from itertools import permutations, combinations

ans=10**10
for v in permutations(r):
    tmp=0
    for i in range(R-1):
        tmp+=d[v[i]][v[i+1]]
    ans=min(ans,tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
#s=input().rstrip()

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:辺の数
lis=LI()
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())
    x-=1
    y-=1
    d[x][y] = z
    d[y][x] = z
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
#print(warshall_floyd(d))
#インデックスで与えられていることに注意

z=permutations(lis,r)
mn=inf
for s in z:
    u=list(s)
    dis=0
    for i in range(r-1):
        dis+=d[u[i]-1][u[i+1]-1]
    if dis<mn:
        mn=dis
print(mn)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import permutations

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m, r = map(int, input().split())
    R = list(map(int, input().split()))
    C = [[0 for _ in range(n)] for _ in range(n)]

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

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

    res = f_inf
    for pattern in permutations(R):
        cost = 0
        for k in range(r - 1):
            i, j = pattern[k], pattern[k + 1]
            cost += C[i - 1][j - 1]
        res = min(res, cost)

    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
from itertools import permutations

n, m, r = map(int, readline().split())
rr = list(map(int, readline().split()))
graph = [[0] * n for _ in range(n)]
for i in range(m):
    a, b, c = map(int, readline().split())
    graph[a - 1][b - 1] = c
    graph[b - 1][a - 1] = c
cost = floyd_warshall(csr_matrix(graph))
ans = float('inf')
for bit in permutations(rr):
    cnt = 0
    for now, next in zip(bit, bit[1:]):
        cnt += cost[now - 1][next - 1]
    ans = min(cnt, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque, defaultdict
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
inf = 10 ** 10
n, m, r = map(int,input().split())
R = list(map(int,input().split()))

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

G = csgraph_from_dense(edge, null_value = inf)
d = floyd_warshall(G, False)

def cal(s, R):
    #sは始点
    log = defaultdict(lambda :0)
    for i in R:log[i] = 1
    q = deque([s])
    log[s] = 0
    rec = 0
    cnt = 1
    while q:
        v = q.pop()
        mini = inf
        ind = 0
        for i in range(n):
            if i == v - 1:continue
            if not log[i + 1]:continue
            temp = d[v - 1][i]
            if temp < mini:
                mini = temp
                ind = i + 1
        if mini == inf:
            if cnt != r:
                log[v - 1] = 1
                cnt += 1
                q.append(ind)
                continue
            else:
                return rec
        log[ind] = 0
        cnt += 1
        rec += mini
        q.append(ind)
        #print(rec, (mini, ind), s)

rec = inf
for i in R:
    temp = cal(i, R)
    if temp == -1:continue
    rec = min(temp, rec)

print(int(rec))

Submission status: Wrong Answer

Solution code:
from collections import deque, defaultdict
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
inf = 10 ** 10
n, m, r = map(int,input().split())
R = list(map(int,input().split()))

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

G = csgraph_from_dense(edge, null_value = inf)
d = floyd_warshall(G, False)

def cal(s, R):
    #sは始点
    log = defaultdict(lambda :0)
    for i in R:log[i] = 1
    q = deque([s])
    log[s] = 0
    rec = 0
    cnt = 1
    while q:
        v = q.pop()
        mini = inf
        ind = 0
        for i in range(n):
            if i == v - 1:continue
            if not log[i + 1]:continue
            temp = d[v - 1][i]
            if temp < mini:
                mini = temp
                ind = i + 1
        if mini == inf:
            if cnt != r:
                log[v - 1] = 1
                cnt = 1
                q.append(ind)
                continue
            else:
                return rec
        log[ind] = 0
        cnt += 1
        rec += mini
        q.append(ind)
        #print(rec, (mini, ind), s)

rec = inf
for i in R:
    temp = cal(i, R)
    if temp == -1:continue
    rec = min(temp, rec)

print(int(rec))

Submission status: Wrong Answer

Solution code:
from collections import deque, defaultdict
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
inf = 10 ** 10
n, m, r = map(int,input().split())
R = list(map(int,input().split()))

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

G = csgraph_from_dense(edge, null_value = inf)
d = floyd_warshall(G, False)
#print(*d, sep = '\n')


def cal(s, R):
    #sは始点
    log = defaultdict(lambda :0)
    for i in R:log[i] = 1
    q = deque([s])
    log[s] = 0
    rec = 0
    cnt = 0
    while q:
        v = q.pop()
        mini = inf
        ind = 0
        for i in range(n):
            if i == v - 1:continue
            if not log[i + 1]:continue
            temp = d[v - 1][i]
            if temp < mini:
                mini = temp
                ind = i + 1
        if mini == inf:
            if cnt == 0:
                log[v - 1] = 1
                cnt = 1
                continue
            else:
                return - 1
        log[ind] = 0
        rec += mini
        q.append(ind)
        #print(rec, (mini, ind), s)
    return rec

rec = inf
for i in R:
    temp = cal(i, R)
    if temp == -1:continue
    rec = min(temp, rec)

print(int(rec))

Submission status: Wrong Answer

Solution code:
from collections import deque, defaultdict
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
inf = 10 ** 10
n, m, r = map(int,input().split())
R = list(map(int,input().split()))

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

G = csgraph_from_dense(edge, null_value = inf)
d = floyd_warshall(G, False)
#print(*d, sep = '\n')


def cal(s, R):
    #sは始点
    log = defaultdict(lambda :0)
    for i in R:
        log[i] = 1
    q = deque()
    q.append(s)
    log[s] = 0
    rec = 0
    while q:
        v = q.pop()
        mini = inf
        ind = 0
        for i in range(n):
            if i == v - 1:continue
            if not log[i + 1]:continue
            temp = d[v - 1][i]
            if temp < mini:
                mini = temp
                ind = i + 1
        if mini == inf:continue
        log[ind] = 0
        rec += mini
        q.append(ind)
        #print(rec, (mini, ind), s)
    return rec

rec = inf
for i in R:
    rec = min(cal(i, R), rec)

print(int(rec))

Submission status: Wrong Answer

Solution code:
'''重み0の辺は自動で消されてしまうので注意'''
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
inf = 10 ** 10
n, m, r = map(int,input().split())
R = list(map(int,input().split()))

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

G = csgraph_from_dense(edge, null_value = inf)
d = floyd_warshall(G, False)
#print(*d, sep = '\n')

rec = 0
for i in R:
    for j in R:
        if i == j:continue
        temp = d[i - 1][j - 1]
        if temp > rec:rec = temp
print(int(rec))

Submission status: Wrong Answer

Solution code:
import itertools

MAX_DIS = 10**10
N,M,R = map(int,input().split(" "))
r_list = list(map(int,input().split(" ")))
roads = [[MAX_DIS for i in range(N)] for i in range(N)]
for i in range(N):
    roads[i][i] = 0
for i in range(M):
    A,B,C = map(int,input().split(" "))
    roads[A-1][B-1] = C
    roads[B-1][A-1] = C
for i in range(N):
    for j in range(N):
        for k in range(N):
            roads[i][j] = min(roads[i][j],roads[i][k]+roads[k][j])
min_dis = MAX_DIS
for directions in itertools.permutations(r_list):
    distance  = 0
    for dir in range(1,len(directions)):
        distance += roads[directions[dir-1]-1][directions[dir]-1]
    if distance < min_dis:
        min_dis =distance
print(min_dis)

Submission status: Wrong Answer

Solution code:
import itertools

MAX_DIS = 10**10
N,M,R = map(int,input().split(" "))
r_list = list(map(int,input().split(" ")))
roads = [[MAX_DIS for i in range(N)] for i in range(N)]
for i in range(N):
    roads[i][i] = 0
print(roads)
for i in range(M):
    A,B,C = map(int,input().split(" "))
    roads[A-1][B-1] = C
    roads[B-1][A-1] = C
for i in range(N):
    for j in range(N):
        for k in range(N):
            roads[i][j] = min(roads[i][j],roads[i][k]+roads[k][j])
min_dis = MAX_DIS
for directions in itertools.permutations(r_list):
    distance  = 0
    for dir in range(1,len(directions)):
        distance += roads[directions[dir-1]-1][directions[dir]-1]
    if distance < min_dis:
        min_dis =distance
print(min_dis)

Submission status: Wrong Answer

Solution code:
t,r,g=map(int,input().split())
inf=10**1000000
d=[[inf  for ccc in range(t)] for i in range(t)]
for i in range(t):
    d[i][i]=0
gl=list(map(int,input().split()))
for j in range(r):
    x,y,c=map(int,input().split())
    d[x-1][y-1]=c
    d[y-1][x-1]=c
for i in range(t):
    for j in range(t):
        for k in range(t):
            d[i][j]=min(d[i][j],d[i][k]+d[k][j])
from itertools import permutations as pe
ans=inf
for G in pe(gl):
    p=0
    for qw in range(g-1):
        p+=d[G[qw]-1][G[qw+1]-1]
    ans=min(ans,p)
print(ans)

Submission status: Wrong Answer

Solution code:
t,r,g=map(int,input().split())
d=[[float("INF") for ccc in range(t)] for i in range(t)]
for i in range(t):
    d[i][i]=0
gl=list(map(int,input().split()))
for j in range(r):
    x,y,c=map(int,input().split())
    d[x-1][y-1]=c
    d[y-1][x-1]=c
for i in range(t):
    for j in range(t):
        for k in range(t):
            d[i][j]=min(d[i][j],d[i][k]+d[k][j])
from itertools import permutations as pe
ans=float("INF")
for i in pe(gl):
    p=0
    xc=list(i)
    for qw in range(1,g):
        p+=min(d[xc[qw-1]-1][xc[qw]-1],d[xc[qw]-1][xc[qw-1]-1])
    ans=min(ans,p)
print(ans)

Submission status: Wrong Answer

Solution code:
t,r,g=map(int,input().split())
d=[[float("INF") for ccc in range(t)] for i in range(t)]
for i in range(t):
    d[i][i]=0
gl=list(map(int,input().split()))
for j in range(r):
    x,y,c=map(int,input().split())
    d[x-1][y-1]=c
    d[y-1][x-1]=c
for i in range(t):
    for j in range(t):
        for k in range(t):
            d[i][j]=min(d[i][j],d[i][k]+d[k][j])
        d[j][i]=d[i][j]
from itertools import permutations as pe
ans=float("INF")
for i in pe(gl):
    p=0
    xc=list(i)
    for qw in range(1,g):
        p+=d[xc[qw-1]-1][xc[qw]-1]
    ans=min(ans,p)
print(ans)

Submission status: Wrong Answer

Solution code:
t,r,g=map(int,input().split())
d=[[float("INF") for ccc in range(t)] for i in range(t)]
for i in range(t):
    d[i][i]=0
gl=list(map(int,input().split()))
for j in range(r):
    x,y,c=map(int,input().split())
    d[x-1][y-1]=c
    d[y-1][x-1]=c
for i in range(t):
    for j in range(t):
        for k in range(t):
            d[i][j]=min(d[i][j],d[i][k]+d[k][j])
from itertools import permutations as pe
ans=float("INF")
cv=len(gl)
for i in pe(gl):
    p=0
    xc=list(i)
    for qw in range(1,cv):
        p+=d[xc[qw-1]-1][xc[qw]-1]
    ans=min(ans,p)
print(ans)

Submission status: Wrong Answer

Solution code:
t,r,g=map(int,input().split())
d=[[float("INF") for ccc in range(t)] for i in range(t)]
for i in range(t):
    d[i][i]=0
gl=list(map(int,input().split()))
for j in range(r):
    x,y,c=map(int,input().split())
    d[x-1][y-1]=c
    d[y-1][x-1]=c
for i in range(t):
    for j in range(t):
        for k in range(t):
            d[i][j]=min(d[i][j],d[i][k]+d[k][j])
from itertools import permutations as pe
ans=float("INF")
for i in pe(gl):
    p=0
    xc=list(i)
    for k,j in zip(xc,xc[1:]):
        p+=d[k-1][j-1]
    ans=min(ans,p)
print(ans)

Submission status: Wrong Answer

Solution code:
t,r,g=map(int,input().split())
d=[[float("INF")]*t for i in range(t)]
for i in range(t):
    d[i][i]=0
gl=list(map(int,input().split()))
for j in range(r):
    x,y,c=map(int,input().split())
    d[x-1][y-1]=c
    d[y-1][x-1]=c
for i in range(t):
    for j in range(t):
        for k in range(t):
            d[i][j]=min(d[i][j],d[i][k]+d[k][j])
from itertools import permutations as pe
ans=float("INF")
for i in pe(gl,r=None):
    #rは長さ、Noneでiteraterの長さ
    p=0
    for k,j in zip(i,i[1:]):
        p+=d[k-1][j-1]
    ans=min(ans,p)
print(ans)

Submission status: Wrong Answer

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

n,m,r= map(int, input().split())
rr= list(map(int, input().split()))
a= [list(map(int, input().split())) for i in range(m)]
edges=[[] for i in range(n)]

for x,y,z in a:
    edges[x-1].append((y-1,z))
    edges[y-1].append((x-1,z))

#ダイクストラ法
from heapq import heappush, heappop

def dijkstra(edges, size, source,g):
    # edge=探索するグラフ
    # size=グラフの点の数
    # source=スタート点
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance[g]

# bit DP
# dp[S][v]: 訪れた点の集合がSで最後にVを訪れた時のVのMIN
INF=float('inf')
dp=[[INF]*r for i in range(1<<r)]
dp[0]=[0]*r

for i in range(1<<r):
    for k in range(r):
        # 訪問リストに入っているものを最後に訪問する時
        if (i >> k) & 1:
            # 最後に訪れるものを除いた集合でどこを最後に訪問した時がminか調べる
            dpm = min(dp[i ^ (1 << k)])
            xx = dp[i ^ (1 << k)].index(min(dp[i ^ (1 << k)]))
            ad = dijkstra(edges, n, rr[xx] - 1, rr[k] - 1)
            dp[i][k] = dpm + ad

print(min(dp[-1]))

Submission status: Wrong Answer

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

n,m,r= map(int, input().split())
rr= list(map(int, input().split()))
a= [list(map(int, input().split())) for i in range(m)]
edges=[[] for i in range(n)]

for x,y,z in a:
    edges[x-1].append((y-1,z))
    edges[y-1].append((x-1,z))

#ダイクストラ法
from heapq import heappush, heappop

def dijkstra(edges, size, source,g):
    # edge=探索するグラフ
    # size=グラフの点の数
    # source=スタート点
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance[g]

# bit DP
# dp[S][v]: 訪れた点の集合がSで最後にVを訪れた時のVのMIN
INF=pow(10,12)
dp=[[INF]*r for i in range(1<<r)]
dp[0]=[0]*r

for i in range(1<<r):
    cnt = []
    for j in range(r):
        # 論理積１なら訪問
        if (i>>j)&1:
            cnt.append(rr[j])
    for k in range(r):
        # 訪問リストに入っているものを最後に訪問する時
        if (i >> k) & 1:
            # 最後に訪れるものを除いた集合でどこを最後に訪問した時がminか調べる
            dpm = min(dp[i ^ (1 << k)])
            xx = dp[i ^ (1 << k)].index(min(dp[i ^ (1 << k)]))
            ad = dijkstra(edges, n, rr[xx] - 1, rr[k] - 1)
            dp[i][k] = dpm + ad

print(min(dp[-1]))

Submission status: Wrong Answer

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

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

def main():
    N, M, R = map(int, input().split())
    A = list(map(int, input().split()))
    inf = float('inf')
    G = [[inf] * N for _ in range(N)]
    for _ 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)
    warshall_floyd(G)
    ans = float('inf')
    for perm in permutations(A, R):
        tmp = 0
        for i in range(R-1):
            tmp += G[A[i]-1][A[i+1]-1]
        ans = min(ans, tmp)
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from heapq import heappop, heappush

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

def prim(G):
    used = [False] * len(G) 
    hq = [(0, 0)]
    res = 0
    while hq:
        w, v = heappop(hq)
        if used[v]:
            continue
        used[v] = True
        res += w
        for cv, cw in G[v]:
            if used[cv]:
                continue
            heappush(hq, (cw, cv))
    return res

def main():
    N, M, R = map(int, input().split())
    R_l = list(map(int, input().split()))
    A = {}
    for i, a in enumerate(R_l):
        A[a-1] = i
    inf = float('inf')
    graph = [[inf] * R for _ in range(R)]
    for i in range(R):
        graph[i][i] = 0
    for _ in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        if a in A and b in A:
            graph[A[a]][A[b]] = min(c, graph[A[a]][A[b]])
            graph[A[b]][A[a]] = min(c, graph[A[b]][A[a]])
    warshall_floyd(R, graph)
    graph2 = [[] for _ in range(R)]
    for i in range(R-1):
        for j in range(i+1, R):
            graph2[i].append((j, graph[i][j]))
            graph2[j].append((i, graph[i][j]))
    print(prim(graph2))

if __name__ == '__main__':
    main()

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

import sys
input = sys.stdin.readline
n,m,r = map(int,input().split())
R = [int(i)-1 for i in input().split()]
d = [[10**9]*n for i in range(n)]

for i in range(m):
    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
    
chk = tuple(warshall_floyd(d))
ans = float('inf')

import itertools
for i in itertools.permutations(R, r):
  if i[0] >= 5:
    break
  p = 0
  for j in range(r-1):
    p += d[i[j]][i[j+1]]
  ans = min(ans,p)
  
print(ans)

Submission status: Wrong Answer

Solution code:
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
INF = 10**15
cost = [[INF for _ in range(N)] for _ 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
    
def dijkstra(s, n, w, cost):
    d = [INF]*N
    used = [False]*N
    d[s] = 0
    
    while True:
        v = -1
        for i in range(N):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if(v == -1):
            break
        used[v] = True
        
        for j in range(N):
            d[j] = min(d[j], d[v]+cost[v][j])
    return d

ans = dijkstra(0, N, M, cost)
print(max(ans))

Submission status: Wrong Answer

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

n,m,r=map(int,input().split())
r=list(map(int,input().split()))
abc=[list(map(int,input().split())) for i in range(m)]

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 = [[float("inf") for i in range(n)] for i in range(n)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(m):
    x,y,z = abc[i]
    x-=1
    y-=1
    d[x][y] = z
    d[y][x] = z
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
# print(warshall_floyd(d))

lst=list(permutations(r))
# print(lst)

ans=float('inf')
for i in range(len(lst)):
    tmp=0
    for j in range(len(lst[i])-1):
        tmp+=d[lst[i][j+1]-1][lst[i][j]-1]
    ans=min(ans,tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
INF = 10 ** 8

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

G = [[INF] * N for _ in range(N)]
for i in range(N):
    G[i][i] = 0
for el in ABC:
    a, b, c = el
    G[a-1][b-1] = c
    G[b-1][a-1] = c

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

#print(G)
M = 0
for i in range(N):
    for j in range(N):
        if i + 1 in r and j + 1 in r:
            M = max(M, G[i][j])
print(M)

Submission status: Wrong Answer

Solution code:
import itertools

n,m,r=map(int,input().split())
D=[[10**10]*n for _ in range(n)]
R=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
A=[]
for v in itertools.permutations(R,r):
    ans=0
    for i in range(r-1):
        ans+=D[v[i]-1][v[i+1]-1]
    A.append(ans)
print(min(A))

Submission status: Wrong Answer

Solution code:
import itertools
n,m,r=map(int,input().split())
point=list(map(int,input().split()))
g=[[10**9]*n for i in range(n)]
for _ in range(m):
  u,v,c=map(int,input().split())
  g[u-1][v-1]=g[v-1][u-1]=c
for k in range(n):
  for i in range(n):
    for j in range(n):
      g[i][j]=min(g[i][j],g[i][k]+g[k][j])
for i in range(n):
  g[i][i]=0
ans=10**18
for v in itertools.permutations(point):
  tmp=0
  for i in range(r-1):
    tmp+=g[v[i]-1][v[i+1]-1]
  ans=min(ans,tmp)
  if ans==2:
    print(v)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
n,m,r=map(int,input().split())
point=list(map(int,input().split()))
g=[[10**9]*n for i in range(n)]
for _ in range(m):
  u,v,c=map(int,input().split())
  g[u-1][v-1]=g[v-1][u-1]=c
for k in range(n):
  for i in range(n):
    for j in range(n):
      g[i][j]=min(g[i][j],g[i][k]+g[k][j])
for i in range(n):
  g[i][i]=0
ans=10**18
for v in itertools.permutations([int(i) for i in range(r)]):
  tmp=0
  for i in range(r-1):
    tmp+=g[v[i]][v[i+1]]
  ans=min(ans,tmp)
print(ans)