Dijkstra+DFS+Memoization beats 100% python3
Explanation of the Soultion: \nWe need to find the number of paths between 1st to nth node in which the shortest path from the end node to each of the nodes of 
Explanation of the Soultion: \nWe need to find the number of paths between 1st to nth node in which the **shortest path from the end node** to each of the nodes of the path is in **strictly decreasing order**, for an example\nlets say there exist a path where n=5: 1->3->5, now lets say shortest path from 1 to 5 is 3 and shortest path from 3 to 5 is 2 then this is a valid restricted path because 3>2.\n\nNow, let us divide the problem in two parts:\n1. find the shortest path of each node from the end node (using dijkstra)\n2. do a depth first search from node n, now as this is an exhaustive search or simply figuring out all the paths from n to 1 which are restricted, there is a possibility that we may visit a node which was already visited previously hence we will end up calculating the path again. Now to tackle this, we can further optimise it using memoization.\nBelow is the code:\n```\nclass Solution:\n    def dijkstra(self,start,graph,distanceArr):\n        distanceArr[start]=0\n        queue=[(0,start)]\n        heapq.heapify(queue)\n        while queue:\n            wt,u=heapq.heappop(queue)\n            if wt>distanceArr[u]:continue #to only check min distance node in priority queue\n            for v,w in graph[u]:\n                if distanceArr[v]<=distanceArr[u]+w:continue\n                distanceArr[v]=distanceArr[u]+w\n                heapq.heappush(queue,(distanceArr[v],v))\n        return 0\n    \n    def dfs(self,u,graph,distanceArr,dp):\n        if u==1:return 1\n        if dp[u]!=-1:return dp[u]\n        ans=0\n        for v,w in graph[u]:\n            if distanceArr[v]>distanceArr[u]:\n                ans=(ans+self.dfs(v,graph,distanceArr,dp))%self.mod\n        dp[u]=ans\n        return ans\n    \n        \n    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n        graph=defaultdict(lambda:[])\n        dp=[-1]*(n+1)\n        self.mod=1000_000_007\n        for u,v,w in edges:\n            graph[u].append((v,w))\n            graph[v].append((u,w))\n        distanceArr=[float(\'inf\')]*(n+1)\n        self.dijkstra(n,graph,distanceArr)\n        return self.dfs(n,graph,distanceArr,dp)\n\n```\n\nComplexity:\n    Time: O(M * logN), where M is number of edges, N is number of nodes.\n    Space: O(M + N)\n
['Depth-First Search', 'Memoization']