백준 9205 맥주 마시면서 걸어가기 (자바)

import java.util.ArrayList;
import java.util.Arrays;

import java.util.Scanner;
import java.io.FileInputStream;


class Solution
{
	public static void main(String args[]) throws Exception
	{

		System.setIn(new FileInputStream("sample_input.txt"));


		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();

		for(int test_case = 1; test_case <= T; test_case++)
		{
			int INF = 10000000;
			int N = sc.nextInt()+2;
			int[][] graph=new int[N][N];
			ArrayList<Node> nodes = new ArrayList<>();
			for (int i = 0; i < N; i++) {
				nodes.add(new Node(sc.nextInt(),sc.nextInt()));
			}
			for (int i = 0; i < N; i++) {
				for (int j = i+1; j < graph.length; j++) {
					int dist = getDistance(nodes.get(i),nodes.get(j));
					if(dist<=1000) {
						graph[i][j]=1;
						graph[j][i]=1;
					}
					else {
						graph[i][j]=INF;
						graph[j][i]=INF;
					}
				}
			}
			
			for (int k = 0; k < N; k++) {
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						graph[i][j] = Math.min(graph[i][j], graph[i][k]+graph[k][j]);
					}
				}
			}
			if(graph[0][N-1]!=INF)System.out.println("happy");
			else System.out.println("sad");
		}
	}

	private static int getDistance(Node node1, Node node2) {
		// 
		return Math.abs(node1.x-node2.x)+Math.abs(node1.y - node2.y);
	}
	
}
class Node{
	int x;
	int y;
	
	public Node(int x, int y) {
		super();
		this.x = x;
		this.y = y;
	}

	
}