(UVA) Shipping Routes - Solução 2

In this solution, the Breadth-First Search method was improved from the previous solution (here). Moreover, instead of using two queues (queue and distance), it was created one queue which holds 'Element' objects, which has both values.

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

class Main  {
    public static HashMap<String, ArrayList<String>> adjList = new HashMap<String, ArrayList<String>>();
   
    public static int bfs(String start, String goal) {
        Queue<Element> queue = new ArrayDeque<Element>();
        Element e = new Element(start, 0);
        queue.add(e);
       
        HashSet<String> addedToQueue = new HashSet<String>();
        addedToQueue.add(start);
       
        while (queue.size() > 0) {
            String current = queue.element().vertex;

            if (current.equals(goal)) {
                return queue.element().distance;
            }
           
            ArrayList<String> neighbors = adjList.get(current);
            for (int i = 0; i < neighbors.size(); i++) {
                if (!addedToQueue.contains(neighbors.get(i))) {
                    addedToQueue.add(neighbors.get(i));
                    e = new Element(neighbors.get(i), queue.element().distance+1);
                    queue.add(e);
                }
            }
           
            queue.remove();
        }   
       
        return -1;
    }
   
    public static void readRequests(Scanner sc, int numRequests, int numLegsBtwWarehouses) {
        for (int j = 0; j < numRequests; j++) {
            int sizeOfShipment = sc.nextInt();
            String source = sc.next();
            String destination = sc.next();
           
            int steps = -1;
            if (numLegsBtwWarehouses > 0) {
                steps = bfs(source, destination);               
            }
                   
            if (steps == -1) {
                System.out.println("NO SHIPMENT POSSIBLE");
            }
            else {
                System.out.println("$" + sizeOfShipment*steps*100);
            }
        }
    }

    public static void readEdges(Scanner sc, int numLegsBtwWarehouses) {
        for (int j = 0; j < numLegsBtwWarehouses; j++) {
            String w1 = sc.next();
            String w2 = sc.next();
           
            adjList.get(w1).add(w2);
            adjList.get(w2).add(w1);     
        }
    }
   
    public static void  readWarehouses(Scanner sc, String[] warehouses, int numWarehouses) {
        for (int j = 0; j < numWarehouses; j++) {
            warehouses[j] = sc.next();
            ArrayList<String> list = new ArrayList<String>();
            adjList.put(warehouses[j], list);
        }
    }
   
    public static void process() throws NumberFormatException, IOException {   
        Scanner sc = new Scanner(System.in);
       
        int numDataSets = sc.nextInt();
       
        System.out.println("SHIPPING ROUTES OUTPUT");
        for (int i = 0; i < numDataSets; i++) {
            int numWarehouses = sc.nextInt();
            int numLegsBtwWarehouses = sc.nextInt();
            int numRequests = sc.nextInt();
           
            // read warehouses
            String[] warehouses = new String[numWarehouses];
            readWarehouses(sc, warehouses, numWarehouses);
           
            // read the edges between the warehouses
            readEdges(sc, numLegsBtwWarehouses);
              
            // read the requests
            System.out.println("\nDATA SET  " + (i+1) + "\n");           
            readRequests(sc, numRequests, numLegsBtwWarehouses);
           
            adjList.clear();
        }
        System.out.println("\nEND OF OUTPUT");
                                       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}

class Element {
    String vertex;
    int distance;
   
    public Element (String vertex, int distance) {
        this.vertex = vertex;
        this.distance = distance;
    }
}