[백준] 10423번 전기가 필요해 (gold 3

 

원래 골드 2였던 문제였는데, 난이도 기여에서 골드3을 하자 난이도가 내려갔다..!

다들 gold3에 좀더 많이 의견이 쏠려있었나 보다..

이렇게 난이도 제시한게 모여서 , 바로 반영되는 건 처음이었는데 신기했다. 

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

class Point{
    int city;
    int v;
    public Point(int city, int v){
        this.city=city;
        this.v=v;
    }
}
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());
        int k=Integer.valueOf(st.nextToken());

        //간선구성
        ArrayList<Point>[] map=new ArrayList[n+1];
        for(int i=1; i<=n; i++){
            map[i]=new ArrayList<>();
        }
        //방문여부
        boolean[] visit=new boolean[n+1];
        //pq 구성
        PriorityQueue<Point> que=new PriorityQueue<>(new Comparator<Point>(){
            public int compare(Point o1 , Point o2){
                return o1.v-o2.v;
            }
        });

        //발전소 설치된 도시 입력. 이 수들에서 mst가 시작됨.
        //큐에 넣어서 세팅. 시작값들이므로. 다들 거리는 0
        st=new StringTokenizer(br.readLine());
        for(int i=0; i<k; i++){
            int t=Integer.valueOf(st.nextToken());
            que.offer(new Point(t, 0));
        }

        //간선입력
        for(int i=0; i<m; i++){
            st=new StringTokenizer(br.readLine());
            int a=Integer.valueOf(st.nextToken());
            int b=Integer.valueOf(st.nextToken());
            int v=Integer.valueOf(st.nextToken());

            map[a].add(new Point(b,v));
            map[b].add(new Point(a,v));
        }

        //총방문 도시수.
        int total=0;
        //가중치 총합
        int sum=0;

        //mst진행
        while(!que.isEmpty()){
            Point temp=que.poll();
            if(visit[temp.city]){
                continue;
            }

            visit[temp.city]=true;
            sum+=temp.v;
            total++;

            if(total==n){
                break;
            }

            for(int i=0; i<map[temp.city].size(); i++){
                Point move=map[temp.city].get(i);
                if(!visit[move.city]){
                    que.offer(new Point(move.city , move.v));
                }
            }

        }

        bw.write(sum+"");
        bw.flush();
    }
}