(UVA) Oreon - Solution 2

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

If you want to see another solution for this problem, click here.

This solution used Prim's algorithm to solve this problem.


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

class Main {
    public ArrayList<ArrayList<Edge>> adjList;
    public Queue<Edge> edges;
   
    public void prim(int start, int numCities) {
        Queue<Edge> queue = new PriorityQueue<>();
        queue.add(new Edge(start, 0, -1));
       
        HashSet<Integer> visited = new HashSet<>();
       
        while (queue.size() > 0) {
            Edge curr = queue.poll();
            int currCity = curr.city;
            int currCost = curr.cost;
            int currParent = curr.parent;
           
            if (visited.contains(currCity)) {
                continue;
            }
            visited.add(currCity);
           
            if (currParent != -1) {
                edges.add(new Edge((currCity <= currParent) ? currCity : currParent, currCost, (currCity <= currParent) ? currParent : currCity));
            }
            if (visited.size() == numCities) {
                return;
            }
           
            ArrayList<Edge> reachable = adjList.get(currCity);
            for (int i = 0; i < reachable.size(); i++) {
                queue.add(new Edge(reachable.get(i).city, reachable.get(i).cost, currCity));
            }
        }
    }
   
    public void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int numTests = Integer.parseInt(br.readLine());
        for (int test = 0; test < numTests; test++) {
            int numCities = Integer.parseInt(br.readLine());
           
            adjList = new ArrayList<>();
            for (int i = 0; i < numCities; i++) {
                adjList.add(new ArrayList<Edge>());
            }
           
            for (int i = 0; i < numCities; i++) {
                String line = br.readLine();
                line = line.replace(" ", "");
                String[] s = line.split(",");
                for (int j = 0; j < numCities; j++) {
                    if (Integer.parseInt(s[j]) == 0) {
                        continue;
                    }
                    adjList.get(i).add(new Edge(j, Integer.parseInt(s[j]), -1));
                    adjList.get(j).add(new Edge(i, Integer.parseInt(s[j]), -1));
                }               
            }
           
            edges = new PriorityQueue<>();
            prim(0, numCities);
           
            int size = edges.size();
            bw.write("Case "+(test+1)+":\n");
            for (int i = 0; i < size; i++) {
                Edge e = edges.poll();
                bw.write((char)(e.city+'A')+"-"+(char)(e.parent+'A')+" "+e.cost+"\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 Edge implements Comparable<Edge> {
    int city;
    int cost;
    int parent;
   
    public Edge(int ci, int co, int p) {
        city = ci;
        cost = co;
        parent = p;
    }
   
    public int compareTo(Edge e) {
        if (this.cost-e.cost == 0) {
            return this.parent-e.parent;
        }
        return this.cost-e.cost;
    }
}