(UVA) Audiophobia - Solution

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

For this problem, we need to generate the Minimum Spanning Tree (MST). Then, for every edge (street) that we use, we need to keep that one that has the biggest value (decibels).


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

class Main {
    public ArrayList<ArrayList<Edge>> adjList;
     
    public int prim(int start, int end) {
        Queue<Edge> queue = new PriorityQueue<>();
        queue.add(new Edge(start, 0));
       
        HashSet<Integer> visited = new HashSet<>();
       
        int maxSoundIntensity = 0;
        while (queue.size() > 0) {
            Edge curr = queue.poll();
            int currCrossing = curr.crossing;
            int currDecibels = curr.decibels;
           
            if (visited.contains(currCrossing)) {
                continue;
            }
            visited.add(currCrossing);
           
            maxSoundIntensity = Math.max(maxSoundIntensity, currDecibels);
            if (currCrossing == end) {
                return maxSoundIntensity;
            }
           
            ArrayList<Edge> reachNodes = adjList.get(currCrossing);
            for (int i = 0; i < reachNodes.size(); i++) {
                queue.add(new Edge(reachNodes.get(i).crossing, reachNodes.get(i).decibels));
            }
        }
       
        return -1;
    }
   
    public void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
       
        int numCase = 0;
       
        int numCrossings = sc.nextInt();
        int numStreets = sc.nextInt();
        int numQueries = sc.nextInt();
        while (numCrossings != 0 || numStreets != 0 || numQueries != 0) {
            if (numCase > 0) {
                bw.write("\n"); // blank line between two consecutive test cases
            }
           
            adjList = new ArrayList<>();
            for (int i = 0; i <= numCrossings; i++) {
                adjList.add(new ArrayList<Edge>());
            }
           
            for (int i = 0; i < numStreets; i++) {
                int c1 = sc.nextInt();
                int c2 = sc.nextInt();
                int decibels = sc.nextInt();
               
                adjList.get(c1).add(new Edge(c2, decibels));
                adjList.get(c2).add(new Edge(c1, decibels));
            }
           
            bw.write("Case #" + ++numCase + "\n");
            for (int i = 0; i < numQueries; i++) {
                int start = sc.nextInt();
                int end = sc.nextInt();
                int minSoundIntensity = prim(start, end);
                String answer = (minSoundIntensity == -1) ? "no path\n" : (minSoundIntensity+"\n");
                bw.write(answer);
            }
           
            numCrossings = sc.nextInt();
            numStreets = sc.nextInt();
            numQueries = sc.nextInt();
        }
                                      
        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 crossing;
    int decibels;
   
    public Edge(int c, int d) {
        crossing = c;
        decibels = d;
    }
   
    public int compareTo(Edge e) {
        return this.decibels-e.decibels;
    }
}