50分,第一个样例输出是17.32,答案是17.15,感觉是浮点数运算出了问题,但我实在看不出来,求大佬解惑
#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<cstring>
#include<deque>
#include<cmath>
#include<set>
#include<map>
#include<unordered_map>
#include<math.h>
#include<algorithm>
#include<iomanip>
#define endl '\n'
using namespace std;
const int inf = 2147483647;
const long long lof = 9223372036854775807;
double dp[15][65535];//以 i 为终点,状态为 j 的路程
struct point {
double x, y;
};
double distance(point& p1, point& p2) {
return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}
int popcount(int x) {
int ans = 0;
while(x != 0) {
if(x & 1)
ans++;
x >>= 1;
}
return ans;
}
void solve() {
int n;
cin >> n;
vector<point> v(n + 1);
point yuandian = {0, 0};
v[0] = yuandian;
for (int i = 1; i <= n; i++) {
double x, y;
cin >> x >> y;
point pp = {x, y};
v[i] = pp;
}
memset(dp, 127, sizeof(dp));
dp[0][0] = 0;
int max_state = pow(2, n) - 1;
for (int j = 1; j <= n; j++) {
int sj = (1 << (j - 1));
dp[j][sj] = distance(v[j], v[0]);
}
for (int k = 2; k <= n; k++) {
for (int i = 1; i < n; i++) {//枚举上一个终点
for (int si = 1; si < max_state; si++) {//枚举上一个终点状态
if(popcount(si) != k - 1 || (i != 0 && ((1 << (i - 1)) & si) != (1 << (i - 1))))
continue;
for(int j = 1; j <= n; j++) {//第 j 个点为终点
int sj = (((1 << (j - 1)) | si) | si);
if(sj == si)
continue;
dp[j][sj] = min(dp[j][sj], dp[i][si] + distance(v[i], v[j]));
}
}
}
}
double ans = inf;
for (int i = 1; i <= n; i++) {
ans = min(ans, dp[i][max_state]);
}
cout << fixed << setprecision(2) << ans << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int t = 1;
//cin >> t;
while(t--) {
solve();
}
return 0;
}