Easy One Pass Dijkstra Solution ||  No DFS + DP required
Approach\nApproach:\nThe approach to solve this problem is based on a combination of Dijkstra\'s algorithm for shortest paths and dynamic programming.\n\nShorte
# Approach\nApproach:\nThe approach to solve this problem is based on a combination of Dijkstra\'s algorithm for shortest paths and dynamic programming.\n\nShortest Path Calculation (Dijkstra\'s Algorithm):\n\nWe start by calculating the shortest distance from every node to node n using Dijkstra\'s algorithm.\nWe use a priority queue (min-heap) to efficiently get the next node with the smallest distance.\n\nCounting Restricted Paths:\n\nUsing the distances calculated, we determine the number of restricted paths from node 1 to node n.\nWe use a priority queue to process nodes in the order of their distance from node n, ensuring that when we process a node, all nodes with shorter distances have already been processed.\nFor each node x, for each neighbor y, if the distance to n from y is greater than from x (dist[y] > dist[x]), it means we can move from x to y in a restricted path. We then update the number of restricted paths to y by adding the number of restricted paths to x.\n\n# Complexity\n- Time complexity:\nGraph Construction: O(E)\nDijkstra\'s Algorithm: O(V + E)logV\n\n\n- Space complexity:\nGraph Representation: O(E + V)\nDistance and Path Arrays: O(V)\nPriority Queue: O(V)\n\n# Code\n```\nclass Pair {\n    int node, weight;\n    \n    Pair(int node, int weight) {\n        this.node = node;\n        this.weight = weight;\n    }\n}\n\nclass Solution {\n    public int countRestrictedPaths(int n, int[][] edges) {\n        List<List<Pair>> adj = new ArrayList<>();\n        for (int i = 0; i <= n; i++) {\n            adj.add(new ArrayList<>());\n        }\n\n        for (int[] edge : edges) {\n            int u = edge[0], v = edge[1], w = edge[2];\n            adj.get(u).add(new Pair(v, w));\n            adj.get(v).add(new Pair(u, w));\n        }\n\n        int[] dist = new int[n + 1];\n        int[] ans = new int[n + 1];\n        Arrays.fill(dist, Integer.MAX_VALUE);\n        dist[n] = 0;\n        ans[n] = 1;\n        PriorityQueue<Pair> heap = new PriorityQueue<>((a, b) -> a.weight - b.weight);\n        heap.offer(new Pair(n, 0));\n        int mod = (int) 1e9 + 7;\n\n        while (!heap.isEmpty()) {\n            Pair top = heap.poll();\n            int d = top.weight, x = top.node;\n            if (d > dist[x]) continue;\n            if (x == 1) break;\n            for (Pair neighbor : adj.get(x)) {\n                int y = neighbor.node, w = neighbor.weight;\n                if (dist[y] > dist[x] + w) {\n                    dist[y] = dist[x] + w;\n                    heap.offer(new Pair(y, dist[y]));\n                }\n                if (dist[y] > dist[x]) {\n                    ans[y] = (ans[y] + ans[x]) % mod;\n                }\n            }\n        }\n        return ans[1];\n    }\n}\n```
['Dynamic Programming', 'Graph', 'Topological Sort', 'Heap (Priority Queue)', 'Shortest Path', 'Java']