gistfile1.txt

# create a new city (the 0th city), and set distance to every other city to be 0
from copy import deepcopy


def memoize(fn):
    CACHE = {}
    def newfn(*args):
        if tuple(args) not in CACHE:
            CACHE[tuple(args)] = fn(*args)
        return CACHE[tuple(args)]
    return newfn

@memoize
def best(first, second):
    if first == 0 and second == 1: return (0, set(), set([1]))

    low = (float('inf'), set(), set())
    check = [(i, second) for i in range(first)]
    if first != second - 1:
        check.append(first, second - 1)

    for oldfirst, oldsecond in check:
        dist, firstset, secondset = best(*sorted(oldfirst, oldsecond))
        if oldfirst != first: dist += distances[oldfirst][first]
        if oldsecond != second: dist += distances[oldsecond][second]
        if dist < low[0]:
            low = (dist, deepcopy(firstset), deepcopy(secondset))

    return low

print(min([best(i, n) for i in range(n)])[0])