[JAVA] 백준 6248 - Bronze Cow Party

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

특정 노드에서 각 노드로 출발했을 때, 가장 멀리 떨어져 있는 노드까지의 왕복가중치를 구하는 문제이다.

 

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] info = getArray(br.readLine());
        int nodeCount = info[0];
        int roadCount = info[1];
        int startNode = info[2];
        List<N18352> nodeList = new ArrayList<>();
        for (int i = 0; i <= nodeCount; i++) {
            nodeList.add(new N18352(i));
        }
        nodeList.get(startNode).weight = 0;
        PriorityQueue<N18352> pq = new PriorityQueue<>();
        for (int i = 0; i < roadCount; i++) {
            int[] road = getArray(br.readLine());
            nodeList.get(road[0]).roadList.add(new V18352(road[1],road[2]));
            nodeList.get(road[1]).roadList.add(new V18352(road[0],road[2]));
        }
        boolean[] visited = new boolean[nodeCount+1];
        pq.offer(nodeList.get(startNode));
        while(!pq.isEmpty()){
            N18352 node = pq.poll();
            List<V18352> roadList = node.roadList;
            if(visited[node.value]) continue;
            visited[node.value] = true;
            for (int i = 0; i < roadList.size(); i++) {
                int targetNode = roadList.get(i).to;
                if(node.weight + roadList.get(i).weight < nodeList.get(targetNode).weight){
                    nodeList.get(targetNode).weight = node.weight + roadList.get(i).weight;
                    pq.offer(nodeList.get(targetNode));
                }
            }
        }
        System.out.println(nodeList.stream().mapToInt(x -> x.weight==Integer.MAX_VALUE?-1:x.weight).max().getAsInt()*2);
    }

    static int par(String s) {
        return Integer.parseInt(s);
    }

    static int[] getArray(String s) {
        return Arrays.stream(s.split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

class N18352 implements Comparable<N18352>{
    int value;
    int weight = Integer.MAX_VALUE;
    List<V18352> roadList = new ArrayList<>();
    N18352(int value){
        this.value = value;
    }
    @Override
    public int compareTo(N18352 other){
        return this.weight - other.weight;
    }
}

class V18352{
    int to;
    int weight;
    V18352(int t, int w){
        this.to = t;
        this.weight = w;
    }
}