(SPOJ) Copa do Mundo - Solution

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

The problem wants us to find a path among the cities that results in a minimum cost. For this reason, the solution below used Prim's algorithm.

P.S.: Remember that the railways have priority over the highways.


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

class Main {
    public HashMap<Integer, ArrayList<Edge>> adjList;
   
    public Comparator<Edge> costComparator = new Comparator<Edge>() {
        public int compare(Edge e1, Edge e2) {
            if (e1.type-e2.type == 0) {
                return e1.cost-e2.cost;
            }
            return e1.type-e2.type;
        }  
    };
   
    public int prim(int start, int numCities) {
        Queue<Edge> queue = new PriorityQueue<Edge>(numCities, costComparator);
        queue.add(new Edge(start, 0, 0));
       
        HashSet<Integer> visited = new HashSet<>();
       
        int currTotalCost = 0;
        while (queue.size() > 0) {
            Edge curr = queue.poll();
            int currCity = curr.city;
            int currCost = curr.cost;
           
            if (visited.contains(currCity)) {
                continue;
            }
            visited.add(currCity);
            currTotalCost += currCost;
           
            if (visited.size() == numCities) {
                return currTotalCost;
            }
           
            ArrayList<Edge> reachCities = adjList.get(currCity);
            for (int i = 0; i < reachCities.size(); i++) {
                queue.add(new Edge(reachCities.get(i).city, reachCities.get(i).cost, reachCities.get(i).type));
            }
        }
       
        return currTotalCost;
    }
   
    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 numRailways = Integer.parseInt(s[1]);
        int numHighways = Integer.parseInt(s[2]);
       
        adjList = new HashMap<>();
        for (int i = 1; i <= numCities; i++) {
            adjList.put(i, new ArrayList<Edge>());
        }
       
        int start = 1;
        for (int i = 0; i < numRailways; 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]);
           
            adjList.get(c1).add(new Edge(c2, cost, 0));
            adjList.get(c2).add(new Edge(c1, cost, 0));
           
            start = c1;
        }
       
        for (int i = 0; i < numHighways; 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]);
           
            adjList.get(c1).add(new Edge(c2, cost, 1));
            adjList.get(c2).add(new Edge(c1, cost, 1));
        }
       
        int cost = prim(start, numCities);
       
        System.out.println(cost);
                          
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}

class Edge {
    int city;
    int cost;
    int type;
   
    public Edge(int city, int cost, int type) {
        this.city = city;
        this.cost = cost;
        this.type = type;
    }
}