[Algorithm] Dijkstra 파티(파티) - 에이젠

 

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

1238번: 파티

처음 다익스트라 공략 방법을 그대로 사용.

다만 단방향의 Edge에서 왕복을 해야한다는 내용이 추가된 문제.

다익스트라 알고리즘을 두번 사용하여 왕복하는 시간을 알아내었음.

import java.util.*;

class Main {

    static Scanner sc = new Scanner(System.in);


    static class Edge {
        int to ;
        int weight;

        Edge(int _to, int _weigth){
            to = _to;
            weight = _weigth;

        }
    }

    static class Info{
        int idx;
        int dist;

        Info(int _idx, int _dist){
            idx = _idx;
            dist = _dist;
        }
    }

    static int N, M, X;
    static int[] dist;
    static int[] backDist;

    static ArrayList<Edge>[] edges;



    public static void input(){
        N = sc.nextInt();
        M = sc.nextInt();
        X = sc.nextInt();

        dist = new int[N + 1];

        backDist = new int[N + 1];

        edges = new ArrayList[N+1];
        for(int i = 1 ; i <= N ; i ++){
            edges[i] = new ArrayList<Edge>();
        }
        for(int i = 1; i <= M ; i++){
            int from = sc.nextInt();
            int to = sc.nextInt();
            int cost = sc.nextInt();

            edges[from].add(new Edge(to, cost));

        }

    }

    static void dijkstra(int start){
        //dist 초기화
        for(int i = 1; i <= N ; i++){
            dist[i] = Integer.MAX_VALUE;
        }
        //최소 힙 생성
        PriorityQueue<Info> heap = new PriorityQueue<Info>(Comparator.comparingInt(o -> o.dist));

        heap.add(new Info(start,0));
        dist[start] = 0;

        while(!heap.isEmpty()){
            Info info = heap.poll();

            if(dist[info.idx] != info.dist) continue; //기존의 데이터와 다르다면 폐기

            for(Edge e : edges[info.idx]){
                if (dist[info.idx] + e.weight >= dist[e.to]) continue;
                // e.to 까지 갈 수 있는 더 짧은 거리를 찾았다면 이에 대한 정보를 갱신하고 PQ에 기록해준다.
                dist[e.to] = dist[info.idx] + e.weight;
                heap.add(new Info(e.to, dist[e.to]));

            }
        }
    }
    static void pro() {

        int maxTime = 0;
        int time = 0;
        for(int i = 1; i <= N ; i++){
//            if (i == X) continue;
            dijkstra(i);
            time = dist[X];
            dijkstra(X);
            time = time + dist[i];

            if (maxTime <= time ){
                maxTime = time;
            }
        }

        System.out.println(maxTime);

    }


    public static void main(String[] args){
        input();
        pro();

    }
}