[Java] Dijkstra + DFS Solution
\n// Dijkstra + DFS Solution\n// Dijkstra Algorithm to the shortest distances from n to other nodes.\n// Then DFS to explore the restricted pathes.\n// Time com
```\n// Dijkstra + DFS Solution\n// Dijkstra Algorithm to the shortest distances from n to other nodes.\n// Then DFS to explore the restricted pathes.\n// Time complexity: O(ElogN + N)\n// Space complexity: O(N + E)\nclass Solution {\n    private static final int MOD = (int) 1E9 + 7;\n    public int countRestrictedPaths(int n, int[][] edges) {\n        if (n <= 0) return 0;  // Or throw exception\n        List<Node>[] graph = buildGraph(n, edges);\n        int[] dists = new int[n + 1];\n        Arrays.fill(dists, Integer.MAX_VALUE);\n        dists[n] = 0;\n        PriorityQueue<Node> minHeap = new PriorityQueue<>((n1, n2) -> Integer.compare(n1.dist, n2.dist));\n        minHeap.add(new Node(n, 0));\n        while (!minHeap.isEmpty()) {\n            Node node = minHeap.poll();\n            for (Node neighbor : graph[node.id]) {\n                if (dists[neighbor.id] > dists[node.id] + neighbor.dist) {\n                    dists[neighbor.id] = dists[node.id] + neighbor.dist;\n                    minHeap.add(new Node(neighbor.id, dists[neighbor.id]));\n                }\n            }\n        }\n        int[] memo = new int[n + 1];\n        Arrays.fill(memo, -1);\n        memo[n] = 1;\n        return dfs(1, n, graph, dists, memo);\n    }\n    \n    private int dfs(int start, int target, List<Node>[] graph, int[] dists, int[] memo) {\n        if (start == target) return 1;\n        if (memo[start] >= 0) return memo[start];\n        int paths = 0;\n        for (Node neighbor : graph[start]) {\n            if (dists[start] > dists[neighbor.id]) {\n                paths = (paths + dfs(neighbor.id, target, graph, dists, memo)) % MOD;\n            }\n        }\n        memo[start] = paths;\n        return paths;\n    }\n    \n    private List<Node>[] buildGraph(int n, int[][] edges) {\n        List<Node>[] graph = new List[n + 1];\n        for (int i = 1; i <= n; i++) {\n            graph[i] = new ArrayList<>();\n        }\n        for (int[] edge : edges) {\n            int u = edge[0], v = edge[1], w = edge[2];\n            graph[u].add(new Node(v, w));\n            graph[v].add(new Node(u, w));\n        }\n        return graph;\n    }\n    \n    class Node {\n        int id, dist;\n        Node(int id, int dist) {\n            this.id = id;\n            this.dist = dist;\n        }\n    }\n}\n```
['Java']