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 collections import Counter

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()]

cities = Counter()

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 a in range(n + 1):
        for b in range(n + 1):
            c = costs[a][k] + costs[k][b]
            if costs[a][b] > c:
                costs[a][b] = 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 collections import Counter

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()]

cities = Counter()

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 a in range(n + 1):
        for b in range(n + 1):
            c = costs[a][k] + costs[k][b]
            if costs[a][b] > c:
                costs[a][b] = 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) * n

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 collections import Counter

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()]

cities = Counter()

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 a in range(n + 1):
        for b in range(n + 1):
            c = costs[a][k] + costs[k][b]
            if costs[a][b] > c:
                costs[a][b] = 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

def passing_all_cities(selected):
    for r in rs:
        if r not in selected:
            return False
    return True

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 collections import Counter

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()]

cities = Counter()

routes = {}
costs = {}
for _ in range(m):
    a, b, c = read_line(int, int, int)

    cities[a] = 1
    cities[b] = 1

    if a in routes:
        routes[a][b] = c
    else:
        routes[a] = { b : c }

    if b in routes:
        routes[b][a] = c
    else:
        routes[b] = { a : c }

keys = list(cities.keys())

for a in keys:
    costs[a] = {}
    for b in keys:
        if a in routes and b in routes[a]:
            costs[a][b] = routes[a][b]
        else:
            costs[a][b] = 100000 + 1

for k in keys:
    for a in keys:
        for b in keys:
            c = costs[a][k] + costs[k][b]
            if costs[a][b] > c:
                costs[a][b] = 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

def passing_all_cities(selected):
    for r in rs:
        if r not in selected:
            return False
    return True

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]
            if True or cost(selected + [r]) < smallest:
                rest_copy = rest[:]
                del rest_copy[i]
                f(selected + [r], rest_copy)

f([], rs)
print(smallest)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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()]

cities = Counter()

routes = {}
costs = {}
for _ in range(m):
    a, b, c = read_line(int, int, int)

    cities[a] = 1
    cities[b] = 1

    if a in routes:
        routes[a][b] = c
    else:
        routes[a] = { b : c }

    if b in routes:
        routes[b][a] = c
    else:
        routes[b] = { a : c }

keys = list(cities.keys())

for a in keys:
    if a not in costs:
        costs[a] = {}
    for b in keys:
        if a in routes and b in routes[a]:
            costs[a][b] = routes[a][b]
        else:
            costs[a][b] = 100000 + 1

for k in keys:
    for a in keys:
        for b in keys:
            c = costs[a][k] + costs[k][b]
            if costs[a][b] > c:
                costs[a][b] = 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 = cost(rs)

def passing_all_cities(selected):
    for r in rs:
        if r not in selected:
            return False
    return True

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

f([], rs)
print(smallest)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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()]

cities = Counter()

routes = {}
costs = {}
for _ in range(m):
    a, b, c = read_line(int, int, int)

    cities[a] = 1
    cities[b] = 1

    if a in routes:
        routes[a][b] = c
    else:
        routes[a] = { b : c }

    if b in routes:
        routes[b][a] = c
    else:
        routes[b] = { a : c }

keys = list(cities.keys())

for a in keys:
    if a not in costs:
        costs[a] = {}
    for b in keys:
        if a in routes and b in routes[a]:
            costs[a][b] = routes[a][b]
        else:
            costs[a][b] = 100000 + 1

for k in keys:
    for a in keys:
        for b in keys:
            c = costs[a][k] + costs[k][b]
            if costs[a][b] > c:
                costs[a][b] = 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 = cost(rs)

def passing_all_cities(selected):
    for r in rs:
        if r not in selected:
            return False
    return True

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

f([], rs)
print(smallest)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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()]

cities = Counter()

routes = {}
costs = {}
for _ in range(m):
    a, b, c = read_line(int, int, int)

    cities[a] = 1
    cities[b] = 1

    if a in routes:
        routes[a][b] = c
    else:
        routes[a] = { b : c }

    if b in routes:
        routes[b][a] = c
    else:
        routes[b] = { a : c }

keys = list(cities.keys())

for a in keys:
    for b in keys:
        if a not in costs:
            costs[a] = {}
        if b not in costs:
            costs[b] = {}

        if a in routes and b in routes[a]:
            costs[a][b] = routes[a][b]
            costs[b][a] = routes[a][b]
        else:
            costs[a][b] = 100000 + 1
            costs[b][a] = 100000 + 1

for k in keys:
    for a in keys:
        for b in keys:
            c = costs[a][k] + costs[k][b]
            if costs[a][b] > c:
                costs[a][b] = 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 = cost(rs)

def passing_all_cities(selected):
    for r in rs:
        if r not in selected:
            return False
    return True

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

f([], rs)
print(smallest)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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()]

cities = Counter()

routes = {}
costs = {}
for _ in range(m):
    a, b, c = read_line(int, int, int)

    cities[a] = 1
    cities[b] = 1

    if a in routes:
        routes[a][b] = c
    else:
        routes[a] = { b : c }

    if b in routes:
        routes[b][a] = c
    else:
        routes[b] = { a : c }

for a in cities.keys():
    for b in cities.keys():
        if a not in costs:
            costs[a] = {}
        if b not in costs[a]:
            if a in routes and b in routes[a]:
                costs[a][b] = routes[a][b]
            else:
                costs[a][b] = 100000 + 1

keys = list(cities.keys())

for k in keys:
    for a in keys:
        for b in keys:
            c = costs[a][k] + costs[k][b]
            if costs[a][b] > c:
                costs[a][b] = 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 = cost(rs)

def passing_all_cities(selected):
    for r in rs:
        if r not in selected:
            return False
    return True

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

f([], rs)
print(smallest)

Submission status: Wrong Answer

Solution code:
#coding=UTF-8

def search(jun):
    global ans
    global R
    global rrCost
    tmpans=0
    if len(jun)==R:
        mae=jun[0]
        for idx in range(1,R,1):
            ba=jun[idx]
            tmpans += rrCost[mae][ba]
            mae=ba

        if ans==None or tmpans<ans:
            ans=tmpans
    else:
        for me in range(0,R,1):
            if not (me in jun):
                search(jun+[me])

mozir=input()
hyo=mozir.split(' ')
N=int(hyo[0])
M=int(hyo[1])
R=int(hyo[2])

mozir=input()
hyo=mozir.split(' ')
r=[(int(mono)-1) for mono in hyo]

michi=[]
for idx in range(0,M,1):
    mozir=input()
    hyo=mozir.split(' ')
    A=int(hyo[0])-1
    B=int(hyo[1])-1
    C=int(hyo[2])

    michi.append((A,B,C))
    michi.append((B,A,C))

rrCost=[]
for idx in range(0,R,1):
    rrCost.append([None]*R)

for idx in range(0,R,1):
    rrCost[idx][idx]=0

for idr in range(0,R,1):
    deCost=[None]*N
    deCost[r[idr]]=0
    
    miru=[]
    for mono in michi:
        if mono[0] == r[idr]:
            deCost[mono[1]]=mono[2]
            miru.append(mono[1])

            for myon in range(0,R,1):
                if mono[1] == r[myon]:
                    rrCost[idr][myon]=mono[2]
                    rrCost[myon][idr]=mono[2]

    while miru:
        nextmiru=[]
        try:
            rrmax=max(rrCost[idr])
        except:
            rrmax=None
            
        for me in miru:
            preCost=deCost[me]
            for mono in michi:
                if mono[0] == me:
                    tmpCost=preCost+mono[2]
                    if deCost[mono[1]]==None or deCost[mono[1]]>tmpCost:
                        if rrmax==None or tmpCost < rrmax:
                            deCost[mono[1]]=tmpCost
                            nextmiru.append(mono[1])
                            
                            for myon in range(0,R,1):
                                if mono[1] == r[myon]:
                                    rrCost[idr][myon]=tmpCost
                                    rrCost[myon][idr]=tmpCost

        miru=list(set(nextmiru))



ans=None
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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()]

cities = Counter()

routes = {}
costs = {}
for _ in range(m):
    a, b, c = read_line(int, int, int)

    cities[a] = 1
    cities[b] = 1

    if a in routes:
        routes[a][b] = c
    else:
        routes[a] = { b : c }

    if b in routes:
        routes[b][a] = c
    else:
        routes[b] = { a : c }

for a in cities.keys():
    for b in cities.keys():
        if a not in costs:
            costs[a] = {}
        if b not in costs[a]:
            if a in routes and b in routes[a]:
                costs[a][b] = routes[a][b]
            else:
                costs[a][b] = 100000 + 1

keys = list(cities.keys())

for k in keys:
    for a in keys:
        for b in keys:
            c = costs[a][k] + costs[k][b]
            if costs[a][b] > c:
                costs[a][b] = 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

def passing_all_cities(selected):
    for r in rs:
        if r not in selected:
            return False
    return True

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

f([], keys)
print(smallest)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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()]

cities = Counter()

routes = {}
costs = {}
for _ in range(m):
    a, b, c = read_line(int, int, int)

    cities[a] = 1
    cities[b] = 1

    if a in routes:
        routes[a][b] = c
    else:
        routes[a] = { b : c }

    if b in routes:
        routes[b][a] = c
    else:
        routes[b] = { a : c }

for a in cities.keys():
    for b in cities.keys():
        if a not in costs:
            costs[a] = {}
        if b not in costs[a]:
            if a in routes and b in routes[a]:
                costs[a][b] = routes[a][b]
            else:
                costs[a][b] = 100000 + 1

keys = list(cities.keys())

for k in keys:
    for a in keys:
        for b in keys:
            c = costs[a][k] + costs[k][b]
            if costs[a][b] > c:
                costs[a][b] = 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

def passing_all_cities(selected):
    for r in rs:
        if r not in selected:
            return False
    return True

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

f([], rs)
print(smallest)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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()]

cities = Counter()

routes = {}
costs = {}
for _ in range(m):
    a, b, c = read_line(int, int, int)

    cities[a] = 1
    cities[b] = 1

    if a in routes:
        routes[a][b] = c
    else:
        routes[a] = { b : c }

    if b in routes:
        routes[b][a] = c
    else:
        routes[b] = { a : c }

for a in cities.keys():
    for b in cities.keys():
        if a not in costs:
            costs[a] = {}
        if b not in costs[a]:
            if a in routes and b in routes[a]:
                costs[a][b] = routes[a][b]
            else:
                costs[a][b] = 100000 + 1

keys = list(cities.keys())

for k in keys:
    for a in keys:
        for b in keys:
            c = costs[a][k] + costs[k][b]
            if costs[a][b] > c:
                costs[a][b] = 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

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

f([], rs)
print(smallest)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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()]

cities = Counter()

routes = {}
costs = {}
for _ in range(m):
    a, b, c = read_line(int, int, int)

    cities[a] = 1
    cities[b] = 1

    if a in routes:
        routes[a][b] = c
    else:
        routes[a] = { b : c }

    if b in routes:
        routes[b][a] = c
    else:
        routes[b] = { a : c }

for a in cities.keys():
    for b in cities.keys():
        if a not in costs:
            costs[a] = {}
        if b not in costs[a]:
            if a in routes and b in routes[a]:
                costs[a][b] = routes[a][b]
            else:
                costs[a][b] = 100000 + 1

# print('*')

keys = list(cities.keys())

for k in keys:
    for i in keys:
        for j in keys:
            c = costs[a][k] + costs[k][b]
            if a != b and costs[a][b] > c:
                costs[a][b] = c

# print('*')

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

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

f([], keys)
print(smallest)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import permutations


# sys.stdin = open('d1.in')


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


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


def main():
    def floyd_warshall():
        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] = dd

    n, m, r = read_int_list()
    v = read_int_list()
    v = [x - 1 for x in v]
    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 = read_int_list()
        a -= 1
        b -= 1
        d[a][b] = c
        d[b][a] = c
    floyd_warshall()
    res = float('inf')
    for p in permutations(v):
        s = 0
        for i in range(r - 1):
            s += d[p[i]][p[i + 1]]
        if s < res:
            res = s
    print(res)


main()

Submission status: Wrong Answer

Solution code:
from collections import Counter

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()]

cities = Counter()

routes = {}
costs = {}
for _ in range(m):
    a, b, c = read_line(int, int, int)

    cities[a] = 1
    cities[b] = 1

    if a in routes:
        routes[a][b] = c
    else:
        routes[a] = { b : c }

    if b in routes:
        routes[b][a] = c
    else:
        routes[b] = { a : c }

for a in cities.keys():
    for b in cities.keys():
        if a not in costs:
            costs[a] = {}
        if b not in costs[a]:
            if a in routes and b in routes[a]:
                costs[a][b] = routes[a][b]
            else:
                costs[a][b] = 100000 + 1

# print('*')

keys = list(cities.keys())

for k in keys:
    for i in keys:
        for j in keys:
            c = costs[a][k] + costs[k][b]
            if a != b and costs[a][b] > c:
                costs[a][b] = c

# print('*')

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

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

f([], rs)
print(smallest)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import permutations


# sys.stdin = open('d1.in')


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


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


def main():
    def floyd_warshall():
        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] = dd

    n, m, r = read_int_list()
    v = read_int_list()
    v = [x - 1 for x in v]
    d = [[float('inf')] * n for i in range(n)]
    for i in range(m):
        a, b, c = read_int_list()
        a -= 1
        b -= 1
        d[a][b] = c
        d[b][a] = c
    floyd_warshall()
    res = float('inf')
    for p in permutations(v):
        s = 0
        for i in range(r - 1):
            s += d[p[i]][p[i + 1]]
        if s < res:
            res = s
    print(res)


main()

Submission status: Wrong Answer

Solution code:
import sys
from itertools import permutations

# sys.stdin = open('d1.in')


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


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


def main():
    def floyd_warshall():
        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] = dd

    n, m, r = read_int_list()
    v = read_int_list()
    v = [x - 1 for x in v]
    d = [[float('inf')] * n for i in range(n)]
    for i in range(m):
        a, b, c = read_int_list()
        a -= 1
        b -= 1
        d[a][b] = c
        d[b][a] = c
    floyd_warshall()
    res = float('inf')
    for p in permutations(v):
        s = 0
        for i in range(r - 1):
            s += d[p[i]][p[i-1]]
        if s < res:
            res = s
    print(res)


main()

Submission status: Wrong Answer

Solution code:
def wf(n):
    for i in [0]*n:
        for j in [0]*n:
            for k in[0]*n:
                d[j][k] = min(d[j][k], d[j][i] + d[i][k])

import itertools

n, m, r = map(int, input().split())
rl = [int(i) for i in input().split()]
d = [[1000000000000000 for _ in[0]*(n+1)] for _ in[0]*(n+1)]

for _ in[0]*m:
    f, t, c = map(int, input().split())
    d[f][t] = c
    d[t][f] = c

wf(n)

ans = 10000000000000000000
for arr in itertools.permutations(rl):
    t = 0
    for i in range(0, r-1):
        t += d[arr[i]][arr[i+1]]
    ans = min(ans, t)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product


def closest_path_lens(idx___neigh_idxes__dists, idx1):
    INF = 100001 * 201 * 200
    n = len(idx___neigh_idxes__dists)
    idx___visited = [False] * n
    idx___dist = [INF] * n
    idx___dist[idx1] = 0
    for _ in range(n):
        curr_idx = -1
        curr_dist = INF
        for idx, dist in enumerate(idx___dist):
            if dist < curr_dist and not idx___visited[idx]:
                curr_idx = idx
                curr_dist = dist
        idx___visited[curr_idx] = True
        for neigh_idx, dist in idx___neigh_idxes__dists[curr_idx]:
            # print(curr_dist, dist)
            idx___dist[neigh_idx] = min(idx___dist[neigh_idx], curr_dist + dist)
    return idx___dist

def is_valid(path):
    town_idx___visited = [0] * len(list(path))
    zero_dists = 0
    for curr_idx, (idx, dist) in enumerate(path):
        if dist == 0:
            zero_dists += 1
        else:
            town_idx___visited[idx] = 1
            town_idx___visited[curr_idx] = 1
    if zero_dists > 1:
        return False
    elif sum(town_idx___visited) != len(town_idx___visited):
        return False
    else:
        return True

towns_nr, roads_nr, towns_to_visit_nr = (int(x) for x in input().split())
towns_to_visit = [(int(x) - 1) for x in input().split()]
town_idx___neigh_idxes__dists = [set() for _ in range(towns_nr)]
for road_idx in range(roads_nr):
    idx1, idx2, dist = (int(x) for x in input().split())
    idx1 -= 1
    idx2 -= 1
    town_idx___neigh_idxes__dists[idx1].add((idx2, dist))
    town_idx___neigh_idxes__dists[idx2].add((idx1, dist))
ttv_idx___ttv_idx__dist = []
for ttv in towns_to_visit:
    town_idx___dist  = closest_path_lens(town_idx___neigh_idxes__dists, ttv)
    print(town_idx___dist)
    ttv_idx___dist = [town_idx___dist[idx] for idx in towns_to_visit]
    ttv_idx___ttv_idx__dist.append(list(enumerate(ttv_idx___dist)))
ans = 100001 * 201 * 200
for path in product(*ttv_idx___ttv_idx__dist):
    if is_valid(path):
        dists = [x[1] for x in path]
        # print(dists)
        # print(path)
        ans = min(ans, sum(dists))
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations

N, M, R = map(int, raw_input().split())
g = [[0 for x in xrange(N)] for x in xrange(N)]
r = map(int, raw_input().split())
r = [x-1 for x in r]
for m in xrange(0, M):
    A, B, C = map(int, raw_input().split())
    A -= 1
    B -= 1
    g[A][B] = g[B][A] = C
# print g

for k in xrange(N):
    for i in xrange(N):
        for j in xrange(i+1, N):
            g[j][i] = g[i][j] = min(g[j][i], g[i][k]+g[k][j])
# print g

min_d = 10000000000000000
n = len(r)
for rr in permutations(r):
    # print rr
    # d = g[rr[i]][rr[i+1]]
    # for i in xrange(1, n):
    #     for j in xrange(i):
    #         if 
    d = 0
    for i in xrange(n-1):
        d += g[rr[i]][rr[i+1]]
    min_d = min(d, min_d)
print min_d