[BOJ]1238 - 파티(G3)

문제 링크

1238-파티

---

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다.

두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다.
시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.

모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.

출력

첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

---

문제 풀이

다익스트라 알고리즘을 이용하는 문제

일단, 처음에 문제 제대로 안읽어서 좀 헤맴
오고가는!!!!을 똑바로 안읽어서..하하..

우선 전체적으로 집에서 X로 가는, X에서 집으로 가는 시간을 구하기 위해서는
출발점과 도착점을 반대로 하는 배열을 정의해주는게 편하다

이 부분만 제외하면 일반적인 다익스트라 알고리즘 문제였다.
마지막에는 왕복시간이 가장 오래 걸리는 시간을 출력해야하기 때문에
값과 두 배열의 같은 인덱스값의 합을 비교해 최대값을 구해서 출력!

사소한거일 수 있지만, 배열 크기들을 N으로 맞추냐 N+1로 맞추냐때문에 잠깐 헤맸다..
다음부턴 좀 제대로 읽고 생각해야지

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Town implements Comparable<Town> {

    int end, time;

    Town(int end, int time) {
        this.end = end;
        this.time = time;
    }

    @Override
    public int compareTo(Town o) {
        return time - o.time;
    }
}

public class Main {

    final static int INF = 1000000000;
    static int N,M,X;
    static ArrayList<ArrayList<Town>> maps, mapsReverse;
    static int[] dist, distReverse;


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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());

        maps = new ArrayList<>();
        mapsReverse = new ArrayList<>();

        for (int i = 0; i <= N; i++) {
            maps.add(new ArrayList<>());
            mapsReverse.add(new ArrayList<>());
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());

            maps.get(s).add(new Town(e, t));
            mapsReverse.get(e).add(new Town(s, t));
        }

        dist = new int[N + 1];
        distReverse = new int[N + 1];

        dijkstra(maps, dist);
        dijkstra(mapsReverse, distReverse);

        int ans = -1;
        for (int i = 1; i <= N; i++) {
            ans = Math.max(ans, dist[i] + distReverse[i]);
        }
        System.out.println(ans);

    }

    public static void dijkstra(ArrayList<ArrayList<Town>> list, int[] distance ) {

        PriorityQueue<Town> pq = new PriorityQueue<>();
        pq.offer(new Town(X, 0));

        boolean[] visited = new boolean[N + 1];
        Arrays.fill(distance, INF);
        distance[X] = 0;

        while (!pq.isEmpty()) {
            int cur = pq.poll().end;

            if (!visited[cur]) {
                visited[cur] = true;

                for (Town town : list.get(cur)) {
                    if (distance[town.end] > distance[cur] + town.time) {
                        distance[town.end] = distance[cur] + town.time;
                        pq.add(new Town(town.end, distance[town.end]));
                    }
                }
            }
        }
    }
}