(UVA) 05-2 Rendezvous - Solution

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

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

It is necessary to sum the values in every row to achieve the answer.


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 numCase = 0;
        int numMembers = sc.nextInt();
        int numPaths = sc.nextInt();
        while (numMembers != 0 || numPaths != 0) {
            String[] names = new String[numMembers];
            for (int i = 0; i < numMembers; i++) {
                names[i] = sc.next();
            }      
          
            int[][] matrix = new int[numMembers][numMembers];
            for (int i = 0; i < numMembers; i++) {
                for (int j = 0; j < numMembers; j++) {
                    matrix[i][j] = Integer.MAX_VALUE/2;
                }
                matrix[i][i] = 0;
            }
              
            for (int i = 0; i < numPaths; i++) {
                int p1 = sc.nextInt()-1;
                int p2 = sc.nextInt()-1;
                int cost = sc.nextInt();
              
                matrix[p1][p2] = cost;
                matrix[p2][p1] = cost;
            }
          
            for (int i = 0; i < numMembers; i++) {
                for (int j = 0; j < numMembers; j++) {
                    for (int k = 0; k < numMembers; k++) {
                        matrix[j][k] = Math.min(matrix[j][k], matrix[j][i]+matrix[i][k]);
                    }
                }
            }
          
            int index = 0;
            int minValue = Integer.MAX_VALUE;
            for (int i = 0; i < numMembers; i++) {
                int sum = 0;
                for (int j = 0; j < numMembers; j++) {
                    sum += matrix[i][j];
                }
                if (sum < minValue) {
                    minValue = sum;
                    index = i;
                }
            }
          
            bw.write("Case #"+(++numCase)+" : "+names[index]+"\n");
          
            numMembers = sc.nextInt();
            numPaths = sc.nextInt();       
        }
                                                     
        bw.flush();
        bw.close();
      
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
      
        System.exit(0);
    }
}