파티 1238번 문제

이 문제는 다익스트라 알고리즘이다.

우선 X의 집에서 왔다 갔다한 시간중에 제일 긴 사람을 찾는 문제이다.

즉, 1번부터 N번째까지 사람 중

distance(1,X) + distance(X,1) // 1번에서 X의 집에 갔다가 X의 집에서 다시 1번의 가는 방법이다.

문제에서 단방향으로 간다 했으니 이런식으로 최대값을 구해주어야 한다.

import java.util.*;
public class Main {
 
    static PriorityQueue<Node> queue;
    static ArrayList<Node>[] al;
    static int distance[];
    static int n, m, x;
    static int Max = Integer.MIN_VALUE;
     static class Node implements Comparable<Node>{
        int distance;
        int index;
        
        Node(int index, int distance){
            this.index = index;
            this.distance = distance;
        }
 
        @Override
        public int compareTo(Node o) {
            // TODO Auto-generated method stub
            return this.distance <=o.distance ? -1 : 1;
        }
        
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        x = sc.nextInt();
        distance = new int [n+1];
        queue = new PriorityQueue<>();
        al = new ArrayList[n+1];
        for(int i=0; i<=n; i++) {
            distance[i] = Integer.MAX_VALUE;
            al[i] = new ArrayList<Node>();
        }
        
        
        for(int i=0; i<m;i++) {
            al[sc.nextInt()].add(new Node(sc.nextInt(),sc.nextInt()));
        }
        int result[] = new int[n+1];
        for(int i=1; i<=n; i++) {
            
            result[i] = dijkstra(i,x) + dijkstra(x,i);
            Max = Math.max(result[i], Max);
        }
            
        System.out.println(Max);
         
    }
    
    public static int dijkstra(int start, int end) {
        for(int k=0; k<=n; k++) {
            distance[k] = Integer.MAX_VALUE;
         
        }
        queue = new PriorityQueue<>();
        distance[start] = 0;
        queue.add(new Node(start,0));
        
        while(!queue.isEmpty()) {
            int current_index = queue.peek().index;
            int current_distance = queue.peek().distance;
            queue.remove();
            for(Node node : al[current_index]) {
                int next_index = node.index;
                int next_distance = node.distance;
                
                if(distance[next_index] > current_distance + next_distance) {
                    distance[next_index] = current_distance + next_distance;
                    queue.add(new Node(next_index,distance[next_index]));
                }
            }
        }
        return distance[end];
    }
 
}