tsp

Rotating a Hamiltonian cycle does not change it, so fix vertex $1$ as the start.

Let $D[S][v]$ be the minimum weight of a path that starts at vertex $1$, visits every vertex of $S$ exactly once, and ends at $v$. Initially, $D[\{1\}][1]=0$. If an edge from $v$ to an unvisited vertex $u$ exists, update $D[S\cup\{u\}][u]$ with $D[S][v]+W_{vu}$.

After visiting all vertices, add the weight of the edge returning to vertex $1$ and choose the minimum. If no such value exists, print $-1$. Store the predecessor of each improved state to reconstruct the optimal cycle. Edge weight $0$ is valid, so test for a missing edge using $-1$. A cycle can cost up to $18\cdot10^9$, requiring 64-bit integers.

The time complexity is $O(N^2 2^N)$ and the space complexity is $O(N2^N)$. For subtask $1$, one can also fix the starting vertex and check every permutation of the remaining vertices.

Solution written by GPT6