Samsung-Mr. Kim - TSP

#include <iostream>
using namespace std;

// Input:
// 5 0 0 100 100 70 40 30 10 10 5 90 70 50 20
// 10 39 9 97 61 35 93 62 64 96 39 36 36 9 59 59 96 61 7 64 43 43 58 1 36

// Output:
// 200
// 366

int n, ALL;
int x[15], y[15];
int dp[2050][15];

int dist(int i, int j){
    int sum = 0;
    sum += (x[i] > x[j]) ? (x[i] - x[j]): (x[j] - x[i]);
    sum += (y[i] > y[j]) ? (y[i] - y[j]): (y[j] - y[i]);
    return sum;
}

int tsp(int mask, int pos){
    if(mask == ALL)
        return dist(pos, n);
    if(dp[mask][pos] == -1){
        int ans = 9999;
        for(int i=1; i<n; ++i){
            if((mask & (1<<i)) == 0){
                ans = min(ans, dist(pos, i) + tsp((mask | (1<<i)), i));
            }
        }
        dp[mask][pos] = ans;
    }
    return dp[mask][pos];
}

int main() {
    cin>>n;
    cin>>x[0]>>y[0];
    cin>>x[n+1]>>y[n+1];
    for(int i=1; i<=n; ++i)
        cin>>x[i]>>y[i];
    for(int i=0; i<2050; ++i)
        for(int j=0; j<15; ++j)
            dp[i][j] = -1;
    n++;
    ALL = (1<<n)-1;
    cout<<tsp(1, 0);
    return 0;
}