(UVA) Meeting Prof. Miguel... - Solution 2

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

If you want to see another solution for this problem, click here.

As the previous solution, this one also used Floyd-Warshall algorithm to solve this problem. The difference is that this solution has some improvements:

• We only have one matrix with 3 dimensions. One of them is related to who is young and who is aged 30 or more.
• We do not use a map structure to map the letters to numbers. It is done simply by decreasing 'A' of the character read.
• We assume that the maximum number of letters (nodes) is 26 (A-Z).

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

class Main { 
    public final int MAX_SIZE = 26;
   
    public void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
      
        int numEdges = sc.nextInt();
        while (numEdges != 0) {
            // 3D matrix - 1st dimension is related to (young) and (mature)
            int[][][] matrix = new int[2][MAX_SIZE][MAX_SIZE];
            // iniate matrix (infinite)
            for (int k = 0; k < 2; k++) {
                for (int i = 0; i < MAX_SIZE; i++) {
                    for (int j = 0; j < MAX_SIZE; j++) {
                        matrix[k][i][j] = 10000000;
                    }
                    matrix[k][i][i] = 0; // from a place to itself, cost is zero
                }
            }
                      
            // read edges and fill matrix          
            for (int i = 0; i < numEdges; i++) {
                char age = sc.next().charAt(0);
                char direction = sc.next().charAt(0);
                int n1 = sc.next().charAt(0)-'A';
                int n2 = sc.next().charAt(0)-'A';
                int cost = sc.nextInt();

                int index = (age == 'Y')? 0 : 1;
                matrix[index][n1][n2] = Math.min(matrix[index][n1][n2], cost);
                if (direction == 'B') { // bidirectional
                    matrix[index][n2][n1] = Math.min(matrix[index][n2][n1], cost);
                }
            }
          
            // check the minimum cost between every pair of node
            for (int l = 0; l < 2; l++) {
                for (int i = 0; i < MAX_SIZE; i++) {
                    for (int j = 0; j < MAX_SIZE; j++) {
                        for (int k = 0; k < MAX_SIZE; k++) {
                            matrix[l][j][k] = Math.min(matrix[l][j][k], matrix[l][j][i]+matrix[l][i][k]);
                        }
                    }
                }
            }
                      
            int minCost = 1000000000;
            int start = sc.next().charAt(0)-'A';
            int end = sc.next().charAt(0)-'A';
            // check the minimum cost to meet, if it exists
            for (int i = 0; i < MAX_SIZE; i++) {
                if (matrix[0][start][i] == 10000000 || matrix[1][end][i] == 10000000) {
                    continue;
                }
                int totalCost = matrix[0][start][i]+matrix[1][end][i];
                minCost = Math.min(minCost, totalCost);
            }
          
            // print answer
            if (minCost == 1000000000) {
                bw.write("You will never meet.\n"); // if it not exist a way to meet
            }
            else {
                // check every place (node) to meet which has the minimum cost
                bw.write(minCost+"");
                for (int i = 0; i < MAX_SIZE; i++) {
                    int totalCost = matrix[0][start][i]+matrix[1][end][i];
                    if (totalCost == minCost) {
                        bw.write(" " + (char)(i+65));
                    }
                }
                bw.write("\n");
            }
                                  
            numEdges = 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);
    }
}