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 numpy as np
import itertools

N,M,R=map(int,input().split())
R = [ int(i) for i in input().split()]
ABC = [np.array(list(map(int,input().split()))) for _ in range(M)]
inf = 10**6
rs = [np.array([inf]*N) for _ in range(N)]

for i in range(M):
    a = ABC[i][0]-1
    b = ABC[i][1]-1
    c = ABC[i][2]
    rs[a][b]=rs[b][a]=c

for i in range(N-1):
    for j, d1 in enumerate(rs[i][i+1:], start=i+1):
        d2 = np.min(rs[i]+rs[j])
        if d1 >= d2:
            rs[i][j] = rs[j][i] = d2

p = list(itertools.permutations(range(N)));
ans = 10**10
for i in p:
    s = 0
    for j in range(N-1):
        s += rs[i[j]][i[j+1]]
    ans = min(ans,s)

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding:utf-8 -*-
import itertools
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
d = [[0 for x in range(N)] for y in range(N)]

ans = 0

for y in range(N):
    for x in range(N):
        d[y][x] = 0 if x == y else float('inf')

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

for k in range(N):
    for y in range(N):
        if d[y][k] == float('inf'):
            continue
        for x in range(N):
            if d[k][x] == float('inf'):
                continue
            d[y][x] = min(d[y][x], d[y][k]+d[k][x])

for tmp in list(itertools.permutations(r)):
    factor = 0
    for tmp2 in range(0, len(tmp)-1):
        if d[tmp[tmp2]-1][tmp[tmp2+1]-1] != 0 and d[tmp[tmp2]-1][tmp[tmp2+1]-1] != float('inf'):
            factor += d[tmp[tmp2]-1][tmp[tmp2+1]-1]
        else:
            break
    ans = min(ans, factor)

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations

n, m, r = [int(x) for x in input().strip().split()]
targets = [int(x) for x in input().strip().split()]

LARGE = 100000 * 201
roads = [[LARGE for _ in range(n+1)] for _ in range(n+1)]
for i in range(n+1):
    roads[i][i] = 0

for _ in range(m):
    a, b, c = [int(x) for x in input().strip().split()]
    roads[a][b] = roads[b][a] = c

# Warshall-Floyd Algorithm
for k in range(1, n+1):
    for i in range(1, n+1):
        d_ik = roads[i][k]
        for j in range(1, n+1):
            d_ij = roads[i][j]
            d_kj = roads[k][j]
            if d_ij > d_ik + d_kj:
                roads[i][j] = roads[j][i] = d_ik + d_kj

Submission status: Wrong Answer

Solution code:
# ワーシャル・フロイド法
# <https://ja.wikipedia.org/wiki/%E3%83%AF%E3%83%BC%E3%82%B7%E3%83%A3%E3%83%AB%E2%80%93%E3%83%95%E3%83%AD%E3%82%A4%E3%83%89%E6%B3%95>

import sys
import itertools

# コマンドライン引き数の取得
args = sys.argv
if len(args) < 2:
    isDebug = False
elif args[1] == 'DEBUG':
    isDebug = True
else:
    isDebug = False


# 宣言
result = sys.maxsize
A_list = []
B_list = []
C_list = []

# 入力補助関数
def read_int_list():
    return list(map(int, input().split()))

# 入力部
if isDebug:
    # sample1
    # (N, M, R) = (3, 3, 3)
    # r = (1, 2, 3)
    # A_list = [1, 2, 3]
    # B_list = [2, 3, 1]
    # C_list = [1, 1, 4]

    # sample2
    # (N, M, R) = (3, 3, 2)
    # r = (1, 3)
    # A_list = [2, 1, 1]
    # B_list = [3, 3, 2]
    # C_list = [2, 6, 2]

    # sample3
    (N, M, R) = (4, 6, 3)
    r = [2, 3, 4]
    r = [x-1 for x in r]

    A_list = [1, 2, 4, 1, 4, 3]
    B_list = [2, 3, 3, 4, 2, 1]
    C_list = [4, 3, 1, 1, 2, 6]

else:
    (N, M, R) = read_int_list()
    r = read_int_list()
    r = [x-1 for x in r]

# 処理部
# グラフ初期化
graph = [[float('inf')]*N for i in range(N)]
for i in range(N):
    graph[i][i] = 0

for i in range(M):
    a, b, c = read_int_list()
    a -= 1
    b -= 1
    graph[a][b] = 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])

# 経路長計算
for root in itertools.permutations(r):
    distance = 0
    for i in range(len(root) - 1):
        distance += graph[root[i]][root[i+1]]                 
    result = min(result, distance)

# 出力部
print(int(result))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python

import sys

p=[0]*10000;mp=[];inf=655360;v=[0]*1000;t=[0]*1000
 
 
ans=1000000

 
n,m,r=map(int,sys.stdin.readline().split(" "))



s=sys.stdin.readline().replace("\n","")

p=map(int,s.split(" "))


def dsss(x,now):
	global ans,v,p,t,mp
	if x==r+1:
		ans=min(ans,now)
		return 
	else :
		for i in range(r):
			if v[p[i]]==0 :
				v[p[i]]=1
				t[x]=p[i]
				if x==1:
					dsss(x+1,now)
				else :
					dsss(x+1,now+mp[p[i]-1][t[x-1]-1])
				v[p[i]]=0
	return 
 
 
for i in range(n+5):
	mp.append(range(n+5))
 
 
for i in range(n+5):
    for j in range(n+5):
        if(i!=j):
            mp[i][j]=inf


for i in range(m):
	a,b,c=map(lambda x: int(x),sys.stdin.readline().split(" ",3))
	a-=1;b-=1;
	mp[a][b]=min(mp[a][b],c)
	mp[b][a]=min(mp[b][a],c)


for i in xrange(n):
	for j in xrange(n):
		for k in xrange(n):
			if mp[j][i]+mp[i][k]<mp[j][k]:
			    mp[j][k]=mp[j][i]+mp[i][k]

dsss(1,0)
 
print ans

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python

import sys

p=[0]*10000;mp=[];inf=65536;v=[0]*1000;t=[0]*1000
 
 
ans=100000

 
n,m,r=map(int,sys.stdin.readline().split(" "))



s=sys.stdin.readline().replace("\n","")

p=map(int,s.split(" "))


def dsss(x,now):
	global ans,v,p,t,mp
	if x==r+1:
		ans=min(ans,now)
		return 
	else :
		for i in range(r):
			if v[p[i]]==0 :
				v[p[i]]=1
				t[x]=p[i]
				if x==1:
					dsss(x+1,now)
				else :
					dsss(x+1,now+mp[p[i]-1][t[x-1]-1])
				v[p[i]]=0
	return 
 
 
for i in range(n+5):
	mp.append(range(n+5))
 
 
for i in range(n+5):
    for j in range(n+5):
        if(i!=j):
            mp[i][j]=inf


for i in range(m):
	a,b,c=map(lambda x: int(x),sys.stdin.readline().split(" ",3))
	a-=1;b-=1;
	mp[a][b]=min(mp[a][b],c)
	mp[b][a]=min(mp[b][a],c)


for i in xrange(n):
	for j in xrange(n):
		for k in xrange(n):
			if mp[j][i]+mp[i][k]<mp[j][k]:
			    mp[j][k]=mp[j][i]+mp[i][k]

dsss(1,0)
 
print ans

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python

import sys

p=[0]*10000;mp=[];inf=65536;v=[0]*1000;t=[0]*1000
 
 
ans=100000

 
n,m,r=map(int,sys.stdin.readline().split(" "))


print "1"

s=sys.stdin.readline().replace("\n","")

p=map(int,s.split(" "))


def dsss(x,now):
	global ans,v,p,t,mp
	if x==r+1:
		ans=min(ans,now)
		return 
	else :
		for i in range(r):
			if v[p[i]]==0 :
				v[p[i]]=1
				t[x]=p[i]
				if x==1:
					dsss(x+1,now)
				else :
					dsss(x+1,now+mp[p[i]-1][t[x-1]-1])
				v[p[i]]=0
	return 
 
 
for i in range(n+5):
	mp.append(range(n+5))
 
 
for i in range(n+5):
    for j in range(n+5):
        if(i!=j):
            mp[i][j]=inf


for i in range(m):
	a,b,c=map(lambda x: int(x),sys.stdin.readline().split(" ",3))
	a-=1;b-=1;
	mp[a][b]=min(mp[a][b],c)
	mp[b][a]=min(mp[b][a],c)


for i in range(n):
	for j in range(n):
		for k in range(n):
			if mp[j][i]+mp[i][k]+mp[j][k]:
			    mp[j][k]=mp[j][i]+mp[i][k]

dsss(1,0)
 
print ans

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python

import sys

p=[0]*10000;mp=[];inf=65536;v=[0]*10;t=[0]*10
 
 
ans=100000

 
n,m,r=map(int,sys.stdin.readline().split(" "))

s=sys.stdin.readline().replace("\n","")

p=map(int,s.split(" "))


def dsss(x,now):
	global ans
	if x==r+1:
		ans=min(ans,now)
		return 
	else :
		for i in range(r):
			if v[p[i]]==0 :
				v[p[i]]=1
				t[x]=p[i]
				if x==1:
					dsss(x+1,now)
				else :
					dsss(x+1,now+mp[p[i]-1][t[x-1]-1])
				v[p[i]]=0
	return 
 
 
for i in range(n+5):
	mp.append(range(n+5))
 
 
for i in range(n+5):
    for j in range(n+5):
        if(i!=j):
            mp[i][j]=inf
 
for i in range(m):
	a,b,c=map(lambda x: int(x),sys.stdin.readline().split(" ",3))
	a-=1;b-=1;
	mp[a][b]=min(mp[a][b],c)
	mp[b][a]=min(mp[b][a],c)
 
for i in range(n):
	for j in range(n):
		for k in range(n):
			mp[j][k]=min(mp[j][k],mp[j][i]+mp[i][k])

print len(p)

dsss(1,0)
 
print ans

Submission status: Wrong Answer

Solution code:
from itertools import permutations

def input_list():
    return list(map(int, input().split()))

def main():
    n, m, r = input_list()
    rlist = input_list()
    rlist = [r-1 for r in rlist]
    d = [[float('inf')]*n for i in range(n)]
    for i in range(n):
        d[i][i] = 0
    
    for i in range(m):
        a, b, c = input_list()
        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):
                distance = d[i][k]+d[k][j]
                if d[i][j] > distance:
                    d[i][j] = distance

    ans = float('inf')
    for p in permutations(rlist):
        distance = 0
        for i in range(r-1):
            distance += d[p[i]][p[i+1]]

    if ans > distance:
        ans = distance

    print(ans)

main()

Submission status: Wrong Answer

Solution code:
class Graph():
	def __init__(self, nodes,directed = False):
		self.nodes = nodes
		self.distances = {}
		self.edges = {}
		for i in nodes:
			self.edges[i] = []

		self.directed = directed

	def addNode(self,node):
		self.nodes.append(node)
		self.edges[node] = []


	def addEdge(self,_from,_to,dis):
		self.edges[_from].append(_to)
		self.distances[(_from,_to)] = dis
		if not(self.directed):
			self.edges[_to].append(_from)
			self.distances[(_to,_from)] = dis

	def msl(self):
		edges = {}
		nodes = set()

		for f,d in self.distances.items():
			if (f[1],f[0],d) not in edges:
				edges[(f[0],f[1],d)] = True

		edges = list(edges.keys())
		edges = sorted(edges,key = lambda x:x[2])
		start = None
		end = None
		mst = []
		for s,e,d in edges:

			if s in nodes and e in nodes:
				continue
			if start is None and end is None:
				start = s
				end = e
			else:
				fixed = False
				if s == start:
					start = e
					fixed = True
				elif s == end:
					end = e
					fixed = True
				if not(fixed):
					if e == start:
						start = s
					elif e == end:
						end = s

			nodes.add(s)
			nodes.add(e)
			mst.append((s,e,d))

		return mst



		
def solution():
	n,m,r = [int(x) for x in input().split(' ')]
	R = [int(x) for x in input().split(' ')]
	g = Graph([i for i in range(1,n+1)])

	for i in range(m):
		arc = [int(x) for x in input().split(' ')]
		g.addEdge(arc[0],arc[1],arc[2])
	
	msl = g.msl()
	ans = 0
	visited = set()
	for s,e,d in msl:
		if (s in R and s not in visited) or (e in R and e not in visited):
			visited.add(s)
			visited.add(e)
			ans += d
	return ans

print(solution())

Submission status: Wrong Answer

Solution code:
class Graph():
	def __init__(self, nodes,directed = False):
		self.nodes = nodes
		self.distances = {}
		self.edges = {}
		for i in nodes:
			self.edges[i] = []

		self.directed = directed

	def addNode(self,node):
		self.nodes.append(node)
		self.edges[node] = []


	def addEdge(self,_from,_to,dis):
		self.edges[_from].append(_to)
		self.distances[(_from,_to)] = dis
		if not(self.directed):
			self.edges[_to].append(_from)
			self.distances[(_to,_from)] = dis

	def msl(self):
		edges = {}
		nodes = set()

		for f,d in self.distances.items():
			if (f[1],f[0],d) not in edges:
				edges[(f[0],f[1],d)] = True

		edges = list(edges.keys())
		edges = sorted(edges,key = lambda x:x[2])
		start = None
		end = None
		mst = []
		for s,e,d in edges:

			if s in nodes and e in nodes:
				continue
			if start is None and end is None:
				start = s
				end = e
			else:
				fixed = False
				if s == start:
					start = e
					fixed = True
				elif s == end:
					end = e
					fixed = True
				if not(fixed):
					if e == start:
						start = s
					elif e == end:
						end = s

			nodes.add(s)
			nodes.add(e)
			mst.append((s,e,d))

		return mst



		
def solution():
	n,m,r = [int(x) for x in input().split(' ')]
	R = [int(x) for x in input().split(' ')]
	g = Graph([i for i in range(1,n+1)])

	for i in range(m):
		arc = [int(x) for x in input().split(' ')]
		g.addEdge(arc[0],arc[1],arc[2])
	
	msl = g.msl()
	ans = 0
	for s,e,d in msl:
		ans += d if s in R or e in R else 0 
	return ans

print(solution())

Submission status: Wrong Answer

Solution code:
class Graph():
	def __init__(self, nodes,directed = False):
		self.nodes = nodes
		self.distances = {}
		self.edges = {}
		for i in nodes:
			self.edges[i] = []

		self.directed = directed

	def addNode(self,node):
		self.nodes.append(node)
		self.edges[node] = []


	def addEdge(self,_from,_to,dis):
		self.edges[_from].append(_to)
		self.distances[(_from,_to)] = dis
		if not(self.directed):
			self.edges[_to].append(_from)
			self.distances[(_to,_from)] = dis

	def msl(self):
		edges = {}
		nodes = set()

		for f,d in self.distances.items():
			if (f[1],f[0],d) not in edges:
				edges[(f[0],f[1],d)] = True

		edges = list(edges.keys())
		edges = sorted(edges,key = lambda x:x[2])
		start = None
		end = None
		mst = []
		for s,e,d in edges:

			if s in nodes and e in nodes:
				continue
			if start is None and end is None:
				start = s
				end = e
			else:
				fixed = False
				if s == start:
					start = e
					fixed = True
				elif s == end:
					end = e
					fixed = True
				if not(fixed):
					if e == start:
						start = s
					elif e == end:
						end = s

			nodes.add(s)
			nodes.add(e)
			mst.append((s,e,d))

		return mst



		
def solution():
	n,m,r = [int(x) for x in input().split(' ')]
	R = [int(x) for x in input().split(' ')]
	g = Graph([i for i in range(1,n+1)])

	for i in range(m):
		arc = [int(x) for x in input().split(' ')]
		g.addEdge(arc[0],arc[1],arc[2])
	
	msl = g.msl()
	ans = 0
	for s,e,d in msl:
		ans += d if s in R or d in R else 0 
	return ans

print(solution())

Submission status: Wrong Answer

Solution code:
if __name__ == '__main__':
    N, M, R = list(map(int, input().split()))
    r = list(map(int, input().split()))
    # ワーシャルフロイド
    d = [[float('inf') for i in range(N)] for i in range(N)]
    for i in range(0, N):
        d[i][i] = 0
    for i in range(M):
        A, B, C = list(map(int, input().split()))
        d[A - 1][B - 1] = C
        d[B - 1][A - 1] = C

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

    mincost = [float('inf') for i in range(N)]
    used = [False for i in range(N)]

    mincost[r[0] - 1] = 0
    ans = 0

    # while True:
    #     v = -1
    #     for tmp_r in r:
    #         # print(tmp_r)
    #         if not used[tmp_r - 1] and (v == -1 or mincost[tmp_r - 1] < mincost[v]):
    #             v = tmp_r - 1
    #
    #     if v == -1:
    #         break
    #
    #     used[v] = True
    #     ans += mincost[v]
    #
    #     for tmp_r in r:
    #         mincost[tmp_r - 1] = min(mincost[tmp_r - 1], d[v][tmp_r - 1])

    print(ans)

Submission status: Wrong Answer

Solution code:
N, M, R = map(int, input().split())
r = list(map(lambda x: int(x) - 1, input().split()))

import numpy as np

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


for k in range(N):
    for i in range(N):
        for j in range(N):
            if array[i, k] + array[k, j] != 0:
                array[i, j] = min(array[i, j], array[i, k] + array[k, j])


def it2():
    from itertools import permutations
    for p in permutations(r):
        pp = iter(p)
        next(pp)
        yield sum(array[a, b] for a, b in zip(p, pp))


print(int(min(it2())))

Submission status: Wrong Answer

Solution code:
from itertools import permutations
 
N,M,R = map(int, input().split())
r = map(int,input().split())
ans = float("inf")

dis = [[float("inf")]*(N+1) for _ in range(N+1)]
for n in range(1, N+1):
	dis[n][n] = 0
for i in range(M):
    Ai, Bi, Ci = map(int, input().split())
    dis[Ai][Bi] = Ci
    dis[Bi][Ai] = Ci
for k in range(1, N+1):    # Warshall-Floyd
    for i in range(1, N+1):
        for j in range(i, N+1):
            if dis[i][j] > dis[i][k] + dis[k][j]:
                dis[i][j] = dis[i][k] + dis[k][j]

for p in permutations(r):
    cnt = 0
    for i in range(len(p)-1):
        cnt += dis[p[i]][p[i+1]]
    ans = min(ans, cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
 
N,M,R = map(int, input().split())
r = map(int,input().split())
 
dis = [[float('inf')]*(N+1) for _ in range(N+1)]
for i in range(1, N+1):
	dis[i][i] = 0
for i in range(M):
    Ai, Bi, Ci = map(int, input().split())
    dis[Ai][Bi] = Ci
    dis[Bi][Ai] = Ci
for k in range(1, N+1):    # Warshall-Floyd
    for i in range(1, N+1):
        for j in range(i, N+1):
            if dis[i][j] > dis[i][k] + dis[k][j]:
                dis[i][j] = dis[i][k] + dis[k][j]
 
ans = float('inf')
for p in permutations(r):
    cnt = 0
    for i in range(len(p)-1):
        cnt += dis[p[i]][p[i+1]]
    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()))
 
dis = [[float('inf')]*(N+1) for _ in range(N+1)]
for i in range(1, N+1):
	dis[i][i] = 0
for i in range(M):
    Ai, Bi, Ci = map(int, input().split())
    if dis[Ai][Bi] > Ci:
        dis[Ai][Bi] = Ci
        dis[Bi][Ai] = Ci
for k in range(1, N+1):    # Warshall-Floyd
    for i in range(1, N+1):
        for j in range(i, N+1):
            if dis[i][j] > dis[i][k] + dis[k][j]:
                dis[i][j] = dis[i][k] + dis[k][j]
 
ans = float('inf')
for p in permutations(r):
    cnt = 0
    for i in range(len(p)-1):
        cnt += dis[p[i]][p[i+1]]
    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()))

dis = [[10e10]*(N+1) for _ in range(N+1)]
for i in range(M):
    Ai, Bi, Ci = map(int, input().split())
    if dis[Ai][Bi] > Ci:
        dis[Ai][Bi] = Ci
        dis[Bi][Ai] = Ci
for k in range(1, N+1):    # Warshall-Floyd
    for i in range(1, N+1):
        for j in range(i, N+1):
            if dis[i][j] > dis[i][k] + dis[k][j]:
                dis[i][j] = dis[i][k] + dis[k][j]

ans = 10e10
for p in permutations(r):
    cnt = 0
    for i in range(len(p)-1):
        cnt += dis[p[i]][p[i+1]]
    ans = min(ans, cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
import scipy.sparse as S
import itertools as i
m=lambda:map(int,input().split())
N,M,_=m()
R=m()
G=S.dok_matrix((N,N))
G.update((lambda x:((next(x)-1,next(x)-1),next(x)))(m())for _ in range(M))
G=S.csgraph.floyd_warshall(G.tocsr(),directed=0)
print(min(sum(G[a-1,b-1]for a,b in zip(p[1:],p))for p in i.permutations(R)))

Submission status: Wrong Answer

Solution code:
n,m,r=map(int,input().split())
r=list(map(int,input().split()))
cost=[[999999999999 if i!=j else 0 for j in range(n)] for i in range(n)]
for _ in range(m):
    a,b,c=map(int,input().split())
    cost[a-1][b-1]=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])            
d=[[cost[x-1][y-1] for x in r] for y in r]
print(max(map(max,d)))

Submission status: Wrong Answer

Solution code:
n,m,r=map(int,input().split())
r=list(map(int,input().split()))
cost=[[999999999999 if i!=j else 0 for j in range(n)] for i in range(n)]
for _ in range(m):
    a,b,c=map(int,input().split())
    cost[a-1][b-1]=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])            
d=[[cost[y-1][x-1] for x in r] for y in r]
print(max(map(max,d)))

Submission status: Wrong Answer

Solution code:
n,m,r=map(int,input().split())
r=list(map(int,input().split()))
cost=[[99999999 if i!=j else 0 for j in range(n)] for i in range(n)]
for _ in range(m):
    a,b,c=map(int,input().split())
    cost[a-1][b-1]=cost[b-1][a-1]=c
for k in range(n):
    cost=[[min(cost[i][j],cost[i][k]+cost[k][j]) for j in range(n)] for i in range(n)]            
d=[[cost[y-1][x-1] for x in r] for y in r]
print(d)
print(max(map(max,d)))

Submission status: Wrong Answer

Solution code:
n,m,r=map(int,input().split())
r=list(map(int,input().split()))
cost=[[99999999 if i!=j else 0 for j in range(n)] for i in range(n)]
for _ in range(m):
    a,b,c=map(int,input().split())
    cost[a-1][b-1]=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])
c=[[cost[y-1][x-1] for x in r] for y in r]
print(max(map(max,c)))

Submission status: Wrong Answer

Solution code:
n,m,r=map(int,input().split())
r=list(map(int,input().split()))
cost=[[99999999 if i!=j else 0 for j in range(n)] for i in range(n)]
for _ in range(m):
    a,b,c=map(int,input().split())
    cost[a-1][b-1]=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])
print(max(map(max,cost)))

Submission status: Wrong Answer

Solution code:
from itertools import permutations
import sys
N, M, R = map(int, sys.stdin.readline().split())
r = [int(i) - 1 for i in sys.stdin.readline().split()]
d = [[10000000 for i in range(N)] for j in range(N)]
for i in range(M):
    A, B, C = map(int, sys.stdin.readline().split())
    d[A-1][B-1] = min(d[A-1][B-1], C)
    d[B-1][A-1] = min(d[A-1][B-1], C)
l = True
for o in permutations(r):
    tmp_l = 0
    for s, e in zip(o[:-1], o[1:]):
        tmp_l = tmp_l + d[s][e]
    if l is True:
        l = tmp_l
    else:
        l = min(l, tmp_l)
print(l)

Submission status: Wrong Answer

Solution code:
import itertools
import sys

def readline():
    return sys.stdin.readline()

def read_int_list():
    return list(map(int, readline().split()))

def read_int():
    return int(readline())

def main():
    N, M, R = read_int_list()

    r = [a-1 for a in read_int_list()]

    d = [[float('inf')]*N for _ in range(N)]

    for _ in range(M):
        a, b, c = read_int_list()
        d[a-1][b-1] = c
        d[b-1][a-1] = c

    for a in range(N):
        d[a][a] = 0

    res = float('inf')

    for i in range(N):
        for j in range(N):
            for k in range(N):
                dd = d[i][k]+d[k][j]
                if dd < d[i][j]:
                    d[i][j] = min(d[i][j], dd)

    for perm in itertools.permutations(r):
        a = 0
        for i in range(len(perm)-1):
            a += d[perm[i]][perm[i+1]]
        res = min(a, res)

    print(res)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]

[N,M,R]=i2()
r=i2()
f=2**20
d=[[f for j in range(N)]for i in range(N)]
for i in range(N):d[i][i]=0
for i in range(M):
    a=i2()
    d[a[0]-1][a[1]-1]=a[2]
    d[a[1]-1][a[0]-1]=a[2]
for i in range(N):
    for j in range(N):
        for k in range(N):
            d[j][k]=min(d[j][k],d[j][i]+d[i][k])

c=2**23

import itertools
for i in list(itertools.permutations(r)):
    ddd=0
    for j in range(len(i)-1):
       ddd+=d[i[j]-1][i[j+1]-1]
    c=min(c,ddd)

print(c)

Submission status: Wrong Answer

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]

[N,M,R]=i2()
r=i2()
f=2**20
d=[[f for j in range(N)]for i in range(N)]
for i in range(N):d[i][i]=0
for i in range(M):
    a=i2()
    d[a[0]-1][a[1]-1]=a[2]
    d[a[1]-1][a[0]-1]=a[2]
for i in range(N):
    for j in range(N):
        for k in range(N):
            d[j][k]=min(d[j][k],d[j][i]+d[i][k])
print(d)
c=2**23

import itertools
for i in list(itertools.permutations(r)):
    ddd=0
    for j in range(len(i)-1):
       ddd+=d[i[j]-1][i[j+1]-1]
    c=min(c,ddd)

print(c)

Submission status: Wrong Answer

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]

[N,M,R]=i2()
r=i2()
f=float("inf")
d=[[f for j in range(N)]for i in range(N)]
for i in range(N):d[i][i]=0
for i in range(M):
    a=i2()
    d[a[0]-1][a[1]-1]=a[2]
    d[a[1]-1][a[0]-1]=a[2]
for i in range(N):
    for j in range(N):
        for k in range(N):
            d[j][k]=min(d[j][k],d[j][i]+d[i][k])
print(d)
c=float("inf")

import itertools
for i in list(itertools.permutations(r)):
    ddd=0
    for j in range(len(i)-1):
       ddd+=d[i[j]-1][i[j+1]-1]
    c=min(c,ddd)

print(c)

Submission status: Wrong Answer

Solution code:
import itertools
def dist(a, b, l):
# 	return (l[a][b]+l[b][a])
	
	if l[a][b] == 0: return (l[b][a])
	if l[b][a] == 0: return (l[a][b])
	
	if l[a][b] > l[b][a]:
		return (l[b][a])
	else:
		return (l[a][b])


# 初期化
ans = float('inf')

#入力
N, M, R = map(int, input().split())		# 5 7 2

r = [int(i) for i in input().split()]	# 1 2 3 4 5 ...
r = list(set(r))


c = [[ans for i in range(N+1)] for j in range(N+1)]
for i in range(N+1):
	c[i][i] = 0

for i in range(1, M+1):
	A, B, C = map(int, input().split())		# 5 7 2
	c[A][B]=C
	c[B][A]=C




## ワーシャルフロイド法
#for k in range(N+1):
#	for i in range(N+1):
#		for j in range(N+1):
#			c[i][j] = min(c[i][j], c[i][k] + c[k][j]);

# ワーシャルフロイド法
for k in range(N+1):
	for i in range(N+1):
		for j in range(i+1, N+1):
			c[i][j] = min(c[i][j], c[i][k] + c[k][j]);


# print(c)
# print(dist(A, B, c))

# for i in range(len(r)-1):
# # 	print(r[i])
# 	ans += dist(r[i], r[i+1], c)

# print(ans)

for l in list(itertools.permutations(r)):
	sum = 0
	for i in range(len(l)-1):
#		sum += dist(l[i], l[i+1], c)
		sum += c[l[i]][l[i+1]]
	
	ans = min(ans, sum)
#	print(l, sum, ans)


print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations

def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, m, r = read_line(int, int, int)

rs = [int(r) for r in input().split()]

costs = {}
for i in range(n + 1):
    costs[i] = {}
    for j in range(n + 1):
        costs[i][j] = 100000 + 1 #float('inf')

for _ in range(m):
    a, b, c = read_line(int, int, int)

    costs[a][b] = costs[b][a] = c

for k in range(n + 1):
    for i in range(n + 1):
        for j in range(n + 1):
            c = costs[i][k] + costs[k][j]
            if costs[i][j] > c:
                costs[i][j] = c

def cost(selected):
    c = 0
    for i in range(len(selected) - 1):
        a = selected[i]
        b = selected[i + 1]
        c += costs[a][b]
    return c

smallest = float('inf')

for p in permutations(rs):
    c = cost(p)
    if smallest > c:
        smallest = c

print(smallest)

Submission status: Wrong Answer

Solution code:
from itertools import permutations

def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, m, r = read_line(int, int, int)

rs = [int(r) for r in input().split()]

costs = {}
for i in range(n + 1):
    costs[i] = {}
    for j in range(n + 1):
        costs[i][j] = 100000 + 1

for _ in range(m):
    a, b, c = read_line(int, int, int)

    costs[a][b] = costs[b][a] = c

for k in range(n + 1):
    for i in range(n + 1):
        for j in range(n + 1):
            c = costs[i][k] + costs[k][j]
            if costs[i][j] > c:
                costs[i][j] = c

def cost(selected):
    c = 0
    for i in range(len(selected) - 1):
        a = selected[i]
        b = selected[i + 1]
        c += costs[a][b]
    return c

smallest = (100000 + 1) * len(rs)

for p in permutations(rs):
    c = cost(p)
    if smallest > c:
        smallest = c
# def f(selected, rest):
#     global smallest
#     if len(rest) == 0:
#         c = cost(selected)
#         if smallest > c:
#             smallest = c
#         # print(selected, c)
#     else:
#         for i in range(len(rest)):
#             r = rest[i]
#             rest_copy = rest[:]
#             del rest_copy[i]
#             f(selected + [r], rest_copy)

# f([], rs)
print(smallest)

Submission status: Wrong Answer

Solution code:
def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, m, r = read_line(int, int, int)

rs = [int(r) for r in input().split()]

costs = {}
for i in range(n + 1):
    costs[i] = {}
    for j in range(n + 1):
        costs[i][j] = 100000 + 1

for _ in range(m):
    a, b, c = read_line(int, int, int)

    costs[a][b] = costs[b][a] = c

for k in range(n + 1):
    for i in range(n + 1):
        for j in range(n + 1):
            c = costs[i][k] + costs[k][j]
            if costs[i][j] > c:
                costs[i][j] = c

def cost(selected):
    c = 0
    for i in range(len(selected) - 1):
        a = selected[i]
        b = selected[i + 1]
        c += costs[a][b]
    return c

smallest = (100000 + 1) * len(rs)

def f(selected, rest):
    global smallest
    if len(rest) == 0:
        c = cost(selected)
        if smallest > c:
            smallest = c
        # print(selected, c)
    else:
        for i in range(len(rest)):
            r = rest[i]
            rest_copy = rest[:]
            del rest_copy[i]
            f(selected + [r], rest_copy)

f([], rs)
print(smallest)

Submission status: Wrong Answer

Solution code:
from itertools import permutations

def read_int_list():
    return list(map(int, input().split()))
    

def floyd_warshall():
            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 dfs(c, las, d):
    global res
    if c == R+1:
        if res > d:
            res = d
        return
    
    for i in range(1,R):
        if used[i] != False:
            used[i] = True
            if las == -1:
                dfs(c+1,i,0)
            else:
                dfs(c+1, i, d+dist[r[las]][r[i]])
            used[i] = False
            
# def permutations():
#     global res
#     for p in permutations(r):
#         s = 0
#         for i in range(R - 1):
#             s += dist[p[i]][p[i + 1]]
#         if s < res:
#             res = s
            
N, M, R = (int(i) for i in input().split())
r = read_int_list()
r = [x - 1 for x in r]
used = [bool]*9
res = float('inf')
dist = [[float("inf") for i in range(201)] for i in range((201))]
for i in range(M):
    a, b, c = (int(i) for i in input().split())
    a -= 1
    b -= 1
    dist[a][b] = c
    dist[b][a] = c

floyd_warshall()
dfs(1,-1,0)

print(res)