(UVA) Traffic Flow - Solution

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

We need to find a path such that the minimum capacity among all of the remaining roads is as large as possible. For this reason, the solution below uses a modified Prim's algorithm. Instead of choosing the edges which the cost is the minimum, we choose those with the maximum cost. Then, we only need to keep which one of these chosen edges has the minimum value (minimum capacity).


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

class Main {  
    public ArrayList<ArrayList<Edge>> adjList;
    
    public int prim(int start, int numNodes) {
        Queue<Edge> queue = new PriorityQueue<>();
        queue.add(new Edge(start, Integer.MAX_VALUE));
       
        HashSet<Integer> visited = new HashSet<>();
       
        int minCost = Integer.MAX_VALUE;
        while (queue.size() > 0) {
            Edge curr = queue.poll();
            int currNode = curr.node;
            int currCost = curr.cost;
           
            if (visited.contains(currNode)) {
                continue;
            }
            visited.add(currNode);
           
            minCost = Math.min(minCost, currCost);
           
            ArrayList<Edge> reachNodes = adjList.get(currNode);
            for (int i = 0; i < reachNodes.size(); i++) {
                queue.add(new Edge(reachNodes.get(i).node, reachNodes.get(i).cost));
            }
        }
       
        return minCost;
    }
   
    public void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
       
        int numTests = sc.nextInt();
        for (int i = 0; i < numTests; i++) {
            int numNodes = sc.nextInt();
            int numEdges = sc.nextInt();
           
            adjList = new ArrayList<>();
            for (int j = 0; j < numNodes; j++) {
                adjList.add(new ArrayList<Edge>());
            }
           
            for (int j = 0; j < numEdges; j++) {
                int n1 = sc.nextInt();
                int n2 = sc.nextInt();
                int cost = sc.nextInt();
               
                adjList.get(n1).add(new Edge(n2, cost));
                adjList.get(n2).add(new Edge(n1, cost));
            }
           
            int minCapacity = prim(0, numNodes);
            bw.write("Case #" + (i+1) + ": " + minCapacity + "\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 node;
    int cost;
   
    public Edge(int n, int c) {
        node = n;
        cost = c;
    }
   
    public int compareTo(Edge e) {
        return e.cost-this.cost;
    }
}