HDU 4385

#include<iostream>

#include<cstdio>

#define MAXN 23

#define MAXM 1500000

using namespace std; int x,y; int bx[MAXN],by[MAXN]; int dis[MAXN][MAXN]; int dp[MAXM]; int way[MAXM]; int n; int num; void get_dp(int x) { if (dp[x] != 0)return ; for (int i(0); i<n; ++i) { int k = 1<<i; if (k > x)break; if (x&k) { if (dp[x^k] == 0)get_dp(x^k); if (dp[x] == 0) {

                dp[x] = dp[x^k] + 2*dis[i+1][0];

                way[x] = x^k; } else { if (dp[x] > dp[x^k] + 2*dis[i+1][0]) {

                    dp[x] = dp[x^k] + 2*dis[i+1][0];

                    way[x] = x^k; } } for (int j(i+1); j<n; ++j) { int kk = 1<<j; if (kk > x)break; if (x&kk) { if (dp[x^k^kk] == 0)get_dp(x^k^kk); if (dp[x] > dp[x^k^kk] + dis[i+1][0] + dis[j+1][0] + dis[i+1][j+1]) {

                        dp[x] = dp[x^k^kk] + dis[i+1][0] + dis[j+1][0] + dis[i+1][j+1];

                        way[x] = x^k^kk; } } } } } return ; } void out(int x) { int t(x^way[x]), i(1); while (t != 0) { if (t&1) {  

            num++; if (num < n)cout<<i<<" "; else cout<<i<<endl; }  

        i++;  

        t>>=1; } if (way[x] > 0)out(way[x]); } int main() { int t;

    scanf("%d",&t); for (int i(1); i<=t; ++i) {

        num = 0;

        cout<<"Case "<<i<<":"<<endl;

        memset(dp,0,sizeof(dp));

        scanf("%d%d",&x,&y);

        scanf("%d",&n); for (int j(1); j<=n; ++j) {

            scanf("%d%d",&bx[j],&by[j]); } for (int j(1); j<=n; ++j) { for (int k(j+1); k<=n; ++k) {

                dis[j][k] = dis[k][j] = (bx[k] - bx[j])*(bx[k] - bx[j]) + (by[k] - by[j])*(by[k] - by[j]); } } for (int j(1); j<=n; ++j) {

            dis[j][0] = (bx[j] - x)*(bx[j] - x) + (by[j] - y)*(by[j] - y); }        

        get_dp((1<<n)-1);

        cout<<dp[(1<<n)-1]<<endl;

        out((1<<n)-1); } return 0; }