家人们救命!谁懂啊!!!这道题思路很简单,但是我一开始设置”memset(f,0x3f,sizeof f);”,没有写成”memset(f,127,sizeof f);”,这导致什么呢?前者,就是填充0x3f3f3f3f时之后的每一个f的结果都是一个近似0但是＞0的数,导致结果出错,调了半天,怎么着也没想到是memset置为0x3f3f3f3f的问题(⊙﹏⊙),而每一位置成127,也就是有符号整数8位的最大值127(相当于一个char类型的有符号最大整数范围),也就是0x7f.
欸😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭

#include <bits/stdc++.h>
using namespace std;
using pdd = pair<double,double>;
#define int long long
const int N = 210,M = 1<<15;
int n;
vector<pdd> v;
double f[M][N]/*当前点的状态,当前所在的点*/,w[N][N],ans,a,b;
double dis(double t1,double t2)
{
    double x1 = v[t1].first,y1 = v[t1].second;
    double x2 = v[t2].first,y2 = v[t2].second;
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
signed main()
{
    cin >> n;
    memset(f,129,sizeof(f));
    ans = f[0][0];
    v.push_back({0,0});
    for(int i = 1; i <= n ; i++){
        cin >> a >> b;
        v.push_back({a,b});
    }
    for(int i = 0; i <= n ; i++)
        for(int j = i+1 ; j <= n ; j++){
            w[i][j] = dis(i,j);
            w[j][i] = w[i][j];
        }
    for(int i = 1 ; i <= n ; i++){
        f[1<<(i-1)][i] = w[0][i];
    }
    for(int i = 1 ; i < (1<<n) ; i++) {
        for(int j = 1 ; j <= n ; j++) {//点1,范围1~4 从这个点开始 
            if((i>>(j-1))&1) {
                for(int k = 1 ; k <= n ; k++) {//点2,同理 到这个点 
                    if( ((i>>(k-1))&1) && j!=k) {
                        f[i][k] = min(f[i][k],f[i-(1<<(k-1))][j]+w[j][k]);
                    }
                }
            }
        }
    }
    for(int i = 1 ; i <= n ; i++) ans = min(ans,f[(1<<n)-1][i]);
    printf("%.2lf",ans);
    return 0;
} 

再刷的代码:

#include <bits/stdc++.h>
using namespace std;
const int N = 19,M = 1<<19;
double x[N],y[N],f[M][N],w[N][N],ans = 0x7f7f7f7f;
double dis(int i,int j)
{
    return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
int main() 
{
    int n;cin >> n;
    for(int i = 1 ; i <= n ; i++) {cin >> x[i] >> y[i];}
    x[0] = 0,y[0] = 0;
    memset(f,0x7f,sizeof f);
    for(int i = 0 ; i <= n ; i++) 
        for(int j = i+1 ; j <= n ; j++) {
            w[i][j] = dis(i,j);
            w[j][i] = w[i][j];
        } 
    for(int i = 1 ; i <= n ; i++) f[1<<(i-1)][i] = w[0][i]; 
    for(int i = 1 ; i < (1<<n) ; i++) 
        for(int j = 1 ; j <= n ; j++) 
            if((i>>(j-1))&1) 
                for(int k = 1 ; k <= n ; k++) 
                    if(((i>>(k-1))&1)&&(j!=k)) 
                        f[i][k] = min(f[i][k],f[i-(1<<(k-1))][j]+w[j][k]);
    for(int i = 1 ; i <= n ; i++) ans = min(ans,f[(1<<n)-1][i]);
    cout << fixed << setprecision(2) << ans << endl;
    return 0;
}