# Poj Solution 2560

```http://poj.org/problem?id=2560

/* @author: */
import java.util.Scanner;
import java.util.Arrays;
public class Main{
static double INF=99999999.0;

public static void main(String args[])
{
Scanner sc=new Scanner(System.in);

double p[][]=new double;
double ax[]=new double;
double ay[]=new double;
double dis[]=new double;
boolean used[]=new boolean;
int n,i,j;
n=sc.nextInt();
for(i=0;i< n;i++){
ax[i]=sc.nextDouble();
ay[i]=sc.nextDouble();
}
for(i=0;i< n;i++)
for(j=0;j< n;j++) p[i][j]=INF;
for(i=0;i< n;i++)
for(j=i+1;j< n;j++)
{
double v=(ax[i]-ax[j])*(ax[i]-ax[j])+(ay[i]-ay[j])*(ay[i]-ay[j]);
v=Math.sqrt(v);
if(v< p[i][j])p[i][j]=p[j][i]=v;
}
for(i=0;i< n;i++)
dis[i]=p[i];
Arrays.fill(used,false);
dis=0;
used=true;
double ans=0;
for(i=0;i< n-1;i++)
{
double min=INF;
int tag=-1;
for(j=1;j< n;j++)
{
if(!used[j]&&dis[j]< min)
{
min=dis[j];
tag=j;
}
}
used[tag]=true;
ans+=min;
for(j=1;j< n;j++)
{
if(!used[j]&&dis[j]>p[tag][j])
dis[j]=p[tag][j];
}
}
System.out.printf("%3.2fn",ans);
}
}
```
This entry was posted in poj. Bookmark the permalink.