Dijkstra Pattern
Important problem\nCheapest flight,minimum effort and more\n# Code\njava []\nclass Solution {\n    public int countPaths(int numIntersections, int[][] roads) {\
Important problem\nCheapest flight,minimum effort and more\n# Code\n```java []\nclass Solution {\n    public int countPaths(int numIntersections, int[][] roads) {\n        ArrayList<ArrayList<Node>> adjacencyList = new ArrayList<>();\n        for (int i = 0; i < numIntersections; i++) {\n            adjacencyList.add(new ArrayList<>());\n        }\n        for (int[] road : roads) {\n            int intersection1 = road[0], intersection2 = road[1], travelTime = road[2];\n            adjacencyList.get(intersection1).add(new Node(travelTime, intersection2));\n            adjacencyList.get(intersection2).add(new Node(travelTime, intersection1));\n        }\n        PriorityQueue<Node> minHeap = new PriorityQueue<>((x, y) -> Long.compare(x.distanceFromSource, y.distanceFromSource));\n        long[] distanceFromSource = new long[numIntersections];\n        int[] numWaysToReach = new int[numIntersections];\n        for (int i = 0; i < numIntersections; i++) {\n            distanceFromSource[i] = Long.MAX_VALUE;\n            numWaysToReach[i] = 0;\n        }\n        distanceFromSource[0] = 0;\n        numWaysToReach[0] = 1;\n        minHeap.add(new Node(0, 0));\n        int modulo = (int) (1e9 + 7);\n        while (!minHeap.isEmpty()) {\n            long currentDistance = minHeap.peek().distanceFromSource;\n            int currentIntersection = minHeap.peek().intersection;\n            minHeap.remove();\n            for (Node neighbor : adjacencyList.get(currentIntersection)) {\n                long neighborIntersection = neighbor.intersection;\n                long travelTimeToNeighbor = neighbor.distanceFromSource;\n                if (currentDistance + travelTimeToNeighbor < distanceFromSource[(int) neighborIntersection]) {\n                    distanceFromSource[(int) neighborIntersection] = currentDistance + travelTimeToNeighbor;\n                    minHeap.add(new Node(currentDistance + travelTimeToNeighbor, (int) neighborIntersection));\n                    numWaysToReach[(int) neighborIntersection] = numWaysToReach[currentIntersection];\n                } else if (currentDistance + travelTimeToNeighbor == distanceFromSource[(int) neighborIntersection]) {\n                    numWaysToReach[(int) neighborIntersection] = (numWaysToReach[(int) neighborIntersection] + \n                                                                 numWaysToReach[currentIntersection]) % modulo;\n                }\n            }\n        }\n        return numWaysToReach[numIntersections - 1] % modulo;\n    }\n    class Node {\n        long distanceFromSource;\n        int intersection;\n        Node(long distanceFromSource, int intersection) {\n            this.distanceFromSource = distanceFromSource;\n            this.intersection = intersection;\n        }\n    }\n}\n```
['Java']