[BOJ_21924] 도시건설

설명

---

타입만 잘 지정하면 된다.

 

코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static class Data implements Comparable<Data>{
        int end;
        int weight;
        public Data(int end, int weight) {
            this.end = end;
            this.weight = weight;
        }
        @Override
        public int compareTo(Data o) {
            return this.weight - o.weight;
        }
    }
    static boolean visited[];
    static long max = 0;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine()," ");
        int V = Integer.parseInt(tk.nextToken()); //정점의 갯수
        int E = Integer.parseInt(tk.nextToken()); //간선의 갯수
        ArrayList<Data>[] list = new ArrayList[V+1];
        visited = new boolean[V+1];
        for(int i = 0;i<V+1;i++) {
            list[i] = new ArrayList();
        }

        for(int i = 0; i < E; i++) {
            tk = new StringTokenizer(in.readLine()," ");
            int from = Integer.parseInt(tk.nextToken());
            int to = Integer.parseInt(tk.nextToken());
            int weight = Integer.parseInt(tk.nextToken());
            list[from].add(new Data(to,weight));
            list[to].add(new Data(from,weight));
            max += weight;
        }
        PriorityQueue<Data> q = new PriorityQueue<Data>();
        q.offer(new Data(1,0)); //자기 자신은 0
        int cnt = 0;
        long res = 0;
        while(!q.isEmpty()) {

            Data cur = q.poll(); 
            if(visited[cur.end]) {
                continue;
            }
            visited[cur.end] = true;
            res += (long)cur.weight;
            cnt++;
            if(cnt == V) { 
                break;
            }

            for (int j = 0; j < list[cur.end].size(); j++) {
                if(!visited[list[cur.end].get(j).end]) {
                    q.offer(new Data(list[cur.end].get(j).end,list[cur.end].get(j).weight));
                }
            }
        }
        if(cnt >= V) {
            System.out.println(max - res);
        }else{
            System.out.println(-1);
        }
    }
}

21924번: 도시 건설