← All solutions

This is a variant of the TSP problem, with some non-standard constraints on the tour. For standard TSP there is a well-known O(n² 2ⁿ ) solution using dynamic programming. It turns out that we can achieve the same time complexity for this problem but we need to do a little more work.

Let s be either the headquarters or the attraction, X be a subset of hotels, and i ∈ X be some hotel. Similarly to the usual DP solution, define C ( X, s, i ) to be the minimum cost of a path that starts in s, goes through all the nodes in X, and ends in i. All such values can be computed using dynamic programming in time O(n² 2ⁿ ).

Next, go over all subsets X of size ⌊h/2⌋ and compute the length of the minimum tour which uses this specific subset as the first ⌊h/2⌋ hotels. Given X, the length of the tour can be computed by composing four paths of the form above (this uses that the graph is undirected; if the graph was directed one would have to compute the length of paths that also end at the headquarters/attraction).