P1433 吃奶酪
程序员文章站
2024-01-11 15:48:58
...
#define fr first
#define sc second
const int N=222+5;
int n,m,t;
int i,j,k;
double minn;
pair<double,double> p[N];
double dis[N][N];
bool vis[N];
void DFS(int num,int now,double len) //已经吃过 num 块奶酪,当前处于 now 的位置及本次搜索的答案
{
if(len>=minn) return ; //最优性剪枝
if(num==n){ minn=min(minn,len); return ;}
for(int i=1;i<=n;i++){
if(!vis[i]){
vis[i]=1;
DFS(num+1,i,len+dis[now][i]);
vis[i]=0;
}
}
}
int main()
{
//IOS;
while(cin>>n){
for(i=1;i<=n;i++){
cin>>p[i].fr>>p[i].sc;
}
p[0].fr=p[0].sc=0;
for(i=0;i<=n;i++){
for(j=0;j<=n;j++){
dis[i][j]=sqrt( (p[i].fr-p[j].fr)*(p[i].fr-p[j].fr) + (p[i].sc-p[j].sc)*(p[i].sc-p[j].sc) );
}
}
minn=inf;
DFS(0,0,0);
pf(minn);
}
//PAUSE;
return 0;
}