cogs 线型网络（状压dp）

/*
需要好大的空间.....
而且lowbit理解的不是很好
先放到博客里 以后慢慢研究
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define inf 999999999;
#define maxn 1050000
using namespace std;
int n,a[maxn];
double x[30],y[30],g[30][30],f[maxn][21],ans=inf;
double Dis(double x1,double y1,double x2,double y2)
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int l(int x)
{
return x&(-x);
}
int main()
{
freopen("linec.in","r",stdin);
freopen("linec.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lf%lf",&x[i],&y[i]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
g[i][j]=Dis(x[i],y[i],x[j],y[j]);
for(int i=0;i<=n;i++)
a[1<<i]=i+1;
for(int i=1;i<(1<<n);i++)if(!a[i])
for(int j=i;j;j-=l(j))//枚举状态i的每一个1 

{
f[i][a[l(j)]]=inf;//更新此状态 
for(int k=i-l(j);k;k-=l(k))
f[i][a[l(j)]]=min(f[i][a[l(j)]],f[i-l(j)][a[l(k)]]+g[a[l(j)]][a[l(k)]]);
}
for(int i=1;i<=n;i++)
ans=min(ans,f[(1<<n)-1][i]);
printf("%.2fn",ans);
return 0;
}