2 / 2
Oct 2015

Hello. I am trying to solve the Mice and Maze4 problem but am getting a runtime error (nzec) in my program. Do any of you have any test cases that I can use to figure out what is wrong with my Java code? If not, I've included my code below. The code returns the correct answer when run on my computer but not on the testing server.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

class Main {
    
    public static void main(String[] args) 
    {
        int cellCount = Integer.parseInt(args[0]);
        int exitCellNumber = Integer.parseInt(args[1]);
        int maxTime = Integer.parseInt(args[2]);
        int numberOfEdges = Integer.parseInt(args[3]);
        
        // populate a list of cells
        List<Cell> cells = new ArrayList<Cell>();
        for (int i = 0; i <= cellCount; i ++) {
            cells.add(new Cell(i));
        }
        
        // populate the edges
        for (int i = 4; i < args.length;) {
            // figure out which Cell each Edge belongs to
            int cellIndex = Integer.parseInt(args[i++]);
            Cell cell = cells.get(cellIndex);
            Cell target = cells.get(Integer.parseInt(args[i++]));
            double weight = Integer.parseInt(args[i++]);
            cell.adjacencies.add(new Edge(target, weight));
        }        
        
        // find the exit cell
        Cell exitCell = null;
        for (Cell c: cells) {
            if (c.name == exitCellNumber) {
                exitCell = c;
                break;
            }
        }        
        
        // count how many cells are within maxTime of finishCell
        int finishingMice = 0;
        computePaths(exitCell);
        for (Cell c: cells) {
            if (c.minDistance <= maxTime) {
                finishingMice++;
            }
        }
        System.out.println(finishingMice);        
    }

    static void computePaths(Cell source) {
        source.minDistance = 0;

        // visit each cell u, always visiting cell with 
        // smallest minDistance first
        PriorityQueue<Cell> cellQueue = new PriorityQueue<Cell>();
        cellQueue.add(source);

        while(!cellQueue.isEmpty()) {
            Cell u = cellQueue.poll();

            // visit each edge exiting u
            for (Edge e: u.adjacencies) {
                Cell v = e.target;
                double weight = e.weight;
                // relax the edge (u,v)
                double distanceThroughU = u.minDistance + weight;
                if (distanceThroughU < v.minDistance) {
                    // remove v from queue
                    cellQueue.remove(v);
                    v.minDistance = distanceThroughU;
                    v.previous = u;
                    // re-add v to queue
                    cellQueue.add(v);
                }
            }
        }
    }

    static List<Cell> getShortestPathTo(Cell target) {
        List<Cell> path = new ArrayList<Cell>();
        for (Cell cell = target; cell != null; cell = cell.previous)
            path.add(cell);

        Collections.reverse(path);
        return path;
    }

}


class Cell implements Comparable<Cell>
{
    public final int name;
    public List<Edge> adjacencies = new ArrayList<Edge>(); //out cells
    public double minDistance = Double.POSITIVE_INFINITY;
    public Cell previous;
    public Cell(int argName) {name = argName;}
    //public String toString() {return name;}

    // Cell comparator
    public int compareTo(Cell other) {
        return Double.compare(minDistance, other.minDistance);
    }

}


class Edge 
{
    public final Cell target;
    public final double weight;
    public Edge(Cell argTarget, double argWeight)
    {target = argTarget; weight = argWeight;}
}
  • created

    Oct '15
  • last reply

    Oct '15
  • 1

    reply

  • 1.3k

    views

  • 2

    users

  • 3

    links

The input for the problem statement does not arrive in the args. The input is given through the stdin stream.


http://www.spoj.com/problems/TEST/24