백준 20010번 : 악덕 영주 혜유 - Java 크루스칼, 다익스트라

https://www.acmicpc.net/problem/20010

20010번: 악덕 영주 혜유

 

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


class Node implements Comparable<Node>{
    int x, y, c;

    Node(int x, int y, int c){
        this.x = x;
        this.y = y;
        this.c = c;
    }

    @Override
    public int compareTo(Node n){
        return c - n.c;
    }

}



class Edge implements Comparable<Edge>{
    int x,c;
    Edge(int x, int c){
        this.x = x;
        this.c = c;
    }

    @Override
    public int compareTo(Edge e){
        return c - e.c;
    }
}


public class Main {
    static int n, k;
    static int unf[];
    static long dist[];
    static PriorityQueue<Node> Q = new PriorityQueue<Node>();
    static PriorityQueue<Edge> q = new PriorityQueue<Edge>();
    static ArrayList<Edge> adj[];

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] split = br.readLine().split(" ");

        int n = Integer.parseInt(split[0]);
        int k = Integer.parseInt(split[1]);



        adj = new ArrayList[n];
        unf = new int[n];
        dist = new long[n];

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

        Arrays.fill(unf,-1);
        Arrays.fill(dist, Long.MAX_VALUE);

        for(int i=0; i<k; i++){
            int a, b, c;
            split = br.readLine().split(" ");
            a = Integer.parseInt(split[0]);
            b = Integer.parseInt(split[1]);
            c = Integer.parseInt(split[2]);

            Q.add(new Node(a,b,c));
        }

        long ans = 0;

        while(!Q.isEmpty()){
            Node cur = Q.poll();
            int x = cur.x;
            int y = cur.y;
            int c = cur.c;


            if(Find(x)!=Find(y)) {
                Union(x, y);
                ans += c;
                adj[x].add(new Edge(y,c));
                adj[y].add(new Edge(x,c));
            }
        }


        q.add(new Edge(0,0));

        int stNode = -1;

        while(!q.isEmpty()){
            Edge cur = q.poll();
            int x = cur.x;
            int c = cur.c;

            if(dist[x] < c ) continue;
            dist[x] = c;
            stNode = x;

            for(int i=0; i<adj[x].size(); i++){
                Edge nx = adj[x].get(i);

                if(dist[nx.x] > c + nx.c){
                    q.add(new Edge(nx.x, c+nx.c));
                }
            }
        }

        Arrays.fill(dist, Long.MAX_VALUE);

        q.add(new Edge(stNode, 0));


        long ansdist = 0;
        while(!q.isEmpty()){
            Edge cur = q.poll();
            int x = cur.x;
            int c = cur.c;

            if(dist[x] < c ) continue;
            dist[x] = c;
            ansdist = c;

            for(int i=0; i<adj[x].size(); i++){
                Edge nx = adj[x].get(i);

                if(dist[nx.x] > c + nx.c){
                    q.add(new Edge(nx.x, c+nx.c));
                }
            }
        }





        System.out.println(ans);
        System.out.println(ansdist);


    }



    static int Find(int x){
        if(unf[x]==-1) return x;
        return Find(unf[x]);
    }

    static void Union(int a, int b){
        int a1 = Find(a);
        int b1 = Find(b);

        if(a1!=b1){
            unf[a1] = b1;
        }
    }

}