在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;
}