Bitonic Tour

조건을 만족하는 투어를 정점 $1$에서 $N$으로 가는 서로 겹치지 않는 두 증가 경로로 나누어 생각한다. 두 경로는 양 끝점 $1,N$만 공유한다.

$D[i][j]$를 $1$부터 $j$까지의 정점을 두 경로에 배분했을 때, 두 경로의 끝점이 각각 $i,j$인 최소 가중치로 정의한다 ($i<j$). 처음에는 $D[1][2]=W_{12}$이다. 새 정점 $j$를 추가할 때 $i<j-1$이면 $j-1$ 뒤에 $j$를 붙여 $D[i][j]=D[i][j-1]+W_{j-1,j}$가 된다. $i=j-1$이면 다른 경로의 끝점 $k<j-1$ 뒤에 $j$를 붙이므로 $D[j-1][j]=\min_{k<j-1}(D[k][j-1]+W_{k,j})$이다. 존재하지 않는 간선은 사용할 수 없다.

모든 정점을 처리한 뒤 끝점 $i$와 $N$을 연결한다. $D[i][N]+W_{i,N}$의 최솟값이 답이다. 각 $D[j-1][j]$를 갱신한 직전 끝점 $k$를 저장하면 선택한 간선들을 거슬러 올라가 두 경로를 복원할 수 있다. 두 경로를 이어 방문 순서를 출력한다. 불가능한 상태는 충분히 큰 값으로 관리하고, 답이 없으면 $-1$을 출력한다. 가중치가 $0$인 간선도 존재하므로 간선의 유무는 $-1$인지로 판단한다. 최댓값은 $2\,000\cdot10^9$이므로 64비트 정수를 사용한다.

시간 복잡도는 $O(N^2)$, 공간 복잡도는 $O(N^2)$이다. 서브태스크 $1$은 중간 정점들을 두 경로에 배분하는 모든 방법을 열거해도 된다.

Solution written by GPT6