50分求助
查看原帖
50分求助
1095652
xiaogongkeainie楼主2024/4/20 22:06

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;
}
2024/4/20 22:06
加载中...