-
Notifications
You must be signed in to change notification settings - Fork 0
/
9-1.py
31 lines (24 loc) · 778 Bytes
/
9-1.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from itertools import permutations
a = open('9.txt').read().split('\n')
cities = set()
distances = {x.split(' = ')[0]: int(x.split(' = ')[1]) for x in a}
for x in a:
cities |= set(x.split(' = ')[0].split(' to '))
minimum = 999999999999999999999999
def get_distance(a, b):
if ' to '.join([a, b]) in distances:
return distances[' to '.join([a, b])]
elif ' to '.join([b, a]) in distances:
return distances[' to '.join([b, a])]
else:
return None
for x in permutations(cities):
local_minimum = 0
for i in range(len(x) - 1):
distance = get_distance(x[i], x[i + 1])
if distance != None:
local_minimum += distance
else:
break
minimum = min([minimum, local_minimum])
print minimum