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:
from itertools import permutations


def warshal(N, ABCs):
    dists = [[10 ** 10 for _ in range(N)] for __ in range(N)]
    for i in range(N):
        dists[i][i] = 0

    for a, b, c in ABCs:
        dists[a - 1][b - 1] = c
        dists[b - 1][a - 1] = c

    for s in range(N):
        for e in range(N):
            for i in range(N):
                dists[s][e] = min(dists[s][e], dists[s][i] + dists[i][e])
    return dists



def solve(N, M, R, Rs, ABCs):
    print(N, ",", M, ",", R, ",", Rs, ", ", ABCs)
    dists = warshal(N, ABCs)
    ans = 10 ** 10
    for way in permutations(Rs):
        ans = min(ans, sum([dists[i - 1][j - 1] for i, j in zip(way, way[1:])]))

    return ans


if __name__ == "__main__":
    N, M, R = tuple(map(int, input().split(" ")))
    Rs = list(map(int, input().split(" ")))
    ABCs = [tuple(map(int, input().split(" "))) for _ in range(M)]
    print(solve(N, M, R, Rs, ABCs))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from heapq import heappop, heappush
import itertools
class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)
    def __len__(self):
        return len(self.graph)
    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))
    def get_nodes(self):
        return self.graph.keys()
class Dijkstra(object):
    def __init__(self, graph, start):
        self.g = graph.graph
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0
        self.prev = defaultdict(lambda: None)
        self.Q = []
        heappush(self.Q, (self.dist[start], start))
        while self.Q:
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))
    def shortest_distance(self, goal):
        return self.dist[goal]
    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]
N, M, R = map(int, input().split())
r = map(int,input().split())
rlist =list(itertools.permutations(r))
g1 = Graph()
INF = float('inf')
for _ in range(M):
    a, b, c = map(int, input().split())
    g1.add_edge(a - 1, b - 1, c)
anslist=[]
for r in rlist:
    score = 0
    for num in range(len(r)-1):
        score+=Dijkstra(g1, r[num]-1).shortest_distance(r[num+1]-1)
    anslist.append(score)
print(min(anslist))

Submission status: Wrong Answer

Solution code:
#074-D

def dijkstra(s):
    d[s]=0
    while True:
        v=-1
        for u in range(n):
            if not used[u] and (v==-1 or d[u]<d[v]):
                v=u
        if v==-1:
            break
        used[v]=True
        for u in range(n):
            d[u]=min(d[u],d[v]+cost[v][u])
    return d
#Union-Find木
par=[]
rank=[]
def init(a): #初期化
    for i in range(a):
        par.append(i)
        rank.append(0)
def find(x): #根を見つける
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
    return par[x]
def unite(x,y): #併合
    x=find(x)
    y=find(y)
    if rank[x]==rank[y]:
        par[x]=y
    else:
        par[y]=x
        if rank[x]==rank[y]:
            rank[x]+=1
    return
def same(x,y): #同じ集合か判定
    return find(x)==find(y)


n,m,r=map(int,input().split())
rl=list(map(int,input().split()))
for i in range(len(rl)):
    rl[i]-=1
refer={}
for i in range(r):
    refer[rl[i]]=i
cost=[[float("INF") for i in range(n)] for j in range(n)]
for i in range(m):
    f,t,c=map(int,input().split())
    cost[f-1][t-1]=c
    cost[t-1][f-1]=c
cl=[]
for i in range(r):
    d=[float("INF") for i in range(n)]
    used=[False for i in range(n)]
    d=dijkstra(rl[i])
    for j in rl:
        cl.append([d[j],i,refer[j]])
cl.sort()
init(r)
ans=0
for c,f,t in cl:
    if c!=0 and not same(f,t):
        unite(f,t)
        ans+=c
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import heapq as hq
from itertools import permutations
def dijkstra(E, D, start,W):
    q = []
    V = [-1]*N
    V[start] = 0
    for i in range(start):
        V[i] = W[i][start]
        for e in E[i]:
            if e > start:
                hq.heappush(q, (V[i] + D[(i,e)], e))
    for e in E[start]:
        if V[e] == -1:
            hq.heappush(q, (D[start, e],e))
    # print(V, q)
    while q:
        d, v = hq.heappop(q)
        if V[v] >= 0:
            continue
        V[v] = d
        for e in E[v]:
            if V[e] == -1:
                hq.heappush(q, (D[v,e]+d, e))
    return V
N, M, r = map( int, input().split())
R = list( map( int, input().split()))
d = defaultdict( int)
E = [ [] for _ in range(N)]
for _ in range(M):
    a, b, c = map( int, input().split())
    a, b = a-1, b-1
    d[(a,b)] = d[(b,a)] = c
    E[a].append(b)
    E[b].append(a)
W = [ [-1]*N for i in range(N)]
for i in range(N):
    W[i] = dijkstra(E,d,i,W)
    # print(W)
ans = 10**9
# for P in permutations( range(r)):
#     now = R[P[0]]-1
#     cans = 0
#     for i in range(1,r):
#         cans += W[now][R[P[i]]-1]
#         now = R[P[i]]-1
#     if cans < ans:
#         ans = cans
print( ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import heapq as hq
from itertools import permutations
def dijkstra(E, D, start,W):
    q = []
    V = [-1]*N
    V[start] = 0
    for i in range(start):
        V[i] = W[i][start]
        hq.heappush(q, (V[i], i))
    for e in E[start]:
        if V[e] == -1:
            hq.heappush(q, (D[start, e],e))
    while q:
        d, v = hq.heappop(q)
        if V[v] >= 0:
            continue
        V[v] = d
        for e in E[v]:
            if V[e] == -1:
                hq.heappush(q, (D[v,e]+d, e))
    return V
N, M, r = map( int, input().split())
R = list( map( int, input().split()))
d = defaultdict( int)
E = [ [] for _ in range(N)]
for _ in range(M):
    a, b, c = map( int, input().split())
    a, b = a-1, b-1
    d[(a,b)] = d[(b,a)] = c
    E[a].append(b)
    E[b].append(a)
W = [ [-1]*N for i in range(N)]
for i in range(N):
    W[i] = dijkstra(E,d,i,W)
ans = 10**9
for P in permutations( range(r)):
    now = R[P[0]]-1
    cans = 0
    for i in range(1,r):
        cans += W[now][R[P[i]]-1]
        now = R[P[i]]-1
    if cans < ans:
        ans = cans
print( ans)

Submission status: Wrong Answer

Solution code:
n, m, r = list(map(int, input().split()))
rs = list(map(int, input().split()))
# construct map
import numpy as np
dists = np.ones((n + 1, n + 1)) * float('inf')
for _ in range(m):
    a, b, c = list(map(int, input().split()))
    dists[a, b] = dists[b, a] = c

from itertools import product, permutations
for i, j in product(range(1, 1 + n), repeat=2):
    for k in range(j + 1, n + 1):
        if dists[j, k] > dists[j, i] + dists[i, k]:
            dists[j, k] = dists[k, j] = dists[j, i] + dists[i, k]

ans = float('inf')

print(ans)

Submission status: Wrong Answer

Solution code:
n, m, r = list(map(int, input().split()))
rs = list(map(int, input().split()))
# construct map
import numpy as np
dists = np.ones((n + 1, n + 1)) * float('inf')
for _ in range(m):
    a, b, c = list(map(int, input().split()))
    dists[a, b] = dists[b, a] = c

from itertools import product, permutations
for i, j, k in product(range(n), repeat=3):
    if dists[j, k] > dists[j, i] + dists[i, k]:
        dists[j, k] = dists[j, i] + dists[i, k]

ans = float('inf')
for path in permutations(rs):
    val = sum(dists[i, j] for i, j in zip(path, path[1:]))
    val = int(val)
    if val < ans:
        ans = val

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
INF = 10 ** 20
n, m, r = map(int, input().split())
rList = list(map(int, input().split()))

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

def dijkstra(start):
    dist = [INF] * n
    dist[start] = 0
    que = []
    heappush(que, (0, start))
    while que:
        time, node = heappop(que)
        for to, cost in edges[node]:
            newTime = time + cost
            if newTime < dist[to]:
                dist[to] = newTime
                heappush(que, (newTime, to))
    return dist

rDist = [[] for _ in range(r)]
for i in range(r):
    dist = dijkstra(rList[i] - 1)
    rDist[i] = [dist[j - 1] for j in rList]

dic = {}
end = 2 ** r - 1
def minCost(state, pos):
    if state in dic:
        return dic[state]
    if state == end:
        return 0

    mask = 1
    ret = INF
    for to in range(r):
        if state & mask:
            mask <<= 1
            continue

        newState = state | mask
        ret = min(ret, rDist[pos][to] + minCost(newState, to))
        mask <<= 1

    dic[state] = ret
    return ret

print(min([minCost(2 ** i, i) for i in range(r)]))

Submission status: Wrong Answer

Solution code:
from itertools import permutations
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
G = [[10**6]*(N+1) for _ in range(N+1)]
for _ in range(M):
    a, b, c = map(int, input().split())
    G[a][b] = c
    G[b][a] = c

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


ans = 10**18
for elem in permutations(r):
    res = 0
    for i in range(R-1):
        res += G[elem[i]][elem[i+1]]
    ans = min(ans, res)
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()))
G = [[10**6]*(N+1) for _ in range(N+1)]
for _ in range(M):
    a, b, c = map(int, input().split())
    G[a][b] = c
    G[b][a] = c

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


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

Submission status: Wrong Answer

Solution code:
from itertools import permutations
import sys


input = sys.stdin.readline


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

dest = [x-1 for x in map(int, input().split())]


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


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


ans = inf
for l in permutations(dest):
    tmp = 0
    for u, v in zip(l, l[1:]):
        tmp += mat[u][v]
    ans = min(ans, tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
import sys


input = sys.stdin.readline


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

dest = [x-1 for x in map(int, input().split())]


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


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


ans = inf
# for l in permutations(dest):
#    tmp = 0
#    for u, v in zip(l, l[1:]):
#        tmp += mat[u][v]
#    ans = min(ans, tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
import sys


input = sys.stdin.readline


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

dest = [x-1 for x in map(int, input().split())]


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


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


ans = inf
# for l in permutations(dest):
#    tmp = 0
#    for u, v in zip(l, l[1:]):
#        tmp += mat[u][v]
#    ans = min(ans, tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
import copy

class warshallFloyd:
    def __init__(self, adj):
        # math.infはpython3.5以降のみ使用可能
        self.inf = 10 ** 9
        self.dis = copy.deepcopy(adj)
        for i in range(len(adj)):
            for j in range(len(adj)):
                if i != j and adj[i][j] == 0:
                    self.dis[i][j] = self.inf

    # 全ての頂点間の最短距離を算出、
    def search(self):
        for k in range(len(self.dis)):
            for i in range(len(self.dis)):
                for j in range(len(self.dis)):
                    if self.dis[i][j] > self.dis[i][k] + self.dis[k][j]:
                        self.dis[i][j] = self.dis[i][k] + self.dis[k][j]
        return self.dis


def func(n, m, r, adj):
    war = warshallFloyd(adj)
    dis = war.search()
    exit()

    def depth(visited, prev, last):
        if last == 0:
            # print("visited:{} prev:{}, last:{}".format(
                # visited, r[prev], last))
            return 0
        add = war.inf
        for i in range(len(visited)):
            if not visited[i]:
                _visited = copy.deepcopy(visited)
                _visited[i] = True
                add = min(add, dis[r[prev]][r[i]] + depth(_visited, i, last - 1))
                # print("add:{}".format(add))
        return add

    _min = war.inf
    for i in range(len(r)):
        # iをスタートとする
        visited = [False for _ in range(len(r))]
        visited[i] = True
        _min = min(_min, depth(visited, i, len(r) - 1))
    return str(_min)

n, m, R = [int(i) for i in input().split()]
r = [int(i) - 1 for i in input().split()]
adj = [[0 for _ in range(n)] for _ in range(n)]
for i in range(m):
    a, b, c = [int(i) for i in input().split()]
    adj[a - 1][b - 1] = c
    adj[b - 1][a - 1] = c
print(func(n, m, r, adj))
"""
print("2 vs "+func(3, 3, [0, 1, 2], [[0, 1, 4], [1, 0, 1], [4, 1, 0]]))
print("4 vs "+func(3, 3, [0, 2], [[0, 2, 6], [2, 0, 2], [6, 2, 0]]))
print("3 vs "+func(4, 6, [1, 2, 3], [[0, 4, 6, 1], [4, 0, 3, 2], [6, 3, 0, 1], [1, 2, 1, 0]]))
# print("print(func({}, {}, {}, {}))".format(n, m, r, adj))
"""

Submission status: Wrong Answer

Solution code:
from itertools import permutations

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

r=list(map(int,input().split()))

for i in range(len(r)):
    r[i]-=1
    
A=[]
a=[]
for i in range(N):
    for j in range(N):
        a.append(1000000)
    A.append(a)
    a=[]
#print(A)

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

for c in range(N):
    for a in range(N):
        for b in range(N):
            A[a][b]=min(A[a][b],A[a][c]+A[c][b])
#print(A)

ans=10000000
for i in permutations(r,len(r)):
    cnt=0
    for j in range(len(i)-1):
        cnt+=A[i[j]][i[j+1]]
    if ans>cnt:
        ans=cnt
print(ans)

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import floyd_warshall
from itertools import permutations
n,m,r=map(int, input().split())
s=[[10**9]*n for i in range(n)]
t=list(map(int, input().split()))
for i in range(m):
    a,b,c=map(int, input().split())
    s[a-1][b-1]=c
    s[b-1][a-1]=c

s=floyd_warshall(s)   
ans=float('inf')
for i in permutations(t):
    an=0
    for j in range(r-1):
        an+=s[i[j]-1][i[j+1]-1]
    ans=min(ans,an)
print(ans)

Submission status: Wrong Answer

Solution code:
n,m,r=map(int, input().split())
s=[[100000]*n for i in range(n)]
t=list(map(int, input().split()))
for i in range(m):
    a,b,c=map(int, input().split())
    s[a-1][b-1]=c
    s[b-1][a-1]=c
 
for k in range(n):
    for i in range(n):
        for j in range(n):
            s[i][j]=min(s[i][j],s[i][k]+s[k][j])
ans=float('inf')
from itertools import permutations
for i in permutations(t):
    an=0
    for j in range(r-1):
        an+=s[i[j]-1][i[j+1]-1]
    ans=min(ans,an)
print(ans)

Submission status: Wrong Answer

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

for k in range(n):
    for i in range(n):
        for j in range(n):
            s[i][j]=min(s[i][j],s[i][k]+s[k][j])
ans=10**9
from itertools import permutations
for i in permutations(t):
    an=0
    for j in range(r-1):
        an+=s[i[j]-1][i[j+1]-1]
    ans=min(ans,an)
print(ans)

Submission status: Wrong Answer

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

for k in range(n):
    for i in range(n):
        for j in range(n):
            s[i][j]=min(s[i][j],s[i][k]+s[k][j])
ans=10000000
from itertools import permutations
for i in permutations(t):
    an=0
    for j in range(r-1):
        an+=s[i[j]-1][i[j+1]-1]
    ans=min(ans,an)
print(ans)

Submission status: Wrong Answer

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

for k in range(n):
    for i in range(n):
        for j in range(n):
            s[i][j]=min(s[i][j],s[i][k]+s[k][j])
ans=0
for i in range(r-1):
    for j in range(i+1,r):
        ans=max(s[t[i]-1][t[j]-1],ans)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations

def wfa(N):
    for i in range(N + 1):
        for j in range(N + 1):
            w_ji = way[j][i]
            for k, (w_ik, w_jk) in enumerate(zip(way[i], way[j])):
                if k == 0:
                    continue
                tmp = w_ji + w_ik
                if w_jk > tmp:
                    way[j][k] = tmp


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

way = [[float("inf") if i != j else 0 for i in range(N + 1)] for j in range(N + 1)]
for m in range(M):
    a, b, c = map(int, input().split())
    way[a][b] = c
    way[b][a] = c


ans = float("inf")
for path in permutations(r):
    time = 0
    for i in range(len(path) - 1):
        time += way[path[i]][path[i + 1]]
    ans = min(ans, time)
print(ans)

Submission status: Wrong Answer

Solution code:
def wf(N, cost):
    for k in range(N):
        for i in range(N):
            c_ik = cost[i][k]
            for j, (c_kj, c_ij) in enumerate(zip(cost[k], cost[i])):
                temp = c_ik + c_kj
                if temp < c_ij:
                    cost[i][j] = temp
                    if k == j:
                        c_ik = temp

import sys
import itertools
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
cost = [[float("inf")] * N for _ in range(N)]
for _ in range(M):
    A, B, C = map(int, sys.stdin.readline().split())
    cost[A - 1][B - 1] = C
    cost[B - 1][A - 1] = C

wf(N, cost)

ans = float('inf')
for place in itertools.permutations(r):
    temp_cost = 0
    current_place = place[0]
    for next_place in place[1:]:
        temp_cost += cost[current_place - 1][next_place - 1]

    if temp_cost < ans:
        ans = temp_cost

print(ans)

Submission status: Wrong Answer

Solution code:
def wf(N, cost):
    for k in range(N):
        for i in range(N):
            c_ik = cost[i][k]
            for j, (c_kj, c_ij) in enumerate(zip(cost[k], cost[i])):
                temp = c_ik + c_kj
                if temp < c_ij:
                    cost[i][j] = temp
                    c_ij = temp

import sys
import itertools
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
cost = [[float("inf")] * N for _ in range(N)]
for _ in range(M):
    A, B, C = map(int, sys.stdin.readline().split())
    cost[A - 1][B - 1] = C
    cost[B - 1][A - 1] = C

wf(N, cost)

ans = float('inf')
for place in itertools.permutations(r):
    temp_cost = 0
    current_place = place[0]
    for next_place in place[1:]:
        temp_cost += cost[current_place - 1][next_place - 1]

    if temp_cost < ans:
        ans = temp_cost

print(ans)

Submission status: Wrong Answer

Solution code:
def wf(N, cost):
    for k in range(N):
        for i in range(N):
            c_ik = cost[i][k]
            for j, (c_kj, c_ij) in enumerate(zip(cost[k], cost[i])):
                temp = c_ik + c_kj
                if temp < c_ij:
                    cost[i][j] = temp

import sys
import itertools
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
cost = [[float("inf")] * N for _ in range(N)]
for _ in range(M):
    A, B, C = map(int, sys.stdin.readline().split())
    cost[A - 1][B - 1] = C
    cost[B - 1][A - 1] = C

wf(N, cost)

ans = float('inf')
for place in itertools.permutations(r):
    temp_cost = 0
    current_place = place[0]
    for next_place in place[1:]:
        temp_cost += cost[current_place - 1][next_place - 1]

    if temp_cost < ans:
        ans = temp_cost

print(ans)

Submission status: Wrong Answer

Solution code:

import queue
from heapq import heappush, heappop

class Graph:

    INF = float('inf')
    
    def __init__(self,v_num,is_directed = False):
        self.is_directed = is_directed
        self.v_num = v_num
        self.E = []
        self.v_s_list = [[] for i in range(self.v_num)]
        
    def appendEdge(self,v1,v2,weight=1):
        if max(v1,v2,self.v_num-1)>=self.v_num or min(v1,v2)<0:
            print("ERROR: The vertex ID is wrong.")
            return False

        self.E.append([v1,v2,weight])
        
        if self.is_directed:
            self.v_s_list[v1].append([v2,weight])
        else:
            self.v_s_list[v1].append([v2,weight])
            self.v_s_list[v2].append([v1,weight])
        
        
    def BFS(self,v,usage="SSSP"):
        is_processed = [False for i in range(self.v_num)]
        distance_list = [Graph.INF for i in range(self.v_num)]
        Q = queue.Queue()
        Q.put(v)
        is_processed[v]=True
        distance_list[v] = 0
        while not Q.empty():
            v1 = Q.get()
            for v2 in self.v_s_list[v1]:
                if not is_processed[v2[0]]:
                    is_processed[v2[0]] = True
                    distance_list[v2[0]] = min(distance_list[v1]+1,distance_list[v2[0]])
                    Q.put(v2[0])
        if usage=="SSSP":
            return distance_list
        elif usage=="ConnectedComponent":
            cc_list = []
            for i in range(self.v_num):
                if is_processed[i]:
                    cc_list.append(i)
            return cc_list

    def getSSSPwithBFS(self,v):
        return self.BFS(v,"SSSP")
        
    def getConnectedComponent(self,v):
        return self.BFS(v,"ConnectedComponent")
        
    def getSSSPwithBellmanFord(self,v):
        distance_list = [Graph.INF for i in range(self.v_num)]
        distance_list[v] = 0
        pre_list = [None for i in range(self.v_num)]

        for i in range(self.v_num-1):
            for e in self.E:
                v1 = e[0]
                v2 = e[1]
                d = e[2]
                if distance_list[v2] > distance_list[v1] + d:
                    distance_list[v2] = distance_list[v1] + d
                    pre_list[v2] = v1
                    
        negative_loop_list = [False for i in range(self.v_num)]
        
        for i in range(self.v_num):
            for e in self.E:
                v1 = e[0]
                v2 = e[1]
                d = e[2]
                if d + distance_list[v1] < distance_list[v2]:
                    distance_list[v2] = d + distance_list[v1]
                    pre_list[v2] = v1
                    negative_loop_list[v2] = True
        
        return distance_list, pre_list, negative_loop_list

    def getSSSPwithDijkstra(self,v):
        distance_list = [Graph.INF for i in range(self.v_num)]
        distance_list[v] = 0
        pre_list = [None for i in range(self.v_num)]
        
        PQ = []
        for i in range(self.v_num):
            heappush(PQ,(distance_list[i],i))
        while len(PQ)>0:
            d,v1 = heappop(PQ)
            for v2 in self.v_s_list[v1]:
                if distance_list[v2[0]] > d + v2[1]:
                    distance_list[v2[0]] = d + v2[1]
                    pre_list[v2[0]] = v1
                    heappush(PQ,(distance_list[v2[0]],v2[0]))
        return distance_list,pre_list
    

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

r = list(map(int,input().split()))

G=Graph(N)

for i in range(M):
    a,b,c = list(map(int,input().split()))
    G.appendEdge(a-1,b-1,c)
    
import itertools

r_perm = list(itertools.permutations(r))

sssp_list = []

for i in range(N):
    distance_list,prev_list = G.getSSSPwithDijkstra(i)
    sssp_list.append(distance_list)

min_score = 10**27+1
for r_a in r_perm:
    prev=r_a[0]-1
    score = 0
    for i in range(1,len(r_a)):
        score+=sssp_list[prev][r_a[i]-1]
    if min_score > score:
        min_score = score

print(min_score)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
N, M, R = map(int, input().split())
r = list(map(lambda x: int(x) - 1, input().split()))
G = [[0] * N for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    G[a][b] = c
    G[b][a] = 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])

# 街の訪れ方を全探索
ans = float('inf')
for perm in permutations(r):
    tmp = 0
    for i in range(R - 1):
        tmp += G[perm[i]][perm[i + 1]]
    ans = min(ans, tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

def search(now,r,dist,ans):
    if len(r)==0:
        return ans
    min_=float('inf')
    for i,x in enumerate(r):
        if i < len(r)-1:
            min_=min(min_,search(x,r[:i]+r[i+1:],dist,ans+dist[now][x]))
        else:
            min_=min(min_, search(x,r[:i],dist,ans+dist[now][x]))
    return min_

N,M,R=list(map(int,input().split()))
r=list(map(int,input().split()))
r=[x-1 for x in r]
dist=[[float('inf') for _ in range(N)] for _ in range(N)]
for i in range(M):
    A,B,C=list(map(int,input().split()))
    dist[A-1][B-1]=C
    dist[B-1][A-1]=C
for i in range(N):
    dist[i][i]=0
dist=np.array(dist)

ans=float('inf')
for i in range(N):
    for j in range(N):
        dist[i][j]=min(dist[i]+dist[j])

ans=float('inf')
for i,x in enumerate(r):
    if i < len(r)-1:
        ans=min(ans, search(x,r[:i]+r[i+1:],dist,0))
    else:
        ans=min(ans, search(x,r[:i],dist,0))
if ans==float('inf'):
    print(0)
else:
    print(int(ans))

Submission status: Wrong Answer

Solution code:
import numpy as np

def search(now,r,dist,ans):
    if len(r)==0:
        return ans
    min_=float('inf')
    for i,x in enumerate(r):
        if i < len(r)-1:
            min_=min(min_,search(x,r[:i]+r[i+1:],dist,ans+dist[now][x]))
        else:
            min_=min(min_, search(x,r[:i],dist,ans+dist[now][x]))
    return min_

N,M,R=list(map(int,input().split()))
r=list(map(int,input().split()))
r=[x-1 for x in r]
dist=[[float('inf') for _ in range(N)] for _ in range(N)]
for i in range(M):
    A,B,C=list(map(int,input().split()))
    dist[A-1][B-1]=C
    dist[B-1][A-1]=C
for i in range(N):
    dist[i][i]=0
dist=np.array(dist)

ans=float('inf')
for i in range(N):
    for j in range(N):
        dist[i][j]=min(dist[i]+dist[j])

ans=float('inf')
for i,x in enumerate(r):
    if i < len(r)-1:
        ans=min(ans, search(x,r[:i]+r[i+1:],dist,0))
    else:
        ans=min(ans, search(x,r[:i],dist,0))
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

def search(now,r,dist,ans):
    if len(r)==0:
        return ans
    min_=float('inf')
    for i,x in enumerate(r):
        if i < len(r)-1:
            min_=min(min_,search(x,r[:i]+r[i+1:],dist,ans+dist[now][x]))
        else:
            min_=min(min_, search(x,r[:i],dist,ans+dist[now][x]))
    return min_

N,M,R=list(map(int,input().split()))
r=list(map(int,input().split()))
r=[x-1 for x in r]
dist=[[10**6 for _ in range(N)] for _ in range(N)]
for i in range(M):
    A,B,C=list(map(int,input().split()))
    dist[A-1][B-1]=C
    dist[B-1][A-1]=C
for i in range(N):
    dist[i][i]=0
dist=np.array(dist)

ans=float('inf')
for i in range(N):
    for j in range(N):
        dist[i][j]=min(dist[i]+dist[j])

ans=float('inf')
for i,x in enumerate(r):
    if i < len(r)-1:
        ans=min(ans, search(x,r[:i]+r[i+1:],dist,0))
    else:
        ans=min(ans, search(x,r[:i],dist,0))
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

def search(now,r,dist,ans):
    if len(r)==0:
        return ans
    min_=float('inf')
    for i,x in enumerate(r):
        if i < len(r)-1:
            min_=min(min_,search(x,r[:i]+r[i+1:],dist,ans+dist[now][x]))
        else:
            min_=min(min_, search(x,r[:i],dist,ans+dist[now][x]))
    return min_

N,M,R=list(map(int,input().split()))
r=list(map(int,input().split()))
r=[x-1 for x in r]
dist=[[10**5 for _ in range(N)] for _ in range(N)]
for i in range(M):
    A,B,C=list(map(int,input().split()))
    dist[A-1][B-1]=C
    dist[B-1][A-1]=C
for i in range(N):
    dist[i][i]=0
dist=np.array(dist)

ans=float('inf')
for i in range(N):
    for j in range(N):
        dist[i][j]=min(dist[i]+dist[j])

ans=float('inf')
for i,x in enumerate(r):
    if i < len(r)-1:
        ans=min(ans, search(x,r[:i]+r[i+1:],dist,0))
    else:
        ans=min(ans, search(x,r[:i],dist,0))
print(ans)