#include<bits/stdc++.h>
using namespace std;
double x[100+5],y[100+5];
double e[100+5][100+5];
const double inf=99999999;
int main()
{
int n,i,j,k;
double low[100+5],ans;
while(~scanf("%d",&n))
{
for(i=0;i<n;i++)
scanf("%lf%lf",&x[i],&y[i]);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(i==j) e[i][j]=inf;
else
{
e[i][j]=e[j][i]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
}
for(i=0;i<n;i++)
low[i]=e[0][i];
low[0]=-1;
ans=0;
for(i=1;i<n;i++)
{
double t=inf;
for(k=0;k<n;k++)
{
if(low[k]!=-1&&low[k]<t)
{
j=k;
t=low[k];
}
}
ans+=t;
low[j]=-1;
for(k=0;k<n;k++)
{
low[k]=min(low[k],e[j][k]);
}
}
printf("%.2f\n",ans);
}
return 0;
}

hdu 4463 Outlets More articles about

  1. 【HDU 4463 Outlets】 Minimum spanning tree (prim,kruscal All right )

    With (x,y) The form of coordinates is given n A little bit , Build roads to connect all the points ( Two of the given special points must be adjacent ), Find the minimum of the total length of all paths . Because there is no limit on the shape of the road to be built , So it can be regarded as a weighted undirected complete graph , The edge weight is the distance between two points . because ...

  2. hdu 4463 Outlets( Minimum spanning tree )

    Outlets Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other) Total Submi ...

  3. HDU 4463 Outlets( Minimum spanning tree coordinates )

    Problem Description In China, foreign brand commodities are often much more expensive than abroad. T ...

  4. HDU—4463 Outlets Minimum spanning tree

    In China, foreign brand commodities are often much more expensive than abroad. The main reason is th ...

  5. HDU 4463 Outlets ( Minimum spanning tree )

    The question : Given n Coordinates of points , And the two points are connected , But none of the others are connected , But to find the shortest way through all the points , And the shortest route . Analysis : I want to think about it , It should be the minimum spanning tree , Take all the two points that can be connected as edges , Then press the minimum ...

  6. HDU 4463 Outlets 【 Minimum spanning tree 】

    < Topic link > The main idea of the topic : I'll give you some coordinates of the points , I want you to connect all these points , But you have to include a special edge , What's the shortest distance between these points . Problem solving analysis : Because you have to include that side , We'll record that side ...

  7. hdu 4463 Outlets( Minimum spanning tree )

    The question :n Road construction at one place , Minimum total length required , But there are two points p.q Must be connected Ideas : Complete graph ,prim The efficiency of the algorithm depends on the number of nodes , For dense graphs . use prim solve . p.q The distance between them is set to 0 that will do , Add the p.q Distance between pri ...

  8. hdu 4463 One side has to be added (2012 Hangzhou regional competition K topic )

    Nike store and Apple stores have to be connected Sample Input42 30 01 00 -1 1 -10 Sample Output3.41 # include <iostream> # includ ...

  9. hdu 4463 The first 37 the ACM/ICPC Hangzhou competition area K topic Minimum spanning tree

    The question : Give some points in the coordinate system , Two of them are already connected to an edge , Finding the value of the minimum spanning tree Set the weight of the connected two points to 0, In this way, it must be added to the minimum spanning tree The final result plus the distance between the two points is the result #include<cstdio& ...

Random recommendation

  1. Principles of computer composition, questions and answers of previous years (tzf!!!)

    Principles of computer composition, questions and answers of previous years ( Download link !!!) Go princess go (1~36) ::http://pan.baidu.com/s/1dDP5Kqd

  2. hadoop turn

    detailed http://wenku.baidu.com/view/c2d1ebb4ba0d4a7302763a84.html http://hadoop.apache.org/docs/r1. ...

  3. [WPF] Resource dictionary —— Resource sharing between assemblies Simple skin change

    Go straight to the code , After that, I checked the situation myself , Novices can also watch it ! 1. Create a new data class and a WPF engineering 2.APP.XAML It should be a resource dictionary , Attention should be paid to Source Format , There must be something in front “/” <ResourceDiction ...

  4. c++ Design patterns 1

    Start with object-oriented 1) Bottom thinking : Down , How to grasp the bottom , Understanding object construction from microcosmic perspective ( Language structure . Compile transformation . Memory model . Runtime mechanism ) Abstract thinking : Up , How to abstract the world around us into program code   ( object-oriented . Component encapsulation ...

  5. Fuck Sharepoint 2013

    Recently, I met a seemingly bug The problem of , Each time you click on the page, the address of the page is one more line /_layouts/15/start.aspx#/ And then ran to the google Search for solutions on , Address :http://social.tec ...

  6. Qt It shows the network picture ( It can be changed to upgrade module )

    http://blog.csdn.net/u011012932/article/details/50773382

  7. How to use Linux Universal back door ( turn zafe)

    hot tip : Only for safety testing and teaching , Prohibition of illegal use . The title party , ha-ha Actually, it 's just ssh back door , You don't need to look at the kernel version , It's simple , To take care of novices ! ********************************** ...

  8. C3p0 Parameter Settings

    C3p0 Parameter Settings :ComboPooledDataSource and BasicDataSource It also provides a way to shut down the data source close() Method , So we can guarantee Spring The data source can be successfully released when the container is closed ...

  9. How to Enable Multi-Touch

    This is a frequently asked question. Multi-touch feature is available on both iOS & Android port ...

  10. Android Dashen blog collection

    Awesome CSDNBlog And personal Blog, these Blog They all have one thing in common , That is, the content is detailed , The explanation is thorough , It can also be regarded as a way for later beginners ! As long as you make up your mind to follow the strong , Become the great God in people's eyes , It's just a matter of time ! Next ...