외판원 순회

#include <iostream>
#include <vector>
#define MAXX 17
#define INF 987654321
using namespace std;
 
int n;
int w[MAXX][MAXX], dp[MAXX][1<<MAXX];
int tsp(int cur, int status) {
    //현재 도착한 노드와 순회 상태 저장 
    if (status == (1 << n)-1) {
        //전부 순회한 상태이다. 
        return w[cur][0] == 0 ? INF : w[cur][0]; //처음 시작한 지점과 현재 지점이 연결된 상태인가(처음 지점으로 되돌아가야 하기 때문에)
    }
 
    if (dp[cur][status] != INF) {
        //이미 방문한 지점
        return dp[cur][status];
    }
 
    for (int i = 0; i < n; i++) {
        if ((status & (1 << i)) == 0 && w[cur][i]) {
            //아직 방문 안했고, 갈 수 있는 곳이면 
            dp[cur][status] = min(dp[cur][status], w[cur][i] + tsp(i, (status | (1<<i))));
        }
    }
    return dp[cur][status];
 
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> w[i][j];
        }
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < (1<<n); j++) {
            dp[i][j] = i == j ? 0 : INF;
        }
    }
 
    cout << tsp(0,1) << '\n';
    return 0;
}