OJ Board

Code: Select all

#include <iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;
int n;
int flag[20];
double t[150000];
class pr{
public:
    int x;
    int y;
};
pr a[20];

double quiz()
{
    double v=100000000,v2,dis;
    int in,k,hsh=0;
    for( k=1;k<=n;k++)
    {
        if(flag[k]==0){
            hsh+=(int)pow(2,k); //calculate hash value for table t
            ///cout<<"inside"<<endl;
            in=k;
        }
    }
    //cout<<"hash:in::"<<hsh<<" "<<in<<endl;
    if(t[hsh]!=-1)
        return t[hsh];

    flag[in]=1;
    for( k=1;k<=n;k++)
    {
        if(flag[k]==0)
        {
            flag[k]=1;
            //dis=sqrt(pow(a[in].x-a[k].x,2)+pow(a[in].y-a[k].y,2));
			dis=hypot(a[in].x-a[k].x, a[in].y-a[k].y);
            v2=quiz();
            flag[k]=0;
            if(dis+v2<v)
                v=dis+v2;
        }
    }
    flag[in]=0;
    t[hsh]=v;
    return v;

}
int main()
{

    char s[25];
    int i,caseno=1;

    while(scanf("%d",&n) && n)
    {
        n=2*n;
        for(i=1;i<=n;i++)
        {
            scanf("%s%d%d",s,&a[i].x,&a[i].y);
            flag[i]=0;
        }

        //sort(a,a+i,fun);
		for(i=1;i<=150000;i++)
            t[i]=-1;
        t[0]=0;
        //cout<<"t:"<<t[10]<<endl;

        double v=quiz();


        printf("Case %d: %.2lf\n",caseno++,v);
    }


    return 0;
}