외판원 순회 문제

해밀턴 사이클은 회전해도 같은 사이클이므로 시작 정점을 $1$로 고정한다.

$D[S][v]$를 정점 $1$에서 출발하여 집합 $S$의 정점을 각각 한 번 방문하고 $v$에서 끝나는 경로의 최소 가중치로 정의한다. 초깃값은 $D[\{1\}][1]=0$이다. $v$에서 아직 방문하지 않은 $u$로 가는 간선이 있으면 $D[S\cup\{u\}][u]$를 $D[S][v]+W_{vu}$로 갱신한다.

모든 정점을 방문한 뒤 마지막 정점에서 $1$로 돌아가는 간선의 가중치를 더한다. 이 값들의 최솟값이 정답이다. 모든 값이 불가능하면 $-1$을 출력한다. 각 상태에 도달한 직전 정점을 저장하면 최적 사이클을 역추적할 수 있다. $0$도 유효한 간선 가중치이므로 간선의 유무는 $-1$인지로 판단한다. 최대 비용은 $18\cdot10^9$이므로 64비트 정수를 사용한다.

시간 복잡도는 $O(N^2 2^N)$, 공간 복잡도는 $O(N2^N)$이다. 서브태스크 $$은 시작 정점을 고정하고 나머지 정점의 모든 순열을 검사할 수도 있다.

Solution written by GPT6