[Python] Dijikstra(early stop) + graph DP, 1660ms
Dijikstra to find the shortest distance from end node(n) to all other nodes. Early stop when node 1 is met. Since the nodes left unvisited will have larger dist
Dijikstra to find the shortest distance from end node(n) to all other nodes. Early stop when node 1 is met. Since the nodes left unvisited will have larger distance to the end node. They won\'t be used to construct restricted paths.\n\nThen graph DP idea is that traversing from closer (to end node) nodes to further nodes. The number of paths for a node equals to sum of all its neighbors whose distance to end node are closer. \n\n```\nclass Solution:\n    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n        # construct the graph\n        neigh = collections.defaultdict(list)\n        for u,v,w in edges:\n            neigh[u].append((v,w))\n            neigh[v].append((u,w))\n            \n        # shortest path for all nodes to destination, using dijkstra:\n        dist = collections.defaultdict(lambda : float(inf))\n        heap = [(0,n)]\n        while len(dist.keys()) < n:\n            curDis, curNode = heapq.heappop(heap)\n            if curNode in dist:\n                continue\n                \n            for nei, w in neigh[curNode]:\n                if nei not in dist:\n                    heapq.heappush(heap, ((curDis+w), nei))\n            if curNode not in dist:\n                dist[curNode] = curDis\n            if curNode == 1:\n                break\n        \n        # search from the closer to further nodes\n        nodes = [(dist[i],i) for i in dist.keys()]\n        nodes.sort()\n        paths = collections.defaultdict(int)\n        paths[n] = 1\n        for _, node in nodes[1:]:\n            path = 0\n            for nei, _ in neigh[node]:\n                path += paths[nei] if dist[nei] < dist[node] else 0   # to avoid the equal distance nodes\n                path = int(path%(1e9+7))\n                \n            paths[node] = path\n            if node == 1:\n                return path\n        \n        return 0\n        \n```
[]