def tsp_return(num_vertex, distances): # ABC180E INF = 9223372036854775807 SUBSETS = 2 ** num_vertex memo = [[INF] * num_vertex for _i in range(SUBSETS)] memo[0][0] = 0 for subset in range(1, SUBSETS): for v in range(num_vertex): for u in range(num_vertex): mask = 1 << u if subset & mask: memo[subset][v] = min( memo[subset][v], memo[subset ^ mask][u] + distances[u][v]) return memo[-1][0] def tsp_not_return(num_vertex, distances, from_start): # PAST3M INF = 9223372036854775807 SUBSETS = 2 ** num_vertex memo = [[INF] * num_vertex for _i in range(SUBSETS)] for subset in range(1, SUBSETS): for v in range(num_vertex): # new vertex mask = 1 << v if subset == 1 << v: # previous vertex is start memo[subset][v] = min( memo[subset][v], from_start[v]) elif subset & mask: # new subset includes v for u in range(num_vertex): memo[subset][v] = min( memo[subset][v], memo[subset ^ mask][u] + distances[u][v]) return min(memo[-1])