(UVA) Galactic Import - Solution

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

The solution below used Breadth-First Search (BFS) to solve this problem.


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

class Main {
    public HashMap<Character, ArrayList<Info>> adjList;
   
    public char bfs(char start, int numPlanets) {
        Queue<Info> queue = new ArrayDeque<>();
        queue.add(new Info(start, 0, 0));
       
        HashSet<Character> visited = new HashSet<>();
       
        double bestValue = 0;
        char bestPlanet = 'Z';
        while (queue.size() > 0) {
            Info curr = queue.poll();
            char currPlanet = curr.planet;
            double currValue = curr.value;
            int currDist = curr.distance;
           
            if (visited.contains(currPlanet) || currValue < 0) {
                continue;
            }
            visited.add(currPlanet);
           
            if (currValue == bestValue && currPlanet != '*') {
                bestPlanet = (currPlanet < bestPlanet) ? currPlanet : bestPlanet;
            } else if (currValue > bestValue) {
                bestValue = currValue;
                bestPlanet = currPlanet;
            }
           
            if (visited.size() == numPlanets) {
                return bestPlanet;
            }
           
            ArrayList<Info> reachable = adjList.get(currPlanet);
            for (int i = 0; i < reachable.size(); i++) {
                queue.add(new Info(reachable.get(i).planet, reachable.get(i).value-((reachable.get(i).value-(0.95*reachable.get(i).value))*currDist), currDist+1));
            }
        }
       
        return bestPlanet;
    }
   
    public void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        while (sc.hasNext()) {
            int numPlanets = sc.nextInt();
            adjList = new HashMap<>();
            for (int i = 0; i < 26; i++) {
                adjList.put((char)(i+'A'), new ArrayList<Info>());
            }
            adjList.put('*', new ArrayList<Info>());
            for (int i = 0; i < numPlanets; i++) {
                // read info
                char planet = sc.next().charAt(0);
                double valueExport = sc.nextDouble();
                String reachables = sc.next();         
                // fill the adjacency list
                for (int j = 0; j < reachables.length(); j++) {
                    adjList.get(planet).add(new Info(reachables.charAt(j), -1, 0));
                    adjList.get(reachables.charAt(j)).add(new Info(planet, valueExport, 0));
                }
            }       

            bw.write("Import from "+bfs('*', numPlanets+1)+"\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 Info {
    char planet;
    double value;
    int distance;
   
    public Info(char p, double v, int d) {
        planet = p;
        value = v;
        distance = d;
    }
}

Comments

Popular posts from this blog

(Coderbyte) Powers of Two - Solução

(Coderbyte) Dash Insert II - Solução

(CoderByte) Number Search - Solução