[백준] 15971번 두 로봇 (gold 4

import java.io.*;
import java.util.*;

class Point{
    int room;
    int v;
    int maxLength;
    public Point(int room, int v, int maxLength){
        this.room=room;
        this.v=v;
        this.maxLength=maxLength;
    }
}
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st=new StringTokenizer(br.readLine());

        int n=Integer.valueOf(st.nextToken());
        int s=Integer.valueOf(st.nextToken());
        int e=Integer.valueOf(st.nextToken());

        ArrayList<Point>[] arr=new ArrayList[n+1];
        for(int i=1; i<=n; i++){
            arr[i]=new ArrayList<>();
        }

        for(int i=1; i<n; i++){
            st=new StringTokenizer(br.readLine());
            int room1=Integer.valueOf(st.nextToken());
            int room2=Integer.valueOf(st.nextToken());
            int v=Integer.valueOf(st.nextToken());

            arr[room1].add(new Point(room2, v,0));
            arr[room2].add(new Point(room1, v,0));
        }

        PriorityQueue<Point> que=new PriorityQueue<>(new Comparator<Point>(){
            public int compare(Point o1 ,Point o2){
                return o1.v-o2.v;
            }
        });
        boolean[] visit=new boolean[n+1];
        que.offer(new Point(s,0,0));
        visit[s]=true;

        //시작점과 끝점을 이으면서, 가장 길었던 루트를 사이에 두고 마주하면됨.
        //즉 가장긴 가중치의 길을 빼는 bfs를 구현하면된다.
        Point answer=new Point(0,0,0);
        while(!que.isEmpty()){
            Point temp=que.poll();
            int find=temp.room;
            if(find==e){
                answer=temp;
                break;
            }
            for(int i=0; i<arr[find].size(); i++){
                Point p=arr[find].get(i);
                if(!visit[p.room]){
                    int max= p.v > temp.maxLength ? p.v : temp.maxLength;
                    visit[p.room]=true;
                    que.offer(new Point(p.room, temp.v+p.v, max));
                }
            }
        }
        //둘 사이에 길이 하나면 이동할 필요 x 길이는 0출력하게됨 (틀린요인
        bw.write(answer.v-answer.maxLength+"");
        bw.flush();
    }
}