不懂就问,0x3f 与 0x7f的区别
查看原帖
不懂就问,0x3f 与 0x7f的区别
784813
SakurajiamaMai楼主2023/8/19 11:18

在memset过程中,我发现0x3f得到的答案是错误的,但是0x7f确实正确的,我记得prim算法0x3f就够了吧?有没有大佬能解释一下?

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int N=1e6+10;
int u,v,n,m,num,cnt,t;
double x[N],y[N],res,g[2000][2000],dis[N];
bool vis[N];
double dist(double x1,double y1,double x2,double y2)
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
double prim()
{
    dis[1]=0;
    for(int i=0;i<n;i++){
        int t=-1;
        for(int j=1;j<=n;j++)//寻找最短距离的点
            if(!vis[j]&&(t==-1||dis[t]>dis[j])) t=j;
        res+=dis[t];
        for(int j=1;j<=n;j++) dis[j]=min(dis[j],g[t][j]);//更新最短距离
        vis[t]=true;
    }
    return res;
}
int main()
{
    cin>>n>>m;
    memset(dis,0x7f,sizeof dis);
    memset(g,0x3f,sizeof g);
    for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            g[i][j]=g[j][i]=dist(x[i],y[i],x[j],y[j]);
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        g[u][v]=g[v][u]=0.0;
    }
    printf("%.2lf",prim());
    return 0;
}


2023/8/19 11:18
加载中...