2098 외판원 순회

https://www.acmicpc.net/problem/2098

d[i][j] = 마지막 방문 도시가 i이면서 방문 상태가 j일 때 최소 비용

방문 상태를 비트마스크를 이용해서 정수 하나로 효율적으로 나타낼 수 있다. 시간 복잡도는 O(N^2*2^N)이다.

#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 987654321
using namespace std;
 
int n,w[16][16],d[16][1<<16];
 
int tsp(int now,int visit)
{
    int &ret=d[now][visit];
    if(ret!=-1) return ret;
    if(visit==(1<<n)-1)
        return w[now][0]?w[now][0]:INF;
    ret=INF;
    for(int i=0;i<n;i++)
    {
        if(visit&(1<<i) || !w[now][i]) continue;
        ret=min(ret,tsp(i,visit|(1<<i))+w[now][i]);
    }
    return ret;
}
 
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            scanf("%d",&w[i][j]);
    memset(d,-1,sizeof(d));
    printf("%d\n",tsp(0,1));
    return 0;
}