[백준] 4386번 별자리 만들기 (gold 3

import java.io.*;
import java.util.*;

class Point{
    double x;
    double y;
    public Point(double x, double y){
        this.x=x;
        this.y=y;
    }
}

class Point2{
    int num;
    double l;
    public Point2(int num, double l){
        this.num=num;
        this.l=l;
    }
}
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int n=Integer.valueOf(br.readLine());
        Point[] star=new Point[n];
        for(int i=0; i<n; i++){
            st=new StringTokenizer(br.readLine());
            double x=Double.valueOf(st.nextToken());
            double y=Double.valueOf(st.nextToken());
            star[i]=new Point(x,y);
        }

        double[][] map=new double[n][n];
        for(int i=0; i<n; i++){
            Arrays.fill(map[i], Double.MAX_VALUE);
        }

        for(int i=0; i<n; i++){
            Point temp=star[i];
            for(int j=i+1; j<n; j++){
                Point temp2=star[j];
                double length=Math.sqrt(Math.pow(temp2.y-temp.y ,2)+ Math.pow(temp2.x-temp.x,2));
                map[i][j]=length;
                map[j][i]=length;
            }
        }

        PriorityQueue<Point2> que=new PriorityQueue<>(new Comparator<Point2>(){
            public int compare(Point2 o1 ,Point2 o2){
                if(o1.l<o2.l){
                    return -1;
                }
                else{
                    return 1;
                }
            }
        });

        double[] visit=new double[n];
        Arrays.fill(visit, Double.MAX_VALUE);
        que.offer(new Point2(0,0));
        double answer=0;
        int visitN=0;

        while(!que.isEmpty()){
            Point2 temp=que.poll();
            if(visit[temp.num]==Double.MIN_VALUE){
                continue;
            }
            visit[temp.num]=Double.MIN_VALUE;
            answer+=temp.l;
            for(int i=0; i<n; i++){
                if(i==temp.num || map[temp.num][i]==Double.MAX_VALUE || visit[i]<=map[temp.num][i]){
                    continue;
                }
                que.offer(new Point2(i, map[temp.num][i]));
            }
        }

        bw.write(String.format("%.2f", answer));
        bw.flush();
    }

}