The first line contains 0 < n <= 1000, the number of point. For each point, a line follows; each following line contains two real numbers indicating the (x,y) coordinates of the point.
Output The shortest distance.prints a single real number to two decimal places. Sample Input 3 1.0 1.0 2.0 2.0 2.0 4.0 Sample Output 3.41
明天就该去青岛打省赛了，今天走之前，再把之前的债还一波。曾经的新生总结赛，超哥让我出两道题，一道最短路，一道并查集。本来说是出题难度中等偏易，结果隔了几天脑子短路了，记成了出题中等偏难....再然后就诞生了1230这道题，后来才发现这一点，然后出了1229这道题，结果...正式比赛的时候我出的这俩题根本没新生做= =心痛。好吧也是我的锅，而这两道题出完我自己也一直没有好好整理一下，马上省赛了现在拿出来再重新来整理一下。
当时出这道题的时候感觉还不算太难所以出了，可能是因为先入为主了吧= =继续背锅...题意是说给出n个点，用线连接这些点，问最短需要多长的线。方法就是将所有点之间的距离都求出来，这时就构建出了一个图出来，然后就是一道最小生成树的问题了，之后就直接套模板就可以了。
题目源于HDU一道题，原来题目的范围是n<=100，因为当时讲课的时候和新生说过边多的情况用prim算法，边少的情况用kruskal算法，所以在出题的时候我本想着卡一下时间，让新生用prim算法来做，所以把范围开到了n<=1000。不过当时因为时间问题（PS：我交给超哥的时候其实已经晚了一天了= =），所以只是开了范围出了数据，然后用prim试了一下就没再管。现在拿出来这个题再看，没想到无心插柳柳成荫了，这题用prim能过，用kruskal做就会超时....
下面AC代码：
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> using namespace std; #define INF 999999999 bool s[1005]; double dist[1005],ma[1005][1005]; typedef struct node { double x,y; }Point; Point p[1005]; double Distance(Point a,Point b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } void init(int n) { int i,j; memset(s,0,sizeof(s)); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { ma[i][j]=INF; } } for(i=1;i<=n;i++) { ma[i][i]=0; } } double Prim(int n) { int i,j,k; double mind,sum; for(i=1;i<=n;i++) { dist[i]=ma[1][i]; } s[1]=1; sum=0; for(i=1;i<=n;i++) { mind=INF; k=1; for(j=1;j<=n;j++) { if(!s[j]&&dist[j]<mind) { k=j; mind=dist[j]; } } s[k]=1; sum+=dist[k]; for(j=1;j<=n;j++) { if(!s[j]&&dist[j]>ma[k][j]) dist[j]=ma[k][j]; } } return sum; } int main() { int m,n,i,j; while(scanf("%d",&n)!=EOF) { init(n); for(i=1;i<=n;i++) { scanf("%lf%lf",&p[i].x,&p[i].y); } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { ma[i][j]=Distance(p[i],p[j]); } } printf("%.2f\n",Prim(n)); } return 0; }