Bitonic Tour

View a valid tour as two increasing paths from vertex $1$ to vertex $N$. They share only their endpoints.

Let $D[i][j]$ be the minimum total weight of two such paths after assigning vertices $1$ through $j$, with endpoints $i$ and $j$ ($i<j$). Initially, $D[1][2]=W_{12}$. When adding $j$, if $i<j-1$, append $j$ after $j-1$, giving $D[i][j]=D[i][j-1]+W_{j-1,j}$. For $i=j-1$, append $j$ after the other path's endpoint $k<j-1$, giving $D[j-1][j]=\min_{k<j-1}(D[k][j-1]+W_{k,j})$. Missing edges cannot be used.

After processing every vertex, connect endpoints $i$ and $N$. The minimum of $D[i][N]+W_{i,N}$ is the answer. Store the previous endpoint $k$ chosen for each $D[j-1][j]$ to trace the selected edges backward and reconstruct both paths. If no tour exists, print $-1$. Edge weight $0$ is valid, so use $-1$ to identify a missing edge. A tour can cost up to $2\,000\cdot10^9$, requiring 64-bit integers.

The time and space complexities are both $O(N^2)$. For subtask $1$, one may enumerate every assignment of intermediate vertices to the two paths.

Solution written by GPT6