(UVA) Bear with me, again.. - Solution 1

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

The solution below used Floyd-Warshall to solve this problem. Through this algorithm, it is possible to know how many days, in the worst case, are spent to travel from one island to another one.


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));
       
        while (sc.hasNext()) {
            int numDays = sc.nextInt(); // max number of days they can stay in the sea
            int speed = sc.nextInt(); // miles a day
           
            ArrayList<Info> coordinates = new ArrayList<>();
            coordinates.add(new Info(0, sc.nextInt(), sc.nextInt(), sc.nextInt())); // start
            coordinates.add(new Info(1, sc.nextInt(), sc.nextInt(), sc.nextInt())); // end
           
            int numIntermediateIslands = sc.nextInt();
            int numTotalIslands = numIntermediateIslands+2;
            for (int i = 2; i < numTotalIslands; i++) { // read coordinates of intermediate islands
                coordinates.add(new Info(i, sc.nextInt(), sc.nextInt(), sc.nextInt()));
            }
           
            double[][] adjMatrix = new double[numTotalIslands][numTotalIslands];
            for (int i = 0; i < numTotalIslands; i++) {       
                for (int j = 0; j < numTotalIslands; j++) {
                    adjMatrix[i][j] = 1000000;  
                }
            }

            // calculate the distance between each pair of island
            for (int i = 0; i < numTotalIslands; i++) {       
                for (int j = i+1; j < numTotalIslands; j++) {
                    // distance between two islands / minus the radius of both islands / it results in how many miles they are distant / divide it by the speed
                    // result: how many days to go from one island to the other
                    double d = (Math.sqrt((coordinates.get(i).x-coordinates.get(j).x)*(coordinates.get(i).x-coordinates.get(j).x)+(coordinates.get(i).y-coordinates.get(j).y)*(coordinates.get(i).y-coordinates.get(j).y)) - coordinates.get(i).radius - coordinates.get(j).radius)/speed;       
                    adjMatrix[i][j] = d;
                    adjMatrix[j][i] = d;
                }
            }

            for (int i = 0; i < numTotalIslands; i++) {       
                for (int j = 0; j < numTotalIslands; j++) {
                    for (int k = 0; k < numTotalIslands; k++) {
                        // instead of "adjMatrix[j][i]+adjMatrix[i][k]", we do "Math.max()" because when you arrive in an island, you start (from 0) counting the days to reach another island
                        adjMatrix[j][k] = Math.min(adjMatrix[j][k], Math.max(adjMatrix[j][i], adjMatrix[i][k]));
                    }
                }
            }

            if (adjMatrix[0][1] <= numDays) {
                bw.write("Larry and Ryan will escape!\n");       
            }
            else {
                bw.write("Larry and Ryan will be eaten to death.\n");
            }       
        }
                       
        bw.flush();
        bw.close();
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}

class Info {
    int id;
    int x;
    int y;
    int radius;
   
    public Info(int id, int x, int y, int radius) {
        this.id = id;
        this.x = x;
        this.y = y;
        this.radius = radius;
    }
}

class Distance {
    int id1;
    int id2;
    double distance;
       
    public Distance(int id1, int id2, double distance) {
        this.id1 = id1;
        this.id2 = id2;
        this.distance = distance;
    }
}