[백준 1238] - [플로이드 와샬] - 파티 (JAVA)

문제 링크 : https://www.acmicpc.net/problem/1238

---

이 문제는 다익스트라 알고리즘으로 문제를 풀 수 있지만 플로이드 와샬 알고리즘으로도 풀 수 있다. 

1부터 N 까지의 학생의 집을 한번씩 들린다 가정하고 이떄의 값을 K로 둔다.

i 부터 j까지 의 거리와 i 에서 K 까지의 거리와 K에서 j 까지의 거리의 합중 최솟값을 최소시간으로 정하면 된다.

플로이드 와샬 알고리즘으로 각 각의 최소 시간을 구한 다음에 각 학생이 파티를 하는 학생에 집에 가고 오는 거리가 제일 큰 학생의 시간을 출력해주면 된다. 

소스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static int size;
    public static int[][] distance;
    public static int student;
    
    public static int INF = 1000000;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        size = Integer.parseInt(st.nextToken());
        int lineCount = Integer.parseInt(st.nextToken());
        student = Integer.parseInt(st.nextToken());
        
        distance = new int[size+1][size+1];
        
        for(int i=1; i <= size; i++) {
            for(int j=1; j <= size; j++) {
                if(i==j) continue;
                
                distance[i][j] = INF;
            }
        }
        while(lineCount-- > 0) {
            st = new StringTokenizer(br.readLine());
            
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            
            distance[start][end] = Math.min(distance[start][end], cost);
        }
        
        
        
        floydWarshall();
        
        int result = 0;
        
        for(int i=1; i <= size; i++) {
            result = Math.max(result, distance[i][student] + distance[student][i]);
        }
        
        System.out.println(result);
    }
    
    public static void floydWarshall() {
        for(int k=1; k <= size; k++) {
            for(int i=1; i <= size; i++) {
                for(int j=1; j <= size; j++) {
                    distance[i][j] = Math.min(distance[i][j], distance[i][k] + distance[k][j]);
                }
            }
        }
    }
}