Java faster than 100% (10ms) through Dijkstra with array for queue
Since Java\'s PriorityQueue doesn\'t handle "decreaseKey" operation, if you use it you will have several times the same node in the queue. The algo still works 
Since Java\'s PriorityQueue doesn\'t handle "decreaseKey" operation, if you use it you will have several times the same node in the queue. The algo still works but it\'s slower because of the duplicated elements in the queue. You can still implement your own queue manually though.\n\nYou can also use an array to represent the queue and look for the minimum each time. You will have to be sure to skip the visited nodes though.\n\n```\nclass Solution {\n    public static final long MODULO = 1_000_000_007;\n\n    public int countPaths(int n, int[][] roads) {\n        long[] distances = new long[n];\n        Arrays.fill(distances, Long.MAX_VALUE);\n        distances[0] = 0;\n        Set<Integer> visited = new HashSet<Integer>();\n        long[] counts = new long[n];\n        counts[0] = 1;\n        List<Integer>[] neighbors = new List[n];\n        for(int i =0; i< n; i++){\n            neighbors[i] = new ArrayList<>();\n        }\n\n        long[][] weights = new long[n][n];\n        for (int[] road : roads) {\n            int u = road[0];\n            int v = road[1];\n            weights[u][v] = road[2];\n            weights[v][u] = road[2];\n            neighbors[u].add(v);\n            neighbors[v].add(u);\n        }\n\n\n        while(visited.size() < n){\n            int u = findMin(distances, visited);\n            if(u == n-1) return (int) counts[n-1]; // destination has the smallest distance, there is no way to find a shorter path\n            long du = distances[u];\n            for(int v : neighbors[u]){\n                if(add(du, weights[u][v]) < distances[v]){\n                    distances[v] = du +  weights[u][v];\n                    counts[v] = counts[u];\n                } else if(add(du, weights[u][v]) == distances[v]){\n                    counts[v] = (counts[v] +counts[u]) % MODULO;\n                }\n            }\n\n            visited.add(u);\n        }\n\n        throw new IllegalStateException(); // no path from source to destination, shouldn\'t happen due to the problem constraints\n    }\n\n    private int findMin(long[] array, Set<Integer> visited){\n        long min = Long.MAX_VALUE;\n        int index = -1;\n        for(int i =0; i< array.length; i++){\n            if(!visited.contains(i) && array[i] < min){\n                min = array[i];\n                index = i;\n            }\n        }\n        return index;\n    }\n\n    // take care of overflows\n    private static long add(long a, long b){\n        return a ==  Long.MAX_VALUE || b == Long.MAX_VALUE ? Long.MAX_VALUE : a + b;\n    }\n}\n```
[]