




'''simple docstring'''






import math
import sys



class  A		:




				'''simple docstring'''





				def __init__(self      )     ->	int:
							__UpperCamelCase				:      Optional[Any]									=       0
							__UpperCamelCase				:      Optional[Any]									=       []
							__UpperCamelCase				:      Dict									=       {}  # 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]:
							__UpperCamelCase				:      Any									=       self.left(_UpperCAmelCase      )
							__UpperCamelCase				:      int									=       self.right(_UpperCAmelCase      )
							if lc < self.cur_size and self.array(_UpperCAmelCase      )[0] < self.array(_UpperCAmelCase      )[0]:
										__UpperCamelCase				:      List[str]									=       lc
							else:
										__UpperCamelCase				:      Optional[int]									=       idx
							if rc < self.cur_size and self.array(_UpperCAmelCase      )[0] < self.array(_UpperCAmelCase      )[0]:
										__UpperCamelCase				:      List[Any]									=       rc
							if smallest != idx:
										self.swap(_UpperCAmelCase			,  _UpperCAmelCase      )
										self.min_heapify(_UpperCAmelCase      )
				def 	a_	(self			,  _UpperCAmelCase      )     ->	Dict:
							# Inserts a node into the Priority Queue
							__UpperCamelCase				:      Optional[Any]									=       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
							__UpperCamelCase				:      Optional[Any]									=       self.array[0][1]
							__UpperCamelCase				:      List[str]									=       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{}
							__UpperCamelCase				:      List[Any]									=       j
							__UpperCamelCase				:      List[Any]									=       i
							__UpperCamelCase				:      int									=       self.array[i]
							__UpperCamelCase				:      Union[str, Any]									=       self.array[j]
							__UpperCamelCase				:      Tuple									=       temp





				def 	a_	(self			,  _UpperCAmelCase			,  _UpperCAmelCase      )     ->	Dict:
							__UpperCamelCase				:      str									=       self.pos[tup[1]]
							# assuming the new_d is atmost old_d
							__UpperCamelCase				:      Any									=       (new_d, tup[1])
							while idx > 0 and self.array[self.par(_UpperCAmelCase      )][0] > self.array[idx][0]:
										self.swap(_UpperCAmelCase			,  self.par(_UpperCAmelCase      )      )
										__UpperCamelCase				:      List[Any]									=       self.par(_UpperCAmelCase      )







class  A		:




				'''simple docstring'''





				def __init__(self			,  _UpperCAmelCase      )     ->	Dict:
							__UpperCamelCase				:      Union[str, Any]									=       {}  # To store graph: u -> (v,w)
							__UpperCamelCase				:      Tuple									=       num  # Number of nodes in graph
							# To store the distance from source vertex
							__UpperCamelCase				:      int									=       [0] * self.num_nodes
							__UpperCamelCase				:      Optional[int]									=       [-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:
										__UpperCamelCase				:      List[str]									=       [(v, w)]

							# Assuming undirected graph
							if v in self.adjList:
										self.adjList[v].append((u, w)      )
							else:
										__UpperCamelCase				:      Union[str, Any]									=       [(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[]
							__UpperCamelCase				:      Dict									=       [-1] * self.num_nodes
							# src is the source node
							__UpperCamelCase				:      Optional[int]									=       0
							__UpperCamelCase				:      List[str]									=       PriorityQueue()
							q.insert((0, src)      )  # (dist from src, node)
							for u in self.adjList:
										if u != src:
													__UpperCamelCase				:      Optional[Any]									=       sys.maxsize  # Infinity
													__UpperCamelCase				:      List[str]									=       -1

							while not q.is_empty():
										__UpperCamelCase				:      Optional[Any]									=       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]:
													__UpperCamelCase				:      Any									=       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      )
																__UpperCamelCase				:      Any									=       new_dist
																__UpperCamelCase				:      Tuple									=       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
							__UpperCamelCase				:      Dict									=       []
							__UpperCamelCase				:      Optional[int]									=       0
							__UpperCamelCase				:      List[Any]									=       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
										__UpperCamelCase				:      str									=       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__":
				_lowerCAmelCase				     = 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









'''simple docstring'''






from __future__ import annotations

import random
from collections.abc import Iterable
from typing import Any, Generic, TypeVar

_lowerCAmelCase				     = TypeVar('''T''', bound=bool)



class  A		(			Generic[T]		):




				'''simple docstring'''





				def __init__(self			,  _UpperCAmelCase      )     ->	None:
							__UpperCamelCase				:      T									=       value
							__UpperCamelCase				:      RandomizedHeapNode[T] | None									=       None
							__UpperCamelCase				:      RandomizedHeapNode[T] | None									=       None
				@property
				def 	a_	(self      )     ->	T:
							return self._value





				@staticmethod
				def 	a_	(_UpperCAmelCase			,  _UpperCAmelCase      )     ->	RandomizedHeapNode[T] | None:
							if not roota:
										return roota

							if not roota:
										return roota

							if roota.value > roota.value:
										__UpperCamelCase		, __UpperCamelCase				:      int									=       roota, roota

							if random.choice([True, False]      ):
										__UpperCamelCase		, __UpperCamelCase				:      Dict									=       roota.right, roota.left

							__UpperCamelCase				:      Any									=       RandomizedHeapNode.merge(roota.left			,  _UpperCAmelCase      )

							return roota







class  A		(			Generic[T]		):




				'''simple docstring'''





				def __init__(self			,  _UpperCAmelCase = ()      )     ->	None:
							__UpperCamelCase				:      RandomizedHeapNode[T] | None									=       None

							if data:
										for item in data:
													self.insert(_UpperCAmelCase      )
				def 	a_	(self			,  _UpperCAmelCase      )     ->	None:
							__UpperCamelCase				:      str									=       RandomizedHeapNode.merge(self._root			,  RandomizedHeapNode(_UpperCAmelCase      )      )
				def 	a_	(self      )     ->	T | None:
							__UpperCamelCase				:      Dict									=       self.top()

							if self._root is None:
										return None

							__UpperCamelCase				:      List[str]									=       RandomizedHeapNode.merge(self._root.left			,  self._root.right      )

							return result
				def 	a_	(self      )     ->	T:
							if not self._root:
										raise IndexError("Can't get top element for the empty heap."      )
							return self._root.value
				def 	a_	(self      )     ->	None:
							__UpperCamelCase				:      int									=       None
				def 	a_	(self      )     ->	list[Any]:
							__UpperCamelCase				:      int									=       []
							while self:
										result.append(self.pop()      )

							return result





				def __bool__(self      )     ->	bool:
							return self._root is not None


if __name__ == "__main__":
				import doctest

				doctest.testmod()



