求助 prim 按模板写的,才分
查看原帖
求助 prim 按模板写的,才分
451563
ruisen楼主2021/7/31 22:31
#include<bits/stdc++.h>
using namespace std;
struct node{
	int x,y;
}q[1050];
double a[1200][1200];
double lowcost[1200];
double sum;
int n,m;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>q[i].x;
		cin>>q[i].y;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(i==j)
			a[i][j]=0;
			else{
				double k=(double)(sqrt((double)(q[i].x - q[j].x)*(q[i].x - q[j].x) + (double)(q[i].y - q[j].y) * (q[i].y - q[j].y)));
				a[i][j]=k;
				a[j][i]=k;
			}
		}
	}
	for(int i=1;i<=m;i++)
	{
		int c,d;
		cin>>c>>d;
		a[c][d]=0;
		a[d][c]=0;
	}
	lowcost[1]=-1;
	for(int i=2;i<=n;i++)
	{
		lowcost[i]=a[1][i];
	}
	for(int i=2;i<=n;i++)
	{
		double Min=0x7f;
		int j=1,k=0;
		while(j<=n)
		{
			if(lowcost[j]!=-1&&lowcost[j]<Min){
				Min=lowcost[j];
				k=j;
			}
			j++;	
		}
		sum+=Min;
		lowcost[k]=-1;
		for(int j=1;j<=n;j++)
		{
			if(lowcost[j]!=-1&&a[k][j]<lowcost[j])
			{
				lowcost[j]=a[k][j];
			}
		}	
	}
	printf("%.2lf",sum);
	return 0;
}
2021/7/31 22:31
加载中...