[백준] 1774번 우주신과의 교감 (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 Input{
    int x;
    double y;
    public Input(int x, double y){
        this.x=x;
        this.y=y;
    }
}
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=new StringTokenizer(br.readLine());
        int n=Integer.valueOf(st.nextToken());
        int m=Integer.valueOf(st.nextToken());

        Point[] uni=new Point[n+1];
        for(int i=1; i<=n; i++){
            st=new StringTokenizer(br.readLine());
            uni[i]=new Point(Double.valueOf(st.nextToken()) , Double.valueOf(st.nextToken()));
        }//각 좌표들

        ArrayList<Integer>[] link=new ArrayList[n+1];
        for(int i=1; i<=n; i++){
            link[i]=new ArrayList<>();
        }//연결되어 있는 케이스들

        for(int i=1; i<=m; i++){
            st=new StringTokenizer(br.readLine());
            int a=Integer.valueOf(st.nextToken());
            int b=Integer.valueOf(st.nextToken());
            link[a].add(b);
            link[b].add(a);
        }

        PriorityQueue<Input> que=new PriorityQueue<>(new Comparator<Input>(){
            public int compare(Input o1, Input o2){
                if(o1.y==o2.y){
                    return o1.x-o2.x;
                }
                else {
                    return (int) ((o1.y - o2.y) * 1000);
                }
            }
        });

        double answer=0;
        boolean[] visit=new boolean[n+1];

        que.offer(new Input(1,0));

        while(!que.isEmpty()){
            Input temp=que.poll();
            if(visit[temp.x]){
                continue;
            }
            visit[temp.x]=true;
            answer+=temp.y;

            for(int i=0; i<link[temp.x].size(); i++){
                if(visit[link[temp.x].get(i)]){
                    continue;
                }
                que.offer(new Input(link[temp.x].get(i) , 0.0));
            }

            for(int i=1; i<=n; i++){
                if(visit[i]){
                    continue;
                }
                double l=Math.sqrt(Math.pow(uni[temp.x].x-uni[i].x,2) + Math.pow(uni[temp.x].y-uni[i].y ,2));
                que.offer(new Input(i, l));
            }
        }
        answer=(double)((int)(Math.round(answer*100)))/100;
        bw.write(String.format("%.2f" , (answer)));
        bw.flush();
    }
}

// 이미 연결되어 있는 경우가 있는 상황에서 연결 안 된 노드들의 mst를 구하는 문제이다
// 각 좌표의 값을 저장하고, 이미 연결되어 있는 연결점들도 저장한다.
// mst를 돌면서 이미 연결된 경우는 거리를 0으로, 나머지 연결점들은 거리값을 que에 넣어주면서
// mst를 구하면된다. 이때 고려할 점은 priorityQueue에서의 comparator였다.
// 총 3번 정도 틀렸는데, 그 문제를 파악해보니. 우선순위큐에서의 우선순위 판단에서. 
// return (int) (o1.y - o2.y) * 10; 이부분이 오류였다.
// 왜냐하면 (int)형변환은 뒤에 (o1.y - o2.y)까지이기 때문이다. 그래서 만약 소수점의 차이가 존재하면.
// (int)형변환으로 0이되어 같은 값으로 판별된다. 따라서, return (int) ((o1.y - o2.y) * 1000);
// 다음처럼 전체를 괄호로 묶어야 올바르게 크기 판단이 이루어진다.