62 lines
1.5 KiB
C++
62 lines
1.5 KiB
C++
#include <iostream>
|
||
#include <vector>
|
||
#include <cmath>
|
||
#include <iomanip>
|
||
|
||
using namespace std;
|
||
|
||
// 修改点1：坐标改为 double
|
||
vector<pair<double, double>> points;
|
||
double ans = 1e9;
|
||
|
||
double calc(int last, int now){
|
||
double first = (points[last].first - points[now].first);
|
||
first *= first;
|
||
double second = (points[last].second - points[now].second);
|
||
second *= second;
|
||
return sqrt(first+second);
|
||
}
|
||
|
||
void dfs(vector<bool>& visited, double res, int num, int last){
|
||
// 修改点2：必须加剪枝，否则 n=15 会超时
|
||
if(res >= ans) return;
|
||
|
||
if(num == visited.size()){
|
||
if(res < ans) ans = res;
|
||
return;
|
||
}
|
||
for(int i = 0; i < visited.size(); ++i){
|
||
if(!visited[i]){
|
||
visited[i] = true;
|
||
double s = calc(last, i);
|
||
dfs(visited, res+s, num+1, i);
|
||
visited[i] = false;
|
||
}
|
||
}
|
||
}
|
||
|
||
int main(){
|
||
int n;
|
||
if(!(cin >> n)) return 0;
|
||
|
||
// 修改点3：手动加入起点 (0,0)
|
||
// 这样 points[0] 就是起点，奶酪是 points[1] 到 points[n]
|
||
points.push_back({0, 0});
|
||
for(int i = 0; i < n; ++i){
|
||
double x, y;
|
||
cin >> x >> y;
|
||
points.push_back({x, y});
|
||
}
|
||
|
||
// visited 数组大小应包含起点，但起点默认已访问
|
||
vector<bool> visited(n + 1, false);
|
||
visited[0] = true;
|
||
|
||
// 从起点 (0,0) 开始搜，此时已访问 1 个点（起点），当前位置下标是 0
|
||
dfs(visited, 0, 1, 0);
|
||
|
||
cout << fixed << setprecision(2) << ans << endl;
|
||
|
||
return 0;
|
||
}
|