旅行商问题

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
static const int MAX = 20;
static const int INF = (1 << 20);
int n;
int d[MAX][MAX];
int dp[1 << MAX][MAX];        //记忆化搜索使用的数组 
//已经访问的结点为S，当前位置为v
int rec(int S, int v){
    if(dp[S][v] >= 0) return dp[S][v];
    if(S == (1 << n) - 1 && v == 0){
        //已经访问过所有结点并回到0号点 
        return dp[S][v] = 0;
    }
    int res = INF;
    for(int u = 0; u < n; u++){
        if(!(S >> u & 1)){
            //下一步移动到顶点u 
            res = min(res, rec(S | 1 << u, u) + d[v][u]);
        }
    }
    return dp[S][v] = res;
} 
void solve(){
    memset(dp, -1, sizeof(dp));
    cout  << rec(0, 0) << endl;
}
int main(int argc, char** argv) {
    cin >> n;
    int x;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> x;
            if(x == 0) d[i][j] = INF;
            else d[i][j] = x;    
        }
    }
    solve();
}