(UVA) Commandos - Solution

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

The solution below used Floyd-Warshall to solve this problem. After filling the adjacency matrix, it is necessary to calculate the distance from the start to every other node. Then, we also need to calculate the distance from every node to the end.


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();
            int numRoads = sc.nextInt();
           
            int[][] adjMatrix = new int[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 < numRoads; j++) {
                int n1 = sc.nextInt();
                int n2 = sc.nextInt();
                adjMatrix[n1][n2] = 1;
                adjMatrix[n2][n1] = 1;
            }
           
            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]);
                    }
                }
            }
           
            int start = sc.nextInt();
            int end = sc.nextInt();
            int[] distance = new int[numNodes];
            // distance from start to every other node
            for (int j = 0; j < numNodes; j++) {
                if (j == start) {
                    distance[j] = 0;
                    continue;
                }
                distance[j] = adjMatrix[start][j];
            }
            // distance from every node to the end
            int max = 0;
            for (int j = 0; j < numNodes; j++) {
                if (j == end) {
                    continue;
                }
                max = Math.max(max, distance[j]+adjMatrix[j][end]);
            }
           
            bw.write("Case " + (i+1) + ": " + max + "\n");
        }
               
        bw.flush();
        bw.close();
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}