10pts求助
查看原帖
10pts求助
1055920
taoqiniu楼主2024/7/5 20:58

样例过了但只得了10pts /(ㄒoㄒ)/~~

#include<bits/stdc++.h>
using namespace std;
const int N=5010;
int n;
double ans=0;
double x[N];
double y[N];
double dis[N];
bool vis[N];
double gett(int a,int b){
	return sqrt(pow(x[a]-x[b],2)+pow(y[a]-y[b],2));
}
void prim(){
	vis[1]=1;
	int k;
	double minn;
	for(int i=2;i<=n;i++){
		k=0;
		minn=0x3f*1.0;
		for(int j=1;j<=n;j++){
			if(!vis[j] && dis[j]<minn){
				minn=dis[j];
				k=j;
			}
		}
		ans+=minn;
		vis[k]=1;
		for(int j=1;j<=n;j++){
			if(dis[j]>gett(k,j)){
				dis[j]=gett(k,j);
			}
		}
	} 
	
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
	}
	dis[1]=0.0;
	for(int i=2;i<=n;i++){
		dis[i]=gett(1,i);
	}
	prim();
	printf("%.2lf",ans);
	return 0;
}
2024/7/5 20:58
加载中...