Dijkstra: Shortest Reach 2

  • + 3 comments

    If you couldn't pass Test Case 7 (like most people did), it's probably not your fault for poorly implementing Dijkstra's algorithm.

    As people have said, Test Case 7 includes a lot of duplicate edges, which is a recipe for disaster if your Dijkstra implementation does not account for edge duplications (which understandably most people didn't expect to have to do).
    This, along with the rather slow I/O and loop processing of certain languages, makes Test Case 7 near impossible to pass if you go with Dijkstra. Some have had success with Bellman-Ford instead, but that's not what this problem meant for you to do (it literally has "Dijkstra" in its title).

    An alternative workaround (and one that I deem legit and not cheating, seeing how absurd Test Case 7 is) is to optimize the reading of the stdin input in the program's entry point (aka. the 'main' function).
    Most importantly, store the edges in a Set when reading stdin instead of the default data structure (in Java's case a List), and then recast it back when appropiate.
    After that, you can look for more language-specific optimizations to the stdin reading if you want. In my case (Java 8) I removed the String.replaceAll("\\s+$", "") that removes trailing spaces which recompiles the RegEx into a Pattern each time it is called which is unnecessarily horribly costly since tests on HackerRank don't have trailing spaces anyways.

    Here's the resulting part of modified main code for Java 8

    Set<List<Integer>> edges = new HashSet<>();
    
    IntStream.range(0, m).forEach(i -> {
        try {
            edges.add(
                Stream.of(bufferedReader.readLine().split(" "))
                .map(Integer::parseInt)
                .collect(toList())
            );
        } catch (IOException ex) {
            throw new RuntimeException(ex);
        }
    });
    
    int s = Integer.parseInt(bufferedReader.readLine().trim());
    
    List<List<Integer>> edgeList = new ArrayList<>();
    edgeList.addAll(edges);
    List<Integer> result = Result.shortestReach(n, edgeList, s);