Travelling Salesman Problem

#include<bits/stdc++.h>
#define n 4

using namespace std;

// int n=4;
int dist[n][n] = {
        {0,20,42,25},
        {20,0,30,34},
        {42,30,0,10},
        {25,34,10,0}
};

vector<vector<int> > dp((1<<n), vector<int>(n, -1));
int VISITED_ALL = (1<<n)-1;


int tsp(int mask, int pos){
    if(mask == VISITED_ALL)
        return dist[pos][0];
    if(dp[mask][pos] != -1)
        return dp[mask][pos];
    int d = INT_MAX;
    for(int city=0; city<n; ++city)
        if((mask & (1<<city)) == 0){
            int res = dist[pos][city] + tsp(mask|(1<<city), city);
            d = min(d, res);
        }
    return dp[mask][pos] = d;
}

int main(){
    cout<<tsp(1, 0);
    return 0;
}