(UVA) Subway - Solution

I used Dijkstra's algorithm to solve this problem.

First, I read the entries, and associate every type of coordinate to a type, for example:

• Coordinate of home: type 0
• Coordinate of school: type 1
• Coordinate of the first subway: type 2
• Coordinate of the second subway: type 3
• And so on...

These types will help me to see if I am walking (10km/h) or taking a subway (40km/h). Then, during the Dijkstra method, I need to check the types of every two different coordinates to evaluate the situation.


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

class Main  {
    public static HashMap<Integer, Coord> map;
    public static ArrayList<Type> listCoords;
   
    public static double time(Coord c1, Coord c2, int v) {
        return (Math.sqrt((c2.x-c1.x)*(c2.x-c1.x)+(c2.y-c1.y)*(c2.y-c1.y))*60)/v;
    }
   
    public static Comparator<Time> timeComparator = new Comparator<Time>() {
        public int compare(Time t1, Time t2) {
            if ((t1.time - t2.time) < 0) {
                return -1;
            }
            else if ((t1.time - t2.time) > 0) {
                return 1;
            }
           
            return 0;
        }
    };
   
    public static double dijkstra(int start, int end, int numNodes) {
        Queue<Time> queue = new PriorityQueue<Time>(numNodes, timeComparator);
        Time t = new Time(start, 0, 0);
        queue.add(t);

        HashSet<Integer> visited = new HashSet<Integer>();
       
        double time = 0.0;
        while (queue.size() > 0) {
            Time curr = queue.poll();
            int currNode = curr.node;
            int currType = curr.type;
            double currTime = curr.time;

            if (visited.contains(currNode)) {
                continue;
            }
            visited.add(currNode);

            if (currNode == end) {
                return currTime;
            }
           
            for (int i = 0; i < numNodes; i++) {
                if (i != currNode) {
                    if (currType == listCoords.get(i).type) { // if they are the same type (subways)
                        if (currNode+1 == i || currNode-1 == i) {
                        }
                        else {
                            time = time(map.get(currNode), listCoords.get(i).c, 10000);
                            t = new Time(i, listCoords.get(i).type, currTime+time);
                            queue.add(t);
                            continue;
                        }
                    }
                    if (currType == listCoords.get(i).type) {
                        time = time(map.get(currNode), listCoords.get(i).c, 40000);
                    }
                    else {
                        time = time(map.get(currNode), listCoords.get(i).c, 10000);
                    }
                    t = new Time(i, listCoords.get(i).type, currTime+time);
                    queue.add(t);
                }
            }
        }
       
        return time;
    }
   
    public static void process() throws NumberFormatException, IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        String line = br.readLine();
        int numCases = Integer.parseInt(line);
        for (int i = 0; i < numCases; i++) {
            if (i == 0) {
                br.readLine();
            }
            else {
                System.out.println();
            }
           
            map = new HashMap<Integer, Coord>();
            listCoords = new ArrayList<Type>();
           
            int indexMap = 0;
            int indexType = 0;
           
            line = br.readLine();
            String[] s = line.split("\\s");
           
            int x = Integer.parseInt(s[0]);
            int y = Integer.parseInt(s[1]);
            map.put(indexMap++, new Coord(x, y));
            listCoords.add(new Type(indexType++, new Coord(x, y)));
           
            x = Integer.parseInt(s[2]);
            y = Integer.parseInt(s[3]);
            map.put(indexMap++, new Coord(x, y));
            listCoords.add(new Type(indexType++, new Coord(x, y)));
           
            line = br.readLine();
            while (!line.equals("")) {
                s = line.split("\\s");
                for (int j = 0; j < s.length-2; j += 2) {
                    x = Integer.parseInt(s[j]);
                    y = Integer.parseInt(s[j+1]);
                    map.put(indexMap++, new Coord(x, y));
                    listCoords.add(new Type(indexType, new Coord(x, y)));
                }
                indexType++;
                line = br.readLine();
                if (line == null) {
                    break;
                }
            }
                       
            int numNodes = indexMap;
            double time = dijkstra(0, 1, numNodes);
            System.out.println(Math.round(time));
        }
                                                
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}

class Coord {
    int x;
    int y;
   
    public Coord(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

class Type {
    int type;
    Coord c;
   
    public Type(int type, Coord c) {
        this.type = type;
        this.c = c;
    }
}

class Time {
    int node;
    int type;
    double time;
   
    public Time(int node, int type, double time) {
        this.node = node;
        this.type = type;
        this.time = time;
    }
}