Untitled

class Solution {

    Map<String, List<Pair<String, Double>>> graph = new HashMap<String, List<Pair<String, Double>>> ();

    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {

        int size = equations.size();

        for (int i = 0; i < size; i++) {
            List<String> equation = equations.get(i);
            String src = equation.get(0);
            String destination = equation.get(1);
            double cost = values[i];

            if (graph.containsKey(src)) {
                graph.get(src).add(new Pair(destination, cost));
            } else {
                List<Pair<String, Double>> list = new ArrayList<Pair<String, Double>>();
                list.add(new Pair(destination, cost));
                graph.put(src, list);
            }

            double reverseCost = 1.0/cost;

            if (graph.containsKey(destination)) {
                graph.get(destination).add(new Pair(src, reverseCost));
            } else {
                List<Pair<String, Double>> list = new ArrayList<Pair<String, Double>>();
                list.add(new Pair(src, reverseCost));
                graph.put(destination, list);
            }
        }

        double[] res = new double[queries.size()];
        int idx = 0;

        for (List<String> query : queries) {
            String src = query.get(0);
            String destination = query.get(1);

            Map<String, Boolean> visited = new HashMap<String, Boolean>();
            double result = bfs(src, destination, graph, visited);
            res[idx++] = result;
        }

        return res;
    }

    private double bfs(String src, String destination, Map<String, List<Pair<String, Double>>> graph, Map<String, Boolean> visited) {

        if (graph.containsKey(src) && src.equals(destination)) {
            return (double) 1.0;
        }

        Queue<Pair<String, Double>> queue = new LinkedList<Pair<String, Double>>();
        Pair<String, Double> pair = new Pair(src, (double) 1.0);
        queue.add(pair);

        while(!queue.isEmpty()) {
            Pair<String, Double> top = queue.poll();
            List<Pair<String, Double>> neighbors = graph.get(top.getKey());
            double cost = top.getValue();
            visited.put(top.getKey(), true);
    
            if (neighbors == null) {
                continue;
            }

            for (Pair<String, Double> neighbor: neighbors) {
                String newSrc = neighbor.getKey();
                double newCost = neighbor.getValue();

                if (visited.get(newSrc) == null) {
                    queue.add(new Pair(newSrc, cost * newCost));
                    if (newSrc.equals(destination)) {
                        return cost * newCost;
                    }
                }
            }
        }

        return -1;
    }
}