pku2560.java

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· Java 代码 · 共 65 行

import java.io.*;
import java.util.*;
import java.lang.Math;
public class Main
{
	public static void main(String args[]) throws Exception
	{
		Scanner cin=new Scanner(System.in);
		int N,i,j,near,number=1;
		double[][] point,dist;
		boolean[] status;
		double min,len=0;
		int minpoint;
		N=cin.nextInt();
		point=new double[N][2];
		dist=new double[N][N];
		status=new boolean[N];
		for(i=0;i<N;i++)
		{
			point[i][0]=cin.nextDouble();
			point[i][1]=cin.nextDouble();
			status[i]=false;
		}
		for(i=0;i<N;i++)
		{
			for(j=0;j<N;j++)
			{
				dist[i][j]=length(point[i],point[j]);
			}
		}
		status[0]=true;
		number=1;
		while(number<N)
		{
			j=0;
			while(status[j])j++;
			minpoint=j;
			min=dist[0][j];
			for(i=0;i<N;i++)
			{
				if(status[i])
				{
					for(j=0;j<N;j++)
					{
						if(!status[j])
							if(dist[i][j]<min)
							{
								min=dist[i][j];
								minpoint=j;
							} 
					}
				}
			}
			status[minpoint]=true;
			number++;
			len+=min;
		}
		System.out.printf("%.2f\n",len);
	}
	static double length(double a[],double b[])
	{
		return Math.sqrt((a[0]-b[0])*(a[0]-b[0])+(a[1]-b[1])*(a[1]-b[1]));
	}
}