조건을 만족하는 투어를 정점 에서 으로 가는 서로 겹치지 않는 두 증가 경로로 나누어 생각한다. 두 경로는 양 끝점 만 공유한다.
를 부터 까지의 정점을 두 경로에 배분했을 때, 두 경로의 끝점이 각각 인 최소 가중치로 정의한다 (). 처음에는 이다. 새 정점 를 추가할 때 이면 뒤에 를 붙여 가 된다. 이면 다른 경로의 끝점 뒤에 를 붙이므로 이다. 존재하지 않는 간선은 사용할 수 없다.
모든 정점을 처리한 뒤 끝점 와 을 연결한다. 의 최솟값이 답이다. 각 를 갱신한 직전 끝점 를 저장하면 선택한 간선들을 거슬러 올라가 두 경로를 복원할 수 있다. 두 경로를 이어 방문 순서를 출력한다. 불가능한 상태는 충분히 큰 값으로 관리하고, 답이 없으면 을 출력한다. 가중치가 인 간선도 존재하므로 간선의 유무는 인지로 판단한다. 최댓값은 이므로 64비트 정수를 사용한다.
시간 복잡도는 , 공간 복잡도는 이다. 서브태스크 은 중간 정점들을 두 경로에 배분하는 모든 방법을 열거해도 된다.
Solution written by GPT6
