Find the minimum spanning tree with alternating colored edges | Python implementation of the approach ; Initializing dp of size = ( 2 ^ 18 ) * 18 * 2. ; Recursive Function to calculate Minimum Cost with alternate colour edges ; Base case ; If already calculated ; Masking previous edges as explained in above formula . ; Function to Adjacency List Representation of a Graph ; Function to getCost for the Minimum Spanning Tree Formed ; Assigning maximum possible value . ; Driver Code
graph = [ [ [ 0 , 0 ] for i in range ( 18 ) ] for j in range ( 18 ) ] NEW_LINE dp = [ [ [ 0 , 0 ] for i in range ( 18 ) ] for j in range ( 1 << 15 ) ] NEW_LINE def minCost ( n : int , m : int , mask : int , prev : int , col : int ) -> int : NEW_LINE INDENT global dp NEW_LINE if mask == ( ( 1 << n ) - 1 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if dp [ mask ] [ prev ] [ col == 1 ] != 0 : NEW_LINE INDENT return dp [ mask ] [ prev ] [ col == 1 ] NEW_LINE DEDENT ans = int ( 1e9 ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT for j in range ( 2 ) : NEW_LINE INDENT if graph [ prev ] [ i ] [ j ] and not ( mask & ( 1 << i ) ) and ( j != col ) : NEW_LINE INDENT z = graph [ prev ] [ i ] [ j ] + minCost ( n , m , mask | ( 1 << i ) , i , j ) NEW_LINE ans = min ( z , ans ) NEW_LINE DEDENT DEDENT DEDENT dp [ mask ] [ prev ] [ col == 1 ] = ans NEW_LINE return dp [ mask ] [ prev ] [ col == 1 ] NEW_LINE DEDENT def makeGraph ( vp : list , m : int ) : NEW_LINE INDENT global graph NEW_LINE for i in range ( m ) : NEW_LINE INDENT a = vp [ i ] [ 0 ] [ 0 ] - 1 NEW_LINE b = vp [ i ] [ 0 ] [ 1 ] - 1 NEW_LINE cost = vp [ i ] [ 1 ] [ 0 ] NEW_LINE color = vp [ i ] [ 1 ] [ 1 ] NEW_LINE graph [ a ] [ b ] [ color == ' W ' ] = cost NEW_LINE graph [ b ] [ a ] [ color == ' W ' ] = cost NEW_LINE DEDENT DEDENT def getCost ( n : int , m : int ) -> int : NEW_LINE INDENT ans = int ( 1e9 ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT ans = min ( ans , minCost ( n , m , 1 << i , i , 2 ) ) NEW_LINE DEDENT if ans != int ( 1e9 ) : NEW_LINE INDENT return ans NEW_LINE DEDENT else : NEW_LINE INDENT return - 1 NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 3 NEW_LINE m = 4 NEW_LINE vp = [ [ [ 1 , 2 ] , [ 2 , ' B ' ] ] , [ [ 1 , 2 ] , [ 3 , ' W ' ] ] , [ [ 2 , 3 ] , [ 4 , ' W ' ] ] , [ [ 2 , 3 ] , [ 5 , ' B ' ] ] ] NEW_LINE makeGraph ( vp , m ) NEW_LINE print ( getCost ( n , m ) ) NEW_LINE DEDENT