
import math
import sys





class      _lowerCAmelCase :




    def __init__( self					)    ->				int:
       lowerCAmelCase_      =     0
       lowerCAmelCase_      =     []
       lowerCAmelCase_      =     {}  # To store the pos of node in array




    def 					__a						( self					)    ->				Union[str, Any]:
       return self.cur_size == 0




    def 					__a						( self    ,    _UpperCamelCase					)    ->				List[Any]:
       lowerCAmelCase_      =     self.left(_UpperCAmelCase					)
       lowerCAmelCase_      =     self.right(_UpperCAmelCase					)
       if lc < self.cur_size and self.array(_UpperCAmelCase					)[0] < self.array(_UpperCAmelCase					)[0]:
          lowerCAmelCase_      =     lc
       else:
          lowerCAmelCase_      =     idx
       if rc < self.cur_size and self.array(_UpperCAmelCase					)[0] < self.array(_UpperCAmelCase					)[0]:
          lowerCAmelCase_      =     rc
       if smallest != idx:
          self.swap(_UpperCAmelCase    ,    _UpperCAmelCase					)
          self.min_heapify(_UpperCAmelCase					)




    def 					__a						( self    ,    _UpperCamelCase					)    ->				Dict:
       # Inserts a node into the Priority Queue
       lowerCAmelCase_      =     self.cur_size
       self.cur_size += 1
       self.array.append((sys.maxsize, tup[1])					)
       self.decrease_key((sys.maxsize, tup[1])    ,    tup[0]					)




    def 					__a						( self					)    ->				List[str]:
       # Removes and returns the min element at top of priority queue
       lowerCAmelCase_      =     self.array[0][1]
       lowerCAmelCase_      =     self.array[self.cur_size - 1]
       self.cur_size -= 1
       self.min_heapify(1					)
       del self.pos[min_node]
       return min_node




    def 					__a						( self    ,    _UpperCamelCase					)    ->				Any:
       # returns the index of left child
       return 2 * i + 1




    def 					__a						( self    ,    _UpperCamelCase					)    ->				str:
       # returns the index of right child
       return 2 * i + 2




    def 					__a						( self    ,    _UpperCamelCase					)    ->				Union[str, Any]:
       # returns the index of parent
       return math.floor(i / 2					)




    def 					__a						( self    ,    _UpperCamelCase    ,    _UpperCamelCase					)    ->				Optional[int]:
       # swaps array elements at indices i and j
       # update the pos{}
       lowerCAmelCase_      =     j
       lowerCAmelCase_      =     i
       lowerCAmelCase_      =     self.array[i]
       lowerCAmelCase_      =     self.array[j]
       lowerCAmelCase_      =     temp




    def 					__a						( self    ,    _UpperCamelCase    ,    _UpperCamelCase					)    ->				Dict:
       lowerCAmelCase_      =     self.pos[tup[1]]
       # assuming the new_d is atmost old_d
       lowerCAmelCase_      =     (new_d, tup[1])
       while idx > 0 and self.array[self.par(_UpperCAmelCase					)][0] > self.array[idx][0]:
          self.swap(_UpperCAmelCase    ,    self.par(_UpperCAmelCase					)					)
          lowerCAmelCase_      =     self.par(_UpperCAmelCase					)





class      _lowerCAmelCase :




    def __init__( self    ,    _UpperCamelCase					)    ->				Dict:
       lowerCAmelCase_      =     {}  # To store graph: u -> (v,w)
       lowerCAmelCase_      =     num  # Number of nodes in graph
       # To store the distance from source vertex
       lowerCAmelCase_      =     [0] * self.num_nodes
       lowerCAmelCase_      =     [-1] * self.num_nodes  # To store the path




    def 					__a						( self    ,    _UpperCamelCase    ,    _UpperCamelCase    ,    _UpperCamelCase					)    ->				str:
       #  Edge going from node u to v and v to u with weight w
       # u (w)-> v, v (w) -> u
       # Check if u already in graph
       if u in self.adjList:
          self.adjList[u].append((v, w)					)
       else:
          lowerCAmelCase_      =     [(v, w)]

       # Assuming undirected graph
       if v in self.adjList:
          self.adjList[v].append((u, w)					)
       else:
          lowerCAmelCase_      =     [(u, w)]




    def 					__a						( self					)    ->				List[str]:
       # u -> v(w)
       for u in self.adjList:
          print(_UpperCAmelCase    ,    "->"    ,    " -> ".join(str(f"""{v}({w})"""					) for v, w in self.adjList[u]					)					)




    def 					__a						( self    ,    _UpperCamelCase					)    ->				List[str]:
       # Flush old junk values in par[]
       lowerCAmelCase_      =     [-1] * self.num_nodes
       # src is the source node
       lowerCAmelCase_      =     0
       lowerCAmelCase_      =     PriorityQueue()
       q.insert((0, src)					)  # (dist from src, node)
       for u in self.adjList:
          if u != src:
             lowerCAmelCase_      =     sys.maxsize  # Infinity
             lowerCAmelCase_      =     -1

       while not q.is_empty():
          lowerCAmelCase_      =     q.extract_min()  # Returns node with the min dist from source
          # Update the distance of all the neighbours of u and
          # if their prev dist was INFINITY then push them in Q
          for v, w in self.adjList[u]:
             lowerCAmelCase_      =     self.dist[u] + w
             if self.dist[v] > new_dist:
                if self.dist[v] == sys.maxsize:
                   q.insert((new_dist, v)					)
                else:
                   q.decrease_key((self.dist[v], v)    ,    _UpperCAmelCase					)
                lowerCAmelCase_      =     new_dist
                lowerCAmelCase_      =     u

        # Show the shortest distances from src
       self.show_distances(_UpperCAmelCase					)




    def 					__a						( self    ,    _UpperCamelCase					)    ->				Optional[Any]:
       print(f"""Distance from node: {src}"""					)
       for u in range(self.num_nodes					):
          print(f"""Node {u} has distance: {self.dist[u]}"""					)




    def 					__a						( self    ,    _UpperCamelCase    ,    _UpperCamelCase					)    ->				Union[str, Any]:
       # To show the shortest path from src to dest
       # WARNING: Use it *after* calling dijkstra
       lowerCAmelCase_      =     []
       lowerCAmelCase_      =     0
       lowerCAmelCase_      =     dest
       # Backtracking from dest to src
       while self.par[temp] != -1:
          path.append(_UpperCAmelCase					)
          if temp != src:
             for v, w in self.adjList[temp]:
                if v == self.par[temp]:
                   cost += w
                   break
          lowerCAmelCase_      =     self.par[temp]
       path.append(_UpperCAmelCase					)
       path.reverse()

       print(f"""----Path to reach {dest} from {src}----"""					)
       for u in path:
          print(f"""{u}"""    ,    end=" "					)
          if u != dest:
             print("-> "    ,    end=""					)

       print("\nTotal cost of path: "    ,    _UpperCAmelCase					)


if __name__ == "__main__":
   _A       =					Graph(9)
   graph.add_edge(0, 1, 4)
   graph.add_edge(0, 7, 8)
   graph.add_edge(1, 2, 8)
   graph.add_edge(1, 7, 11)
   graph.add_edge(2, 3, 7)
   graph.add_edge(2, 8, 2)
   graph.add_edge(2, 5, 4)
   graph.add_edge(3, 4, 9)
   graph.add_edge(3, 5, 14)
   graph.add_edge(4, 5, 10)
   graph.add_edge(5, 6, 2)
   graph.add_edge(6, 7, 1)
   graph.add_edge(6, 8, 6)
   graph.add_edge(7, 8, 7)
   graph.show_graph()
   graph.dijkstra(0)
   graph.show_path(0, 4)

# OUTPUT
# 0 -> 1(4) -> 7(8)
# 1 -> 0(4) -> 2(8) -> 7(11)
# 7 -> 0(8) -> 1(11) -> 6(1) -> 8(7)
# 2 -> 1(8) -> 3(7) -> 8(2) -> 5(4)
# 3 -> 2(7) -> 4(9) -> 5(14)
# 8 -> 2(2) -> 6(6) -> 7(7)
# 5 -> 2(4) -> 3(14) -> 4(10) -> 6(2)
# 4 -> 3(9) -> 5(10)
# 6 -> 5(2) -> 7(1) -> 8(6)
# Distance from node: 0
# Node 0 has distance: 0
# Node 1 has distance: 4
# Node 2 has distance: 12
# Node 3 has distance: 19
# Node 4 has distance: 21
# Node 5 has distance: 11
# Node 6 has distance: 9
# Node 7 has distance: 8
# Node 8 has distance: 14
# ----Path to reach 4 from 0----
# 0 -> 7 -> 6 -> 5 -> 4
# Total cost of path:  21





# This Python program implements an optimal binary search tree (abbreviated BST)
# building dynamic programming algorithm that delivers O(n^2) performance.
#
# The goal of the optimal BST problem is to build a low-cost BST for a
# given set of nodes, each with its own key and frequency. The frequency
# of the node is defined as how many time the node is being searched.
# The search cost of binary search tree is given by this formula:
#
# cost(1, n) = sum{i = 1 to n}((depth(node_i) + 1) * node_i_freq)
#
# where n is number of nodes in the BST. The characteristic of low-cost
# BSTs is having a faster overall search time than other implementations.
# The reason for their fast search time is that the nodes with high
# frequencies will be placed near the root of the tree while the nodes
# with low frequencies will be placed near the leaves of the tree thus
# reducing search time in the most frequent instances.
import sys
from random import randint





class      _lowerCAmelCase :




				def __init__( self    ,    _UpperCamelCase    ,    _UpperCamelCase					)    ->				str:
							lowerCAmelCase_      =     key
							lowerCAmelCase_      =     freq




				def __str__( self					)    ->				Any:
							return f"""Node(key={self.key}, freq={self.freq})"""






def        lowerCamelCase__    (    __lowerCAmelCase  :  Optional[int]   ,							__lowerCAmelCase  :  Dict   ,							__lowerCAmelCase  :  Optional[Any]   ,							__lowerCAmelCase  :  Optional[int]   ,							__lowerCAmelCase  :  int   ,							__lowerCAmelCase  :  List[Any]    ):




			"""simple docstring"""


			if i > j or i < 0 or j > len(__lowerCAmelCase    ) - 1:
						return

			lowerCAmelCase_      =     root[i][j]
			if parent == -1:  # root does not have a parent
						print(F"""{key[node]} is the root of the binary search tree."""    )
			elif is_left:
						print(F"""{key[node]} is the left child of key {parent}."""    )
			else:
						print(F"""{key[node]} is the right child of key {parent}."""    )

			print_binary_search_tree(__lowerCAmelCase   ,							__lowerCAmelCase   ,							__lowerCAmelCase   ,							node - 1   ,							key[node]   ,							__lowerCAmelCase    )
			print_binary_search_tree(__lowerCAmelCase   ,							__lowerCAmelCase   ,							node + 1   ,							__lowerCAmelCase   ,							key[node]   ,							__lowerCAmelCase    )






def        lowerCamelCase__    (    __lowerCAmelCase  :  Union[str, Any]    ):




			"""simple docstring"""


			nodes.sort(key=lambda __lowerCAmelCase    : node.key    )

			lowerCAmelCase_      =     len(__lowerCAmelCase    )

			lowerCAmelCase_      =     [nodes[i].key for i in range(__lowerCAmelCase    )]
			lowerCAmelCase_      =     [nodes[i].freq for i in range(__lowerCAmelCase    )]

			# This 2D array stores the overall tree cost (which's as minimized as possible);
			# for a single key, cost is equal to frequency of the key.
			lowerCAmelCase_      =     [[freqs[i] if i == j else 0 for j in range(__lowerCAmelCase    )] for i in range(__lowerCAmelCase    )]
			# sum[i][j] stores the sum of key frequencies between i and j inclusive in nodes
			# array
			lowerCAmelCase_      =     [[freqs[i] if i == j else 0 for j in range(__lowerCAmelCase    )] for i in range(__lowerCAmelCase    )]
			# stores tree roots that will be used later for constructing binary search tree
			lowerCAmelCase_      =     [[i if i == j else 0 for j in range(__lowerCAmelCase    )] for i in range(__lowerCAmelCase    )]

			for interval_length in range(2   ,							n + 1    ):
						for i in range(n - interval_length + 1    ):
									lowerCAmelCase_      =     i + interval_length - 1

									lowerCAmelCase_      =     sys.maxsize  # set the value to "infinity"
									lowerCAmelCase_      =     total[i][j - 1] + freqs[j]

									# Apply Knuth's optimization
									# Loop without optimization: for r in range(i, j + 1):
									for r in range(root[i][j - 1]   ,							root[i + 1][j] + 1    ):  # r is a temporal root
												lowerCAmelCase_      =     dp[i][r - 1] if r != i else 0  # optimal cost for left subtree
												lowerCAmelCase_      =     dp[r + 1][j] if r != j else 0  # optimal cost for right subtree
												lowerCAmelCase_      =     left + total[i][j] + right

												if dp[i][j] > cost:
															lowerCAmelCase_      =     cost
															lowerCAmelCase_      =     r

			print("Binary search tree nodes:"    )
			for node in nodes:
						print(__lowerCAmelCase    )

			print(F"""\nThe cost of optimal BST for given tree nodes is {dp[0][n - 1]}."""    )
			print_binary_search_tree(__lowerCAmelCase   ,							__lowerCAmelCase   ,							0   ,							n - 1   ,							-1   ,							__lowerCAmelCase    )






def        lowerCamelCase__    (    ):




			"""simple docstring"""


			lowerCAmelCase_      =     [Node(__lowerCAmelCase   ,							randint(1   ,							50    )    ) for i in range(10   ,							0   ,							-1    )]
			find_optimal_binary_search_tree(__lowerCAmelCase    )


if __name__ == "__main__":
			main()



