주의할 점

1. 메모리 초과 주의
2. 양방향

참고 : https://koosaga.com/14

 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static LinkedList[] tree;
    public static boolean[] isVisit;
    public static int[] nodeValue;

    public static int n;
    public static Queue queue;

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

        n = Integer.parseInt(br.readLine());
        tree = new LinkedList[n + 1];
        isVisit = new boolean[n + 1];
        nodeValue = new int[n + 1];

        for (int i = 1; i <= new="" node="">();
        }

        int startNode = 0;
        for (int i = 1; i <= n="" -="" stringtokenizer="" st="new" int="" start="Integer.parseInt(st.nextToken());" destination="Integer.parseInt(st.nextToken());" weight="Integer.parseInt(st.nextToken());" new="" if="" i="" startnode="start;" max="0;" index="0;" for=""> max) {
                max = nodeValue[i];
                index = i;
            }
        }

        for (int i = 1; i <= max="Math.max(max," for="" int="" i="" public="" static="" void="" queue="new" integer="">();

        queue.add(node);

        while (!queue.isEmpty()) {
            int currentNode = queue.poll();
            isVisit[currentNode] = true;

            for (Node nextNode : tree[currentNode]) {
                if (!isVisit[nextNode.node]) {
                    queue.add(nextNode.node);
                    nodeValue[nextNode.node] = nodeValue[currentNode] + nextNode.weight;
                }
            }
        }
    }
}

class Node {
    int node;
    int weight;

    Node(int node, int weight) {
        this.node = node;
        this.weight = weight;
    }
}