[JAVA] 백준 13379 - Far Far Away

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

쉬고 싶은 대학교 강사들을 위한 [대학교 -> 학술회] 최장거리를 구하는 문제이다.

방향 그래프가 주어지고 DFS, BFS, 다익스트라 등 다양한 방법으로 풀 수 있는데 익숙한 다익스트라를 이용했다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = par(br.readLine());
        for (int i = 0; i < tc; i++) {
            int[] info = getArray(br.readLine());
            int nodeCount = info[0];
            int vertexCount = nodeCount-1;
            int minTime = info[1];
            int[] dist = new int[nodeCount+1];
            Arrays.fill(dist,Integer.MAX_VALUE);
            dist[1] = 0;
            List<List<P13379>> list = new ArrayList<>();
            for (int j = 0; j <= nodeCount; j++) {
                list.add(new ArrayList<>());
            }
            for (int j = 0; j < vertexCount; j++) {
                int[] r = getArray(br.readLine());
                list.get(r[0]).add(new P13379(r[1],r[2]));
            }
            dijkstra(dist,1,list);
            int max = -1;
            for (int j = 1; j < dist.length; j++) {
                if(dist[j]==Integer.MAX_VALUE) continue;
                if(dist[j]<minTime) continue;
                if(max<=dist[j]){
                    max = dist[j];
                }
            }
            System.out.println(max);
        }
    }
    static void dijkstra(int[] dist, int startNode, List<List<P13379>> list){
        PriorityQueue<P13379> pq = new PriorityQueue<>();
        dist[startNode] = 0;
        pq.offer(new P13379(startNode));
        while(!pq.isEmpty()){
            P13379 poll = pq.poll();
            int value = poll.to;
            int weight = poll.weight;
            if(dist[value]<weight) continue;
            List<P13379> vList = list.get(value);
            for (int i = 0; i < vList.size(); i++) {
                P13379 road = vList.get(i);
                int to = road.to;
                int cost = road.weight;
                if(dist[to]>weight+cost){
                    P13379 offer = new P13379(to);
                    offer.weight = weight+cost;
                    dist[to] = weight+cost;
                    pq.offer(offer);
                }
            }
        }
    }

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

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

class P13379 implements Comparable<P13379> {
    int to;
    int weight = 0;

    P13379(int t){
        this.to = t;
    }
    P13379(int t, int weight) {
        this.to = t;
        this.weight = weight;
    }

    @Override
    public int compareTo(P13379 o) {
        return this.weight - o.weight;
    }
}