(UVA) Page Hopping - Solution

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

This problem asks us to determine the average shortest path length between every pair of nodes. However, first, we need to calculate the shortest path length between every pair of nodes, and it is what the Floyd-Warshall algorithm does.


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

class Main {   
    public int[][] matrix;
   
    public void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
       
        int numCase = 0;
               
        int p1 = sc.nextInt();
        int p2 = sc.nextInt();
        while (p1 != 0 || p2 != 0) {
            matrix = new int[100][100];
            for (int i = 0; i < 100; i++) {
                for (int j = 0; j < 100; j++) {
                    matrix[i][j] = 10000000;
                }
                matrix[i][i] = 0;
            }

            while (p1 != 0 || p2 != 0) {
                matrix[p1-1][p2-1] = 1;
                p1 = sc.nextInt();
                p2 = sc.nextInt();
            }       
           
            for (int i = 0; i < 100; i++) {
                for (int j = 0; j < 100; j++) {
                    for (int k = 0; k < 100; k++) {
                        matrix[j][k] = Math.min(matrix[j][k], matrix[j][i]+matrix[i][k]);
                    }
                }
            }
           
            int qty = 0;
            int sum = 0;
            for (int i = 0; i < 100; i++) {
                for (int j = 0; j < 100; j++) {
                    if (matrix[i][j] == 0 || matrix[i][j] == 10000000) {
                        continue;
                    }
                    sum += matrix[i][j];
                    qty++;
                }
            }
           
            System.out.printf("Case %d: average length between pages = %.3f clicks\n", ++numCase, (double)sum/qty);
       
            p1 = sc.nextInt();
            p2 = sc.nextInt();
        }       
                                              
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}