BOJ - 1238 ) 파티

개발자가될수있을까? 2020. 4. 16. 11:13

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

1238번: 파티

문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다. 이 도로들은 단방향이기 때

www.acmicpc.net

N개의 노드에서 다시 자신의 노드로 돌아오는데에 최댓값을 구하는 문제이다.

1~N까지 Floye-Warshall 알고리즘을 통해 최단경로를 구해놓고,

map[x][i] + map[i][x] 의 값이 가장 큰 사람을 출력한다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 파티 {
	// 플로이드워셜
	// 모든 최단거리중 가장 많이 시간을 소비하는 사람 출력
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st =  new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int x = Integer.parseInt(st.nextToken());
		int map[][] = new int[n+1][n+1];
		for(int i= 1 ; i <=n ; i++) {
			for(int j = 1 ; j <=n ; j ++) {
				map[i][j] =987654321;
			}
			map[i][i] =0;
		}
		for(int i = 0 ; i < m ; i ++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b= Integer.parseInt(st.nextToken());
			map[a][b] = Integer.parseInt(st.nextToken());
		}
		for(int mid = 1 ; mid <= n ;mid++) {
			for(int start =1 ; start <=n ; start++) {
				for(int end=1; end<=n ; end++) {
					{
						if(map[start][end] > map[start][mid] + map[mid][end]) {
							map[start][end] = map[start][mid] + map[mid][end];
						}
					}
				}
			}
		}
		int ans = -1;
		
		for(int i= 1 ; i <=n ; i++) {
			if(map[i][x] + map[x][i] > ans) {
				ans = map[i][x] + map[x][i]; 
			}
		}
		System.out.println(ans);
		
	}
}