SMMR-170: Salesman

#include<stdio.h>
typedef long long int ll;
ll const inf = 1e18;
int start = 0;
struct pos{
    int I,J;
};

ll dist(pos a,pos b){
    return (a.I-b.I)*(a.I-b.I) + (a.J-b.J)*(a.J-b.J);
}

int n;
pos town[20];
ll min(ll a,ll b){
    return (a < b ? a : b);
}

ll dp[20][1<<18];

ll TSP(int u,int visited){
//  printf("Test (%d,%d)\n",u,visited);
    if(visited == (1<<n)-1){ //visit all town
        return (u == start ? 0 : inf);
    }
    if(dp[u][visited] != -1)return dp[u][visited];
    ll ans = inf;
    for(int i = 0 ; i < n ; i ++){
        if((visited & (1<<i)) == 0){ // not visit
        //  printf(" Test go to %d\n",i);
            ans = min(ans,TSP(i,(visited | (1<<i))) + dist(town[u],town[i]));
        }
    }
//  printf("Test (%d,%d) : %lld\n",u,visited,ans);
    return dp[u][visited] = ans;
}



int main()
{
    for(int i = 0 ; i < 20 ; i ++)for(int j = 0 ; j < 1<<18 ; j ++)dp[i][j] = -1;
    scanf("%d",&n);
    for(int i = 0 ; i < n ; i ++){
        scanf("%lld %lld",&town[i].I,&town[i].J);
    }
    printf("%lld",TSP(start,0));
    return 0;
}