蒟蒻70pts求调
查看原帖
蒟蒻70pts求调
686342
Jim_Franklin楼主2023/2/2 22:03
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ri register
const int inf=0x3f3f3f;
inline int rd()
{
	int x=0,y=1;char c=getchar();
	for(;c<'0'||c>'9';c=getchar())if(c=='-')y=-1;
	for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);
	return x*y;
}
const int N=2e3+5;
int u,v,n,m,x[N],y[N];
double ans,path[N][N],dis[N];
bool flag[N]; 
double getdis(int x,int y,int x2,int y2){
	return (double)sqrt((double)abs(x2-x)*abs(x2-x)+(double)abs(y2-y)*abs(y2-y));
}
void slove(int u)
{
	for(int i=1;i<=n;i++)
		if(!flag[i]&&path[i][u]<dis[i])dis[i]=path[i][u];
}
int main()
{
	n=rd();m=rd();
	for(int i=1;i<=n;i++)x[i]=rd(),y[i]=rd(),dis[i]=1e9;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)path[i][j]=getdis(x[i],y[i],x[j],y[j]);
	for(int i=1;i<=m;i++)path[u=rd()][v=rd()]=path[v][u]=0;
	flag[1]=1;dis[1]=0;slove(1);
	for(int i=1;i<n;i++)
	{
		double Min=2e9;
		int t=0;
		for(int j=1;j<=n;j++)
			if(!flag[j]&&dis[j]<Min)Min=dis[j],t=j;
		flag[t]=1;
		slove(t);
	}
	for(int i=1;i<=n;i++)ans+=dis[i];
	printf("%.2lf\n",ans);
	return 0;
}

2023/2/2 22:03
加载中...