[Gold III] 파티 - 1238

문제 링크

성능 요약

메모리: 91940 KB, 시간: 756 ms

분류

데이크스트라, 그래프 이론, 최단 경로

제출 일자

2024년 11월 22일 14:01:03

문제 설명

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 T_i(1 ≤ T_i ≤ 100)의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 T_i가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.

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

출력

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

각 도시에서 반환점 X에 도달한 후 다시 해당 도시에 도착하는 거리(A -> C -> A) 중 최장 거리를 구해야 한다
시작 지점과 목표 지점을 매개변수로 받았을 때 목표 지점까지의 거리를 반환해 주는 dijkstra 메서드를 구현
main 메서드에서 반복문을 통해 dijkstra(i, X) + dijkstra(X, i)로 도시별 목표 도시까지의 왕복 거리를 계산
계산된 거리 중 최댓값을 반환

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

class Main {
    static int N;
    static List<int[]>[] graph;

    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()); // 학생 수
        int M = Integer.parseInt(st.nextToken()); // 간선 수
        int X = Integer.parseInt(st.nextToken()); // 반환점

        graph = new List[N+1];

        for(int i=0; i<=N; i++){
            graph[i] = new ArrayList<>();
        }

        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            graph[from].add(new int[]{to, cost});
        }

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

        for (int i = 1; i <= N; i++) {
        	// 도시별 왕복 거리
            dist[i] = dijkstra(i, X) + dijkstra(X, i);
        }

        System.out.println(Arrays.stream(dist).max().getAsInt());

        br.close();
    }

    static int dijkstra(int start, int end){
        boolean[] visited = new boolean[N+1];
        int[] dist = new int[N+1];
        Arrays.fill(dist, Integer.MAX_VALUE);

        dist[start] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
        pq.offer(new int[]{start, 0});

        while(!pq.isEmpty()){
            int[] info = pq.poll();
            int cur = info[0];
            int curCost = info[1];

            if(visited[cur])
                continue;

            visited[cur] = true;

            for(int[] nextInfo : graph[cur]){
                int next = nextInfo[0];
                int nextCost = nextInfo[1];

                if(dist[next] > curCost +  nextCost){
                    dist[next] = curCost + nextCost;
                    pq.offer(new int[]{next, dist[next]});
                }
            }
        }

        return dist[end];
    }
}