[BOJ] 파티

 

문제

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

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

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

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

풀이

출발지 -> 도착지 -> 출발지의 거리를 탐색하면서 비용이 가장 큰 사람을 구하면 된다.
각 노드별 모두의 최단 겨리를 알아야 하므로 플로이드 워셜을 사용하였다.

플로이드 워셜을 이용하여 노드 모두의 최단 거리를 구한 후, 출발지 + 도착지 + 출발지 모두의
거리가 가장 큰 값을 구하도록 하였다.

import java.lang.\*;  
import java.io.\*;  
import java.util.\*;  

public class Main {  

    static int\[\]\[\] distance;  
    static int MAX\_INT = 10000;  

    public static void main(String\[\] args) throws Exception {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        String\[\] str = br.readLine().split(" ");  
        int N = Integer.parseInt(str\[0\]);  
        int M = Integer.parseInt(str\[1\]);  
        int X = Integer.parseInt(str\[2\]);  
        int answer = 0;  
        distance = new int\[N + 1\]\[N + 1\];  

        for (int i = 1; i <= N; i++) {  
            for (int j = 1; j <= N; j++) {  
                if (i == j) {  
                    continue;  
                }  
                distance\[i\]\[j\] = MAX\_INT;  
            }  
        }  

        for (int i = 0; i < M; i++) {  
            str = br.readLine().split(" ");  
            int a = Integer.parseInt(str\[0\]);  
            int b = Integer.parseInt(str\[1\]);  
            int value = Integer.parseInt(str\[2\]);  
            distance\[a\]\[b\] = value;  
        }  


        for (int k = 1; k <= N; k++) {  
            for (int i = 1; i <= N; i++) {  
                for (int j = 1; j <= N; j++) {  
                    distance\[i\]\[j\] = Math.min(distance\[i\]\[j\], distance\[i\]\[k\]+distance\[k\]\[j\]);  
                }  
            }  
        }  

        for (int i = 1; i <= N; i++) {  
            for (int j = 1; j <= N; j++) {  
                Syste[m.out.print(distance\[i\]\[j\]](http://m.out.print\(distance[i][j]) + " ");  
            }  
            System.out.println();  
        }  

        for (int i = 1; i <= N; i++) {  
            answer = Math.max(answer, distance\[i\]\[X\] + distance\[X\]\[i\]);  
        }  

        System.out.println(answer);  

    }  

}