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

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

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

There are two matrices, one for who is young, and the other one for people aged 30 or more. After filling these matrices, we use Floyd-Warshall to find the minimum cost between every pair of node. Then, for every node, we find which ones of them give us the minimum cost.


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 numEdges = sc.nextInt();
        while (numEdges != 0) {
            int[][] matrixY = new int[numEdges*2][numEdges*2];
            int[][] matrixM = new int[numEdges*2][numEdges*2];
            for (int i = 0; i < numEdges*2; i++) {
                for (int j = 0; j < numEdges*2; j++) {
                    matrixY[i][j] = 10000000;
                    matrixM[i][j] = 10000000;
                }
                matrixY[i][i] = 0;
                matrixM[i][i] = 0;
            }
           
            int index = 0;
            HashMap<Character, Integer> map = new HashMap<>();
            HashMap<Integer, Character> mapReverse = new HashMap<>();
            for (int i = 0; i < numEdges; i++) {
                char age = sc.next().charAt(0);
                char direction = sc.next().charAt(0);
                char n1 = sc.next().charAt(0);
                char n2 = sc.next().charAt(0);
                int cost = sc.nextInt();
               
                if (!map.containsKey(n1)) {
                    map.put(n1, index);
                    mapReverse.put(index++, n1);
                }
                if (!map.containsKey(n2)) {
                    map.put(n2, index);
                    mapReverse.put(index++, n2);
                }
                
                if (age == 'Y') {
                    matrixY[map.get(n1)][map.get(n2)] = Math.min(matrixY[map.get(n1)][map.get(n2)], cost);
                    if (direction == 'B') { // bidirectional
                        matrixY[map.get(n2)][map.get(n1)] = Math.min(matrixY[map.get(n2)][map.get(n1)], cost);
                    }
                }
                else {
                    matrixM[map.get(n1)][map.get(n2)] = Math.min(matrixM[map.get(n1)][map.get(n2)], cost);
                    if (direction == 'B') { // bidirectional
                        matrixM[map.get(n2)][map.get(n1)] = Math.min(matrixM[map.get(n2)][map.get(n1)], cost);
                    }
                }
            }
            char start = sc.next().charAt(0);
            char end = sc.next().charAt(0);
           
            for (int i = 0; i < numEdges*2; i++) {
                for (int j = 0; j < numEdges*2; j++) {
                    for (int k = 0; k < numEdges*2; k++) {
                        matrixY[j][k] = Math.min(matrixY[j][k], matrixY[j][i]+matrixY[i][k]);
                        matrixM[j][k] = Math.min(matrixM[j][k], matrixM[j][i]+matrixM[i][k]);
                    }
                }
            }
           
            TreeSet<Character> places = new TreeSet<>();
            int minCost = 1000000000;
            if (map.get(start) != null && map.get(end) != null) {
                for (int i = 0; i < numEdges*2; i++) {
                    if (matrixY[map.get(start)][i] == 10000000 || matrixM[map.get(end)][i] == 10000000) {
                        continue;
                    }
                    int totalCost = matrixY[map.get(start)][i]+matrixM[map.get(end)][i];
                    minCost = Math.min(minCost, totalCost);
                }
                for (int i = 0; i < numEdges*2; i++) {
                    int totalCost = matrixY[map.get(start)][i]+matrixM[map.get(end)][i];
                    if (totalCost == minCost) {
                        places.add(mapReverse.get(i));
                    }
                }
            }
                       
            if (minCost == 1000000000) {
                bw.write("You will never meet.\n");
            }
            else {
                bw.write(minCost+"");
                for (Character c : places) {
                    bw.write(" " + c);
                }
                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);
    }
}