(UVA) Thunder Mountain - Solution

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=682&page=show_problem&problem=1744

The solution below calculates the distance between every pair of town. If the distance is bigger than 10, we do not consider this distance. Next, we fill an adjacency matrix using Floyd-Warshall algorithm. Then, we only need to find the biggest distance between any two pairs of towns.


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

class Main {   
    public void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
       
        int numTests = sc.nextInt();
        for (int i = 0; i < numTests; i++) {
            int numNodes = sc.nextInt();       
            Info[] nodes = new Info[numNodes];
            for (int j = 0; j < numNodes; j++) {
                nodes[j] = new Info(j, sc.nextInt(), sc.nextInt());
            }
           
            double[][] adjMatrix = new double[numNodes][numNodes];
            for (int j = 0; j < numNodes; j++) {
                for (int k = 0; k < numNodes; k++) {
                    adjMatrix[j][k] = 1000000;  
                }
            }
           
            for (int j = 0; j < numNodes; j++) {
                for (int k = j+1; k < numNodes; k++) {
                    double d = Math.sqrt((nodes[j].x-nodes[k].x)*(nodes[j].x-nodes[k].x)+(nodes[j].y-nodes[k].y)*(nodes[j].y-nodes[k].y));
                    if (d <= 10) {
                        adjMatrix[j][k] = d;
                        adjMatrix[k][j] = d;
                    }
                }
            }
           
            for (int j = 0; j < numNodes; j++) {       
                for (int k = 0; k < numNodes; k++) {
                    for (int l = 0; l < numNodes; l++) {
                        adjMatrix[k][l] = Math.min(adjMatrix[k][l], adjMatrix[k][j]+adjMatrix[j][l]);
                    }
                }
            }
           
            double max = 0;
            for (int j = 0; j < numNodes; j++) {
                for (int k = 0; k < numNodes; k++) {
                    if (j == k) {
                        continue;
                    }
                    max = Math.max(max, adjMatrix[j][k]);
                }
            }
           
            System.out.println("Case #" + (i+1) + ":");
            if (max != 1000000) {
                System.out.printf("%.4f\n", max);
            }
            else {
                System.out.println("Send Kurdy");
            }
            System.out.println();
        }
                       
        bw.flush();
        bw.close();
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}

class Info {
    int id;
    int x;
    int y;
   
    public Info(int id, int x, int y) {
        this.id = id;
        this.x = x;
        this.y = y;
    }
}