📝문제

방향성이 있고, 가중치가 없을 때의 최단거리를 구하는 문제이므로 플로이드-와샬 알고리즘을 사용했다.
플로이드-와샬 알고리즘은,
출발점에서 도착점으로 직행하는 경우보다 한 곳을 경유하는 경우의 거리가 더 짧다면 출발점과 도착점 사이의 최단거리를 경유했을 때의 거리로 바꾼다.
이를 모든 노드에 대해 반복했을 때 각 거리는 최단거리가 된다.

📌코드

package Baekjoon;

import java.io.*;
import java.util.*;

public class BOJ11265 {

    static int n; //파티장의 크기
    static int m; //손님 수
    static int[][] cost; //파티장끼리의 거리

    public static void main(String[] args) throws IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        cost = new int[n+1][n+1];
        for(int i = 1; i < n+1; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j < n+1; j++){
                cost[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        StringBuilder sb = new StringBuilder();
        /**
         * 방향성이 있고 가중치가 없다 -> 플로이드 와샬 알고리즘
         * m 줄의 입력을 받기 전에 cost 배열을 최단거리로 수정한다
         */
        for(int middle = 1; middle < n+1; middle++){
            for(int start = 1; start < n+1; start++){
                for(int end = 1; end < n+1; end++){
                    cost[start][end] = Math.min(cost[start][end], cost[start][middle]+cost[middle][end]);
                }
            }
        }
        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            long time = Long.parseLong(st.nextToken());
            if(cost[start][end] <= time) {
                sb.append("Enjoy other party").append("\n");
            } else {
              sb.append("Stay here").append("\n");
            }
        }
        System.out.println(sb);
    }
}