골드3 - 백준 1238 파티

백준 1238 파티

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

접근방법

파티에 가기 위해서 모든 마을에서 파티로 가는 가장 짧은 거리를 구해야하고, 파티에서 각자 마을로 돌아가는 가장 짧은 거리도 구해야한다. 결국 파티를 중심으로 모든 마을까지의 거리를 구하면 되기 때문에 단방향의 도로들을 거꾸로 방향을 전환하여 다익스트라를 통해 각 마을에서 파티까지 최단 거리를 구해주고, 정상적인 방향으로 다익스트라를 이용하여 파티에서 마을로 돌아가는 최단 거리를 구해주었다.

풀이

값을 입력받을 때, 정상 방향의 route1과 방향이 전환된 경로 route2로 따로 저장해주었고 각자 다익스트라를 이용하여 각각의 최단거리를 visited1,2배열에 저장해주었다. 그리고 모든 노드들을 순회하면서 visited1,2에 저장되어있는 값들을 더했을때 가장 큰 값을 result에 갱신해주어 출력해주었다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static ArrayList<ArrayList<Pair>> route1 = new ArrayList<>();
    public static ArrayList<ArrayList<Pair>> route2 = new ArrayList<>();
    public static int[] visited1;
    public static int[] visited2;

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

        String[] input = br.readLine().split(" ");

        int N = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);
        int target = Integer.parseInt(input[2]);

        visited1 = new int[N + 1];
        visited2 = new int[N + 1];

        for(int i=0; i<=N; i++) {
            route1.add(new ArrayList<>());
            route2.add(new ArrayList<>());
            visited1[i] = -1;
            visited2[i] = -1;
        }

        for(int i=0; i<M; i++) {
            input = br.readLine().split(" ");
            int a = Integer.parseInt(input[0]);
            int b = Integer.parseInt(input[1]);
            int c = Integer.parseInt(input[2]);

            route1.get(a).add(new Pair(b, c));
            route2.get(b).add(new Pair(a, c));
        }

        PriorityQueue<Pair> pq = new PriorityQueue<>();
        pq.add(new Pair(0, target));
        visited1[target] = 0;

        while(!pq.isEmpty()) {

            Pair cur = pq.poll();

            for(Pair i : route1.get(cur.second)) {

                if(visited1[i.first] == -1 || visited1[i.first] > cur.first + i.second) {

                    visited1[i.first] = cur.first + i.second;
                    pq.add(new Pair(cur.first + i.second, i.first));
                }
            }
        }

        pq.add(new Pair(0, target));
        visited2[target] = 0;

        while(!pq.isEmpty()) {

            Pair cur = pq.poll();

            for(Pair i : route2.get(cur.second)) {

                if(visited2[i.first] == -1 || visited2[i.first] > cur.first + i.second) {

                    visited2[i.first] = cur.first + i.second;
                    pq.add(new Pair(cur.first + i.second, i.first));
                }
            }
        }
        int result = 0;
        for(int i=1; i<=N; i++) {
            result = Math.max(result, visited1[i] + visited2[i]);
        }

        System.out.println(result);
    }

    public static class Pair implements Comparable<Pair>{
        public int first;
        public int second;

        public Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }

        @Override
        public int compareTo(Pair o) {
            if(this.first > o.first)
                return 1;
            else if(this.first < o.first)
                return -1;
            else {
                if(this.second > o.second)
                    return 1;
                else if(this.second < o.second)
                    return -1;
                else
                    return 0;
            }
        }
    }
}