prim+链式前向星 50分RE求助
查看原帖
prim+链式前向星 50分RE求助
696711
pengrongxuan楼主2023/9/1 22:03
#include<bits/stdc++.h>
#define int long long
#define MAXN 5100000
#define inf 127
using namespace std;
typedef double du;
struct EDGE
{
	int to,nxt;
	du w;
};
EDGE edge[MAXN];
priority_queue<pair<du,int> > q;
int tot,n,x,y,cnt,xx[MAXN],yy[MAXN],head[MAXN],vis[MAXN];
du z,ans,d[MAXN];
inline int read()
{
	int f=1,k=0;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')
		  f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		k=(k<<1)+(k<<3)+(c^48);
		c=getchar();
	}
	return f*k;
}
du juli(int x1,int y1,int x2,int y2)
{
	return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}
void add(int u,int v,du w)
{
	edge[++tot].to=v;
	edge[tot].w=w;
	edge[tot].nxt=head[u];
	head[u]=tot;
}
void prim(int s)
{
	memset(d,inf,sizeof(d));
	d[s]=0;
	q.push(make_pair(0,s));
	while(!q.empty())
	{
		int u=q.top().second;
		q.pop();
		if(vis[u])
		  continue;
		vis[u]=1;
		cnt++;
		ans+=d[u];
		for(int i=head[u];i;i=edge[i].nxt)
		{
			int v=edge[i].to;
			du w=edge[i].w;
			if(d[v]>w)
			{
				d[v]=w;
				q.push(make_pair(-d[v],v));
			}
		}
	}
}
signed main()
{
	n=read();
	for(int i=1;i<=n;i++)
	{
		xx[i]=read();
		yy[i]=read();
	}
	for(int i=2;i<=n;i++)
	{
		for(int j=1;j<=i-1;j++)
		{
			du w=juli(xx[i],yy[i],xx[j],yy[j]);
			add(i,j,w);
			add(j,i,w);
		}
	}
	prim(1);
	printf("%.2lf",ans);
	return 0;
}

2023/9/1 22:03
加载中...