2515: 【普及+/提高】【P1433】吃奶酪
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
房间里放着 块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？老鼠一开始在 点处。
输入
第一行有一个整数，表示奶酪的数量 。
第 到第 行，每行两个实数，第 行的实数分别表示第 块奶酪的横纵坐标 。
输出
输出一行一个实数，表示要跑的最少距离，保留 位小数。
样例输入 复制
4
1 1
1 -1
-1 1
-1 -1样例输出 复制
7.41提示
数据规模与约定
对于全部的测试点，保证 ，，小数点后最多有 位数字。
提示
对于两个点 ，，两点之间的距离公式为 。
#include<bits/stdc++.h>
using namespace std;
int n;
double ans = DBL_MAX, f[16][33000] = {0};
struct point {
double x,y;
bool visit;
int num;
}ps[16];
double dis(point p1,point p2) {
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
void dfs (point p,int step,int mark,double s) {
if (step == n) {
if (s < ans ) ans = s;
return;
}
for(int i = 0; i < n; i++) {
if (ps[i].visit) continue;
int tmp = mark + (1<<i);
if (f[i][tmp] == 0 || f[i][tmp] > f[p.num][mark] + dis (ps[i],p)) {
f[i][tmp] = f[p.num][mark] + dis(ps[i],p);
ps[i].visit = true;
dfs(ps[i],step+1,tmp, s+dis(ps[i],p));
ps[i].visit = false;
}
}
}
int main(){
cin >> n;
for(int i = 0; i < n; i++) {
cin >> ps[i].x >> ps[i].y;
ps[i].visit = 0;
ps[i].num = i;
}
point p = {0,0,1,0};
dfs(p,0,0,0);
printf("%.2lf",ans);
return 0;
}