(UVA) Heavy Cargo - Solution

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

Knowing the maximum load that a truck can transport between two given cities, we need to determine the maximum load that can be transported from a start to a destination city. For this reason, the solution below uses a modified Prim's algorithm. Instead of choosing the edges which the weight limit is the minimum, we choose those with the maximum weight limit. Then, we only need to keep which one of these chosen edges has the minimum value.


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, Integer.MAX_VALUE));
      
        HashSet<Integer> visited = new HashSet<>();
      
        int minLoad = Integer.MAX_VALUE;
        while (queue.size() > 0) {
            Edge curr = queue.poll();
            int currNode = curr.node;
            int currWeightLimit = curr.weightLimit;
          
            if (visited.contains(currNode)) {
                continue;
            }
            visited.add(currNode);
          
            minLoad = Math.min(minLoad, currWeightLimit);
          
            if (currNode == end) {
                return minLoad;
            }
          
            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).weightLimit));
            }
        }
      
        return minLoad;
    }
  
    public void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
      
        int numCase = 0;
      
        int numCities = sc.nextInt();
        int numRoads = sc.nextInt();
        while (numCities != 0 || numRoads != 0) {
            adjList = new ArrayList<>();
            for (int i = 0; i < numCities; i++) {
                adjList.add(new ArrayList<Edge>());
            }
          
            HashMap<String, Integer> map = new HashMap<>();
          
            int index = 0;
            // read edges
            for (int i = 0; i < numRoads; i++) {
                String c1 = sc.next();
                String c2 = sc.next();
                int weightLimit = sc.nextInt();
              
                // map string nodes to integer nodes
                if (!map.containsKey(c1)) {
                    map.put(c1, index++);
                }
                if (!map.containsKey(c2)) {
                    map.put(c2, index++);
                }
              
                adjList.get(map.get(c1)).add(new Edge(map.get(c2), weightLimit));
                adjList.get(map.get(c2)).add(new Edge(map.get(c1), weightLimit));
            }

            String start = sc.next();
            String end = sc.next();
            int maxLoad = prim(map.get(start), map.get(end));
            bw.write("Scenario #" + ++numCase + "\n" + maxLoad + " tons\n\n");
          
            numCities = sc.nextInt();
            numRoads = 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 node;
    int weightLimit;
  
    public Edge(int n, int wL) {
        node = n;
        weightLimit = wL;
    }
  
    public int compareTo(Edge e) {
        return e.weightLimit-this.weightLimit;
    }
}