原题链接
虽然题面很长 但是这道题 只是一个 裸的Prim
不过 滚动数组和二维数组的差别 就是100分和10分的差别 谜一样的MLE 神奇的WA 5000*5000的数组 敬请收看今天的 走出科学·数组的前世今生
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<cmath> #include<algorithm> #include<queue> using namespace std; struct nico { double x,y; }city[5000+5]; double dis[5000+5],ans,dismin; int i,j,n,minx,tmin,vis[5000+5]; int main() { scanf("%d",&n); memset(dis,127,sizeof(dis)); for(i=1;i<=n;i++) scanf("%lf%lf",&city[i].x,&city[i].y); minx=1; dismin=1e12; vis[1]=1; for(i=1;i<=n-1;i++) { for(j=1;j<=n;j++) if(!vis[j]) { double distance=sqrt((city[minx].x-city[j].x)*(city[minx].x-city[j].x)+(city[minx].y-city[j].y)*(city[minx].y-city[j].y)); dis[j]=min(dis[j],distance); if(dis[j]<dismin) { dismin=dis[j]; tmin=j; } } ans+=dismin; minx=tmin; vis[minx]=1; dismin=1e12; } printf("%.2lf",ans); return 0; }