[JAVA] 백준 1238 - 파티

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

한 정점에서 파티가 열리고, 다른 정점에서 해당 정점으로 최단거리로 방문했다가 다시 돌아갈 때, 가중치가 가장 높은 정점의 가중치를 출력하는 문제이다.

사실 입력 조건 중 정점의 개수를 100으로 보고 100만번이면 플로이드-워셜 써도 되겠다~ 하고 플로이드로 풀었는데 

다시보니 1000이여서 10억번이면 무조건 시간초과를 생각이 들었고 일단 아쉬운 김에 제출해봤는데 통과했다.

 

정석적인 풀이는 파티가 열리는 정점에서 다익스트라를 돌리고, 간선의 방향을 전부 반대로 해서 다시 다익스트라를 돌리는 것이라고 한다.

또 하나 배워갑니다.

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] a = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int sCount = a[0];
        int rCount = a[1];
        int party = a[2];
        int[][] map = new int[sCount][sCount];

        for (int i = 0; i < sCount; i++) {
            Arrays.fill(map[i], 100001);
            map[i][i] = 0;
        }
        for (int i = 0; i < rCount; i++) {
            int[] t = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            map[t[0] - 1][t[1] - 1] = t[2];
        }

        for (int k = 0; k < sCount; k++) {
            for (int i = 0; i < sCount; i++) {
                for (int j = 0; j < sCount; j++) {
                    if (map[i][k] + map[k][j] < map[i][j]) {
                        map[i][j] = map[i][k] + map[k][j];
                    }
                }
            }
        }
        int[] answer = new int[sCount];
        for (int i = 0; i < sCount; i++) {
            answer[i] += map[i][party-1]; //i번째 학생이 파티까지 가는 시간
            answer[i] += map[party-1][i]; //파티에서 i번째 학생 집까지 가는 시간
        }

        System.out.println(Arrays.stream(answer).max().getAsInt());
    }
}