为啥只有10分,明明样例都过了awa
查看原帖
为啥只有10分,明明样例都过了awa
309574
未知的X楼主2022/10/5 18:55

代码如下,除了第一个后面全WA QAQ

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
#define INF 2147483647
using namespace std;
struct edge{
	int to;
	long double dis;
};
vector<edge> e[1000005];
long double d[1005];//树枝最短
int n,m;
long double ans=0;
bool vis[1005];
struct point{
	int x,y;
};
point p[5005];
double dist(point a,point b){
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void prim(){
	for(int i=1;i<=n;i++){
		d[i]=INF;
	}
	d[1]=0;
	for(int ii=1;ii<=n;ii++){
		int minn=INF;
		int k=1;
		
		for(int i=1;i<=n;i++){
			if(d[i]<minn&&vis[i]==false){
				minn=d[i];
				k=i;
			}
		}
		vis[k]=true;
		for(int i=1;i<=n;i++){
			if(!vis[i]){
				edge tmp1;
				tmp1.to=i;
				tmp1.dis=dist(p[k],p[i]);
				e[k].push_back(tmp1);
			} 
		}
		for(int i=0;i<e[k].size();i++){
			if(d[e[k][i].to]>e[k][i].dis){
				d[e[k][i].to]=e[k][i].dis;
			}
		}
		if(ii==n) for(int i=1;i<=n;i++) ans+=d[i];
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>p[i].x>>p[i].y;
	}
	prim();
	printf("%.2Lf",ans);
	return 0;
} 
2022/10/5 18:55
加载中...