[Java] Dijkshtra + memoization
\nclass Solution {\n    int dp[];\n    //We use memoization\n    public int countRestrictedPaths(int n, int[][] edges) {\n        int[] dist = new int[n+1];\n  
```\nclass Solution {\n    int dp[];\n    //We use memoization\n    public int countRestrictedPaths(int n, int[][] edges) {\n        int[] dist = new int[n+1];\n        dp = new int[n+1];\n        Arrays.fill(dp,-1);\n        Map<Integer, Map<Integer, Integer>> graph = new HashMap<>();\n        //Create the graph from input edges\n        for(int[] e : edges){\n            graph.putIfAbsent(e[0], new HashMap<>());\n            graph.putIfAbsent(e[1], new HashMap<>());\n            graph.get(e[0]).put(e[1],e[2]);\n            graph.get(e[1]).put(e[0],e[2]);\n        }\n        //Single source shortest distance - something like Dijkstra\'s\n        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->(a[1]-b[1]));\n        int[] base = new int[2];\n        base[0]=n;\n        pq.offer(base);\n        while(!pq.isEmpty()){\n            int[] currNode = pq.poll();\n            \n            for(Map.Entry<Integer, Integer> neighbour: graph.get(currNode[0]).entrySet()){\n                int node = neighbour.getKey();\n                int d = neighbour.getValue()+currNode[1];\n                if(node==n) continue;\n                //Select only those neighbours, whose new distance is less than existing distance\n                //New distance = distance of currNode from n + weight of edge between currNode and neighbour\n            \n                if( dist[node]==0 || d < dist[node]){\n                    int[] newNode = new int[2];\n                    newNode[0]=node;\n                    newNode[1]=d;\n                    pq.offer(newNode);\n                    dist[node]= d;\n                }\n            }\n        }\n\n        return find(1,graph,n,dist);\n    }\n    //This method traverses all the paths from source node to n though it\'s neigbours\n    private int find(int node, Map<Integer, Map<Integer, Integer>> graph, int n, int[] dist ){\n        if(node==n){\n            return 1;\n        }\n        \n        //Memoization avoid computaion of common subproblems. \n        if(dp[node]!=-1) return dp[node];\n\n        int ans = 0;\n        for(Map.Entry<Integer, Integer> neighbour: graph.get(node).entrySet()){\n                int currNode = neighbour.getKey();\n                int d = dist[currNode];\n                if( dist[node] > d){\n                    ans = (ans + find(currNode, graph, n, dist)) % 1000000007;\n            }\n        }\n        \n        return dp[node] = ans;\n    }\n}\n```
['Java']