all in a single night

approach

the distances become an undirected adjacency list. there are few enough places to try every route, so a backtracking dfs starts from each node, marks nodes as visited on the way down and unmarks them on the way back, and returns the route length once every node has been used.

the dfs takes the combining function and its starting value as parameters. part 1 calls it with min and inf, part 2 with max and -inf.

the trick

pass min or max into the same search, and both parts are one function.

def dfs(g, n, v, s, nodes, f, init):
    if nodes == 0:
        return s
    res = init
    for nn, w in g[n]:
        if nn not in v:
            v.add(nn)
            res = f(dfs(g, nn, v, s + w, nodes - 1, f, init), res)
            v.remove(nn)
    return res