LC 882. Reachable Nodes In Subdivided Graph.py

class Solution:
    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:
        '''
        status: 7/47
        Step 1: Create graph 
        Step 2: HP[node] = remain power
        Step 3: sum of main-nodes + sub-nodes
        '''
        
        # Step 1 
        g = [[0]*(n+1) for i in range(n+1)]
        
        for edge in edges:
            #print(edge[2])
            g[edge[0]][edge[1]] = edge[2]
            g[edge[1]][edge[0]] = edge[2]

        csum = 0    
        for i in g[0]:
            #print(i)
            csum+=i
        if csum==0: 
            return 1

        '''
        print(g)
        
        for row in g:
            print(row)
        '''  
        
        # Step 2 => using queue 
        q = [[0,maxMoves]]
        visited = {0:maxMoves}
        #remain_hp = [[0,maxMoves]] 
        while q:
            # find adjacent node
            node,hp = q.pop()
            #print(node)
            #input("pause")
            #print(g[node][2])
            #print(len(g[node]))
            for i in range(n):
                # i is adj.node index
                # g[node][i] is cost
                #print(g[node][i])
                #input("PAUSE")
                if hp-((g[node][i])+1) >= 0:
                    #if k not in visited:
                    if i not in visited.keys():

                        q.append([i,hp-(g[node][i])-1])
                        #visited.add(i,hp-(g[node][i])-1)
                        visited[i] = hp-(g[node][i])-1
                    #print(visited.)
                    #input("checkpoint")
                    #remain_hp.append([i,hp-(g[node][i])])
                    
        # Step 3 => len(visited) + small nodes(between Node)           
        
        # visited[a].get(node,default value)+visited[b].get(node,default value) = A
        # avoid repetition => max is TOTAL small nodes between a and b => graph = B
        # min(A,B)
        # P.S. Python dict => get(target,default_value) => default_value == (max=10001)
        max_Subdivided = 10001
        Subdivided_nodes = 0
        #print(len(visited))
        #print(visited)
        for a,b,c in edges:
                    Subdivided_nodes+=min(visited.get(a,0)+visited.get(b,0),c)
        #print(Subdivided_nodes)            
        return len(visited)+Subdivided_nodes