(SPOJ) Reunião - Solution 1

Link to the problem: http://br.spoj.com/problems/REUNIAO2/

The problem wants us to choose a city observing that the distance that the driver that will have to drive the maximum distance is the minimum. It means that we will need to calculate the distance between every pair of cities.

The Floyd-Warshall algorithm calculates the shortest path between every pair of vertexes in a graph. Therefore, the solution below used this algorithm to find the answer.



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

class Main {
    public int[][] adjMatrix;
   
    public void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        String line = br.readLine();
        String[] s = line.split("\\s");
        int numCities = Integer.parseInt(s[0]);
        int numRoads = Integer.parseInt(s[1]);
           
        adjMatrix = new int[numCities][numCities];
        for (int i = 0; i < numCities; i++) {
            for (int j = 0; j < numCities; j++) {
                adjMatrix[i][j] = 1000000000;
            }
        }
       
        for (int i = 0; i < numRoads; i++) {
            line = br.readLine();
            s = line.split("\\s");
            int c1 = Integer.parseInt(s[0]);
            int c2 = Integer.parseInt(s[1]);
            int cost = Integer.parseInt(s[2]);
           
            adjMatrix[c1][c2] = cost;
            adjMatrix[c2][c1] = cost;
        }
       
        for (int i = 0; i < numCities; i++) {
            for (int j = 0; j < numCities; j++) {
                for (int k = 0; k < numCities; k++) {
                    adjMatrix[j][k] = Math.min(adjMatrix[j][k], adjMatrix[j][i]+adjMatrix[i][k]);
                }
            }
        }
       
        int minDistance = 2000000000;
        for (int i = 0; i < numCities; i++) {
            int maxDistance = -1;
            for (int j = 0; j < numCities; j++) {
                maxDistance = Math.max(maxDistance, adjMatrix[i][j]);
            }
            minDistance = Math.min(minDistance, maxDistance);
        }
       
        System.out.println(minDistance);
                          
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}