巡回セールスマン問題

O(x^2 2^x)

既に訪問済みの町 2^x

最後に訪問した町 x

次に訪問する町　x

始点に戻るパターンと戻らないパターンがある

code:python

def tsp_return(num_vertex, distances):

# ABC180E

INF = 9223372036854775807

SUBSETS = 2 ** num_vertex

for subset in range(1, SUBSETS):

for v in range(num_vertex):

for u in range(num_vertex):

mask = 1 << u

if subset & mask:

def tsp_not_return(num_vertex, distances, from_start):

# PAST3M

INF = 9223372036854775807

SUBSETS = 2 ** num_vertex

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

elif subset & mask: # new subset includes v

for u in range(num_vertex):