[BOJ 1922]ネットワーク接続(Java)

質問する

道賢はコンピューターとコンピューターを接続するネットワークを構築しなければならない.しかし残念なことに、ハブがなく、コンピュータとコンピュータを直接接続する必要があります.しかし、みんなが資料を共有するために、すべてのパソコンがつながっています.(aとbの接続はaとbの経路が存在することを意味する.aとbには接続線があり、bとcには接続線があり、aとcには接続線がある.)
しかし、コンピューターに接続する費用を最小限に抑える以上、コンピューターに接続する費用のほかに、他の場所にお金を使うこともできます.これにより、各コンピュータへの接続に必要なコストが達成されると、すべてのコンピュータへの接続に必要な最低コストが出力されます.接続できないパソコンは1台もありません.

入力

第1行は、計算機数N(1≦N≦1000)を与える.
2行目は、接続可能な直線数M(1≦M≦100000)を与える.
3行目からM+2行目まで、各コンピュータをM行に接続するのに必要な費用.この費用の情報は3つの整数であり、a b cが与えられた場合、aコンピュータとbコンピュータを接続する費用はc(1≦c≦10000)であることを示す.aとbは同じかもしれません.

しゅつりょく

すべてのコンピュータを接続するために必要な最小コストを最初のローに出力します.

方法

簡単なMSTアルゴリズムの問題.Primアルゴリズムで実現しましょう.

ソースコード

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

public class NetworkConnect {

    static ArrayList<Node>[] network;

    static class Node implements Comparable<Node>{
        int goal;
        int price;

        public Node(int goal, int price) {
            this.goal = goal;
            this.price = price;
        }

        @Override
        public int compareTo(Node o) {
            return price - o.price;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        int result = 0;
        network = new ArrayList[n + 1];

        for (int i = 0; i <= n; i++) {
            network[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            String[] input = br.readLine().split(" ");
            int a = Integer.parseInt(input[0]);
            int b = Integer.parseInt(input[1]);
            int p = Integer.parseInt(input[2]);
            network[a].add(new Node(b, p));
            network[b].add(new Node(a, p));
        }

        PriorityQueue<Node> linePriorityQueue = new PriorityQueue<>();
        boolean[] visit = new boolean[n + 1];
        linePriorityQueue.offer(new Node(1, 0));

        while (!linePriorityQueue.isEmpty()) {
            Node now = linePriorityQueue.poll();

            if (visit[now.goal]) continue;
            result += now.price;
            visit[now.goal] = true;

            for (Node node : network[now.goal]) {
                if (!visit[node.goal]) {
                    linePriorityQueue.offer(node);
                }
            }
        }
        System.out.println(result);
    }
}

結果