def solve(N, M, edges, S, K, TS): cc = CoordinateCompression(TS) v2i, _i2v = cc.compress() # dijkstra from collections import defaultdict distances = defaultdict(dict) ds = one_to_all(S, N, edges) from_start = {} for t in TS: from_start[v2i[t]] = ds[t] for t in TS: ds = one_to_all(t, N, edges) for t2 in TS: distances[v2i[t]][v2i[t2]] = ds[t2] # tsp num_vertex = K SUBSETS = 2 ** num_vertex INF = 9223372036854775807 memo = [[INF] * num_vertex for _s 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])