#2#9#10RE求助
查看原帖
#2#9#10RE求助
605945
luo_xiaoran楼主2023/3/28 13:55
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll now=1,tot,cnt,n,m,head[1010],num[1010][2];
bool vis[1010];
double ans,dis[1010];
struct edge{
	ll v,next;
	double w;
}e[500610];
void add(ll u,ll v,double w){
	e[++cnt].v=v;
	e[cnt].w=w;
	e[cnt].next=head[u];
	head[u]=cnt;
}
int main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&num[i][0],&num[i][1]);
		for(int j=1;j<i;j++){
			double l=double(sqrt(double(double(num[i][0]-num[j][0])*(num[i][0]-num[j][0])+double(num[i][1]-num[j][1])*(num[i][1]-num[j][1]))));
			add(i,j,l);
			add(j,i,l);
		}
	}
	for(int i=1;i<=m;i++){
		ll x,y;
		scanf("%lld%lld",&x,&y);
		add(x,y,0.0);
		add(y,x,0.0);
	}
	for(int i=2;i<=n;i++)
		dis[i]=114514191.0;
	for(ll i=head[1];i;i=e[i].next)
		dis[e[i].v]=dis[e[i].v]>e[i].w?e[i].w:dis[e[i].v];
	while(++tot<n){
		double minn=114514191.0;
		vis[now]=1;
		for(int i=1;i<=n;i++)
			if(!vis[i]&&minn>dis[i]){
				minn=dis[i];
				now=i;
			}
		ans+=minn;
		for(int i=head[now];i;i=e[i].next)
			if(dis[e[i].v]>e[i].w&&!vis[e[i].v])
				dis[e[i].v]=e[i].w;
	}
	printf("%.2lf",ans);
	return 0;
}
2023/3/28 13:55
加载中...