BOJ 1197. 최소 스패닝 트리

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static final int MAX_N = 10010;
    static List<Edge>[] edges = new ArrayList[MAX_N];
    static {
        for(int i = 0; i < MAX_N; i++)
            edges[i] = new ArrayList<Edge>();
    }
    static PriorityQueue<Edge> pq = new PriorityQueue<>();
    static boolean[] visited = new boolean[MAX_N];

    static class Edge implements Comparable<Edge> {
        int to, weight;
        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
        @Override
        public int compareTo(Edge o) {
            return Integer.compare(this.weight, o.weight);
        }
    }

    static int solution() {
        int sum = 0;

        visited[1] = true;
        while (!pq.isEmpty()) {
            Edge cur = pq.poll();
            int from = cur.to;
            if (visited[from]) continue;

            visited[from] = true;
            sum += cur.weight;

            for (int i = 0; i < edges[from].size(); i++) {
                int to = edges[from].get(i).to;
                int weight = edges[from].get(i).weight;
                if (visited[to]) continue;

                pq.offer(new Edge(to, weight));
            }
        }
        return sum;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(in.readLine(), " ");
        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(in.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            Edge toB = new Edge(b, c);
            Edge toA = new Edge(a, c);
            edges[a].add(toB);
            edges[b].add(toA);
            if (a == 1) pq.offer(toB);
            if (b == 1) pq.offer(toA);
        }
        System.out.println(solution());
    }
}