(UVA) The Orc Attack - Solution

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

The solution below used Floyd-Warshall to solve this problem.


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 test = 0; test < numTests; test++) {
            int numLocations = sc.nextInt();
            int numConnections = sc.nextInt();
           
            int[][] matrix = new int[numLocations][numLocations];
            for (int i = 0; i < numLocations; i++) {
                for (int j = 0; j < numLocations; j++) {
                    matrix[i][j] = Integer.MAX_VALUE/2;
                }
                matrix[i][i] = 0;
            }
           
            for (int i = 0; i < numConnections; i++) {
                int l1 = sc.nextInt()-1;
                int l2 = sc.nextInt()-1;
                int cost = sc.nextInt();
               
                matrix[l1][l2] = Math.min(matrix[l1][l2], cost);
                matrix[l2][l1] = Math.min(matrix[l2][l1], cost);
            }
           
            for (int i = 0; i < numLocations; i++) {
                for (int j = 0; j < numLocations; j++) {
                    for (int k = 0; k < numLocations; k++) {
                        matrix[j][k] = Math.min(matrix[j][k], matrix[j][i]+matrix[i][k]);
                    }
                }
            }
           
            int minDistance = Integer.MAX_VALUE/2;
            for (int i = 5; i < numLocations; i++) {
                int d = matrix[i][0];
                boolean possible = true;
                for (int j = 1; j < 5; j++) {
                    if (matrix[i][j] != d) {
                        possible = false;
                        break;
                    }
                }
                if (possible) {
                    int maxDistance = -1;
                    for (int j = 0; j < numLocations; j++) {
                        if (j == i) {
                            continue;
                        }
                        maxDistance = Math.max(maxDistance, matrix[i][j]);
                    }
                    minDistance = Math.min(minDistance, maxDistance);
                }
            }
           
            minDistance = (minDistance == Integer.MAX_VALUE/2) ? -1 : minDistance;
            bw.write("Map " + (test+1) + ": " + minDistance+"\n");
        }
                                                                      
        bw.flush();
        bw.close();
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}