#include #include #include #include using namespace std; // 修改点1:坐标改为 double vector> 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& 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 visited(n + 1, false); visited[0] = true; // 从起点 (0,0) 开始搜,此时已访问 1 个点(起点),当前位置下标是 0 dfs(visited, 0, 1, 0); cout << fixed << setprecision(2) << ans << endl; return 0; }