Lc1786

class Solution:
    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:
        """
        1.  build graph + dijkstra get min distance from node x to node n with map  
        2.  start from nth node to ith node distance to make dis(i+1) < dis(i) ===> distance from current node to last node is strictly decreasing 
        dfs + memo 
        Dijkstra:  single source, non-negtive weight 
        Elg(E)
        what to memo?  
        pathNum(x1) = pathNum(x2) + pathNum(x3)+...
        pathNum(x2) = pathNum(x3) + ... 
        -  note here when we do dfs+memo, we don't do visited.  why???? each recursion. we favor lower dis 
                                        but for Dijkstra part we need visited 
        """
        M = 10**9+7
        # build g, adjecency list  
        g = collections.defaultdict(list)
        dmin = {}# min distance from node x to node n 
        for v1,v2,d in edges:
            g[v1].append([v2,d])
            g[v2].append([v1,d])
        # dijkstra 
        pq = []
        # 0. initialize seen set 
        seen = set()
        # 1. put source node with distance in front into pq 
        heappush(pq,[0,n])
        while pq:
            # 2. pop node with min distance  
            d,node = heappop(pq)
            # 3. check if current node has visited  <===  check seen,update seen (1)
            if node in seen:
                continue
            seen.add(node)
            #4. update min distance from source node to current node 
            dmin[node] = d
            # 5. get unvisited neibour node, push <acuumutive distance> with <neighbour node>  into hp.
            for nxt,dis in g[node]:
                if nxt in seen:               #<=====  check seen,no update seen(2)
                    continue
                heappush(pq,[d+dis,nxt])
        # dfs + memo : get total dis
        #!!! note here dfs + memo no need to check seen / handle cycle because restriction distanceToLastNode(zi) > distanceToLastNode(zi+1)
        memo = {}
        def dfs(cur):
            # 1.termination edge case 
            if cur == n:
                return 1
            # 2. check memo 
            if cur in memo:
                return memo[cur]
            #4. initialize path_cnt 
            cnt = 0
            # 3. check distance if restrctly increase 
            for nei,_ in g[cur]:
                if dmin[nei] >= dmin[cur]: #distanceToLastNode(zi) > distanceToLastNode(zi+1)
                    continue
                #5. get acuumulative path from current to nei node 
                cnt += dfs(nei)
                #6. mod cnt 
                cnt %= M
            #7. cache memo
            memo[cur] = cnt
            return cnt
        res = dfs(1)
        return res