외판원 순회
시간 제한1초메모리 제한128 MB
정점이 최대 16개인 방향 그래프에서 비트마스크 동적 계획법으로 최소 비용 해밀턴 순환을 구하는 문제입니다.
문제
도시는 1번부터 N번까지 번호가 매겨져 있다. 일부 도시 사이에는 이동할 수 있는 길이 있고, 길이 없는 경우도 있다. 한 외판원이 어떤 도시에서 출발해 모든 도시를 정확히 한 번씩 방문한 뒤 다시 출발 도시로 돌아오는 순회 경로를 계획하려고 한다. 마지막에 출발 도시로 돌아오는 경우만 예외로 하며, 그 외에는 이미 방문한 도시를 다시 방문할 수 없다.
도시 사이의 이동 비용은 행렬 W로 주어진다. W[i][j]는 도시 i에서 도시 j로 이동하는 비용이다. 비용은 방향에 따라 다를 수 있으므로 W[i][j]와 W[j][i]가 같을 필요는 없다. W[i][i]는 항상 0이다. 도시 i에서 도시 j로 이동할 수 없으면 W[i][j]도 0으로 주어진다.
도시의 수 N과 비용 행렬 W가 주어졌을 때, 가능한 순회 경로 중 총비용이 가장 작은 값을 구하라.
입력
첫째 줄에 도시의 수 N이 주어진다. (2 <= N <= 16)
다음 N개의 줄에는 비용 행렬이 주어진다. 각 원소는 이동할 수 있는 경우 1,000,000 이하의 양의 정수이고, 이동할 수 없는 경우 0이다. W[i][j]는 도시 i에서 도시 j로 이동하는 비용을 뜻한다.
항상 순회 경로가 존재하는 입력만 주어진다.
출력
첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다.