Python [Graph DP]
This question combines graph algorithms with dynamic programming. For shortest distances from each source to target use Dijkstra, which I wrote in a standalone 
This question combines graph algorithms with dynamic programming. For shortest distances from each source to target use Dijkstra, which I wrote in a standalone class.\n\nOnce you get the distances, consider a dynamic programming where `dp(u)` is the number of restricted paths from vertex `u` to target. We can write a top-down DP to get the total number of paths.\n\n```python\n#Generic Dijkstra\nclass GG:\n    def dijkstra(self, graph, source):\n        n = len(graph)\n        vis = [False]*n\n        weig = [math.inf]*n\n        weig[source] = 0\n        pq = []\n        heappush(pq, (0, source))\n        while pq:\n            d, u = heappop(pq)\n            vis[u] = True\n            for v, w in graph[u]:\n                if not vis[v]:\n                    nd = d + w\n                    if nd < weig[v]:\n                        weig[v] = nd\n                        heappush(pq, (nd, v))\n        return weig\n\n\nclass Solution:\n    def countRestrictedPaths(self, n, edges):\n        #build graph\n        graph = [[] for _ in range(n)]\n        for u, v, w in edges:\n            graph[u-1].append((v-1, w))\n            graph[v-1].append((u-1, w))\n        \n        #get the shortest distance from all sources to target\n        #this uses Dijkstra\n        gg = GG()\n        path_sums = gg.dijkstra(graph, n-1)\n        \n        #dp(u) is all restricted paths from vertex-u to target\n        @lru_cache(None)\n        def dp(u):\n            if u==n-1:\n                return 1\n            ans = 0\n            for v,_ in graph[u]:\n                if path_sums[v] < path_sums[u]:\n                    ans = ans + dp(v)\n                    ans = ans % (10**9 + 7)\n            return ans\n        \n        return dp(0)\n```
[]