[알고리즘] Java / 백준 / 끝나지 않는 파티 / 11265

[알고리즘] Java / 백준 / 끝나지 않는 파티 / 11265

문제

문제 링크

접근 방식

플로이드 와샬 알고리즘으로 각각의 파티장들을 서로 연결하는 가장 짧은 거리를 구하고 이용객의 정보를 받아 해당 거리를 시간 안에 갈 수 있는지 없는지를 출력한다.

코드

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

public class Main_11265 {

	public static void main(String[] args) throws IOException{
		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 mat[][] = new int[N][N];
		
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<N;j++) {
				mat[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for(int k=0;k<N;k++) {
			for(int i=0;i<N;i++) {
				if(i==k) continue;
				for(int j=0;j<N;j++) {
					if(i==j || j==k) continue;
					if(mat[i][j] > mat[i][k]+mat[k][j]) {
						mat[i][j] = mat[i][k]+mat[k][j];
					}
				}
			}
		}
		
		StringBuilder sb = new StringBuilder();
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken())-1;
			int end = Integer.parseInt(st.nextToken())-1;
			int time = Integer.parseInt(st.nextToken());
			
			if(time >= mat[start][end]) {
				sb.append("Enjoy other party\n");
			}else sb.append("Stay here\n");
		}
		
		System.out.print(sb);
	}

}