我只是想做壮鸭低劈啊，为什么只有状压没有DP……
原题：
植物大战僵尸这款游戏中，还有个特别有意思的赚钱方式——种花（能长金币的花）。
种出来的金币需要玩家点击才能得到，或者，玩家可以购买一只蜗牛来帮助捡金币。然而，蜗牛爬得慢是众所周知的。所以，场上有若干金币时，蜗牛总是喜欢以最少的行程来捡走所有的金币。
现在告诉你场上n个金币所在位置的坐标，以及蜗牛所在位置，让你求出蜗牛捡走所有金币的最小行程。
n<=16 x、y<=10000
恩这题核心思路是压缩一维状态表示那些花取过了
还要有一维表示当前蜗牛在哪里
然后BFS搞即可
chad说dfs可搞？
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int read(){int z=,mark=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')mark=-; ch=getchar();}
while(ch>=''&&ch<=''){z=(z<<)+(z<<)+ch-''; ch=getchar();}
return z*mark;}
const int oo=;
int power2[]; void get_power2(){power2[]=; for(int i=;i<=;i++)power2[i]=power2[i-]<<;}
int n,xx[],yy[];
double f[][]; int dui[],tou=; bool visited[][];
double get_c(int x,int y){return sqrt(((xx[x]-xx[y])*(xx[x]-xx[y])+(yy[x]-yy[y])*(yy[x]-yy[y]))*1.0);}
void out_ord(int x){for(int i=;i<=n;i++)cout<<(x&),x>>=; cout<<endl;}
void bfs(){
f[][]=; dui[++tou]=; visited[][]=true;
for(int k=;k<=tou;k++){
int now=dui[k]%(n+),ns=dui[k]/(n+);
//out_ord(ns);
for(int i=;i<=n;i++)if(!(ns&power2[i]))
if(f[ns][now]+get_c(now,i)<f[ns|power2[i]][i]){
f[ns|power2[i]][i]=f[ns][now]+get_c(now,i);
if(!visited[ns|power2[i]][i]){
dui[++tou]=i+(ns|power2[i])*(n+);
visited[ns|power2[i]][i]=true;}}
visited[ns][now]=false;}}
int main(){//freopen("ddd.in","r",stdin);
memset(visited,,sizeof(visited));
get_power2();
cin>>n;
for(int i=;i<=(<<n)-;i++)for(int j=;j<=n;j++)f[i][j]=oo;
for(int i=;i<=n;i++) xx[i]=read(),yy[i]=read();
xx[]=read(),yy[]=read();
bfs();
double ans=oo;
for(int i=;i<=n;i++) ans=min(ans,f[(<<n)-][i]);
/*int a=4*(n+1)+power2[4];
cout<<a/(n+1)<<" "<<a%(n+1)<<endl;*/
printf("%.2lf\n",ans);
return ;
}