Salesman

#include<stdio.h>
#include<utility>
using namespace std;
int const N = 18;
int n;

int dist[N][N];

int cd(pair<int,int> a,pair<int,int > b){
    return (a.first - b.first)*(a.first - b.first) + (a.second - b.second)*(a.second - b.second);
}

int min(int a,int b){
    return (a < b ? a : b);
}

int dp[N][(1<<N)];

int cal(int now , int bit){
    if(bit == (1<<n) - 1){
        return dist[now][0];
    }
    if(dp[now][bit] != -1)return dp[now][bit];
    int ans = 1e9;
    for(int i = 0 ; i < n ; i ++){
        if(!(bit&(1<<i)) && i != now){ //not visitted
            ans = min(ans,cal(i,(bit|(1<<i))) + dist[now][i]);
        }
    }
//  printf("Test (%d,%d) : %d\n",now,bit,ans);
    return dp[now][bit] = ans;
}

int main()
{
    for(int i = 0 ; i < N ; i ++)for(int j = 0 ; j < (1<<N) ; j ++)dp[i][j] = -1;
    scanf("%d ",&n);
    pair<int,int> pos[n];
    for(int i = 0 ; i < n; i ++){
        scanf("%d %d",&pos[i].first , &pos[i].second);
    }
    for(int i = 0 ; i < n ; i ++){
        for(int j = 0 ; j < n ; j ++){
            dist[i][j] = cd(pos[i],pos[j]);
        }
    }

    printf("%d",cal(0,1));
    return 0;
}