




"""simple docstring"""







from __future__ import annotations

from collections.abc import Callable
from typing import Generic, TypeVar

a      =							TypeVar('T')
a      =							TypeVar('U')






class       SCREAMING_SNAKE_CASE__					(					Generic[T, U]					):


      def __init__(							self				:			List[Any]						,						lowerCAmelCase				:			T | None						,						lowerCAmelCase				:			U | None					):
          lowerCAmelCase  =				key
          lowerCAmelCase  =				val
          lowerCAmelCase  =				None
          lowerCAmelCase  =				None




      def __repr__(							self				:			List[Any]					):
          return (
              f'''Node: key: {self.key}, val: {self.val}, '''
              f'''has next: {bool(self.next					)}, has prev: {bool(self.prev					)}'''
          )






class       SCREAMING_SNAKE_CASE__					(					Generic[T, U]					):


      def __init__(							self				:			Optional[Any]					):
          lowerCAmelCase  =				DoubleLinkedListNode(lowerCAmelCase						,						lowerCAmelCase					)
          lowerCAmelCase  =				DoubleLinkedListNode(lowerCAmelCase						,						lowerCAmelCase					)
          lowerCAmelCase ,						lowerCAmelCase  =				self.rear, self.head


      def __repr__(							self				:			List[Any]					):
          lowerCAmelCase  =				["""DoubleLinkedList"""]
          lowerCAmelCase  =				self.head
          while node.next is not None:
              rep.append(str(lowerCAmelCase					)					)
              lowerCAmelCase  =				node.next
          rep.append(str(self.rear					)					)
          return ",\n    ".join(lowerCAmelCase					)


      def   __lowercase (							self				:			Optional[Any]						,						lowerCAmelCase				:			DoubleLinkedListNode[T, U]					):
          lowerCAmelCase  =				self.rear.prev

          # All nodes other than self.head are guaranteed to have non-None previous
          assert previous is not None

          lowerCAmelCase  =				node
          lowerCAmelCase  =				previous
          lowerCAmelCase  =				node
          lowerCAmelCase  =				self.rear




      def   __lowercase (							self				:			List[str]						,						lowerCAmelCase				:			DoubleLinkedListNode[T, U]					):

          if node.prev is None or node.next is None:
              return None

          lowerCAmelCase  =				node.next
          lowerCAmelCase  =				node.prev
          lowerCAmelCase  =				None
          lowerCAmelCase  =				None
          return node






class       SCREAMING_SNAKE_CASE__					(					Generic[T, U]					):
      _a    						=						{}


      def __init__(							self				:			Dict						,						lowerCAmelCase				:			int					):
          lowerCAmelCase  =				DoubleLinkedList()
          lowerCAmelCase  =				capacity
          lowerCAmelCase  =				0
          lowerCAmelCase  =				0
          lowerCAmelCase  =				0
          lowerCAmelCase  =				{}


      def __repr__(							self				:			Dict					):
          return (
              f'''CacheInfo(hits={self.hits}, misses={self.miss}, '''
              f'''capacity={self.capacity}, current size={self.num_keys})'''
          )


      def __contains__(							self				:			Tuple						,						lowerCAmelCase				:			T					):
          return key in self.cache


      def   __lowercase (							self				:			Optional[int]						,						lowerCAmelCase				:			T					):
          # Note: pythonic interface would throw KeyError rather than return None

          if key in self.cache:
              self.hits += 1
              lowerCAmelCase  =				self.cache[key]
              lowerCAmelCase  =				self.list.remove(self.cache[key]					)
              assert node == value_node

              # node is guaranteed not None because it is in self.cache
              assert node is not None
              self.list.add(lowerCAmelCase					)
              return node.val
          self.miss += 1
          return None


      def   __lowercase (							self				:			Dict						,						lowerCAmelCase				:			T						,						lowerCAmelCase				:			U					):

          if key not in self.cache:
              if self.num_keys >= self.capacity:
                  # delete first node (oldest) when over capacity
                  lowerCAmelCase  =				self.list.head.next

                  # guaranteed to have a non-None first node when num_keys > 0
                  # explain to type checker via assertions
                  assert first_node is not None
                  assert first_node.key is not None
                  assert (
                      self.list.remove(lowerCAmelCase					) is not None
                  )  # node guaranteed to be in list assert node.key is not None

                  del self.cache[first_node.key]
                  self.num_keys -= 1
              lowerCAmelCase  =				DoubleLinkedListNode(lowerCAmelCase						,						lowerCAmelCase					)
              self.list.add(self.cache[key]					)
              self.num_keys += 1

          else:
              # bump node to the end of the list, update value
              lowerCAmelCase  =				self.list.remove(self.cache[key]					)
              assert node is not None  # node guaranteed to be in list
              lowerCAmelCase  =				value
              self.list.add(lowerCAmelCase					)




      @classmethod
      def   __lowercase (							cls				:			int						,						lowerCAmelCase				:			int = 128					):

          def cache_decorator_inner(lowerCAmelCase				:			Callable[[T], U]					) -> Callable[..., U]:
              def cache_decorator_wrapper(*lowerCAmelCase				:			T					) -> U:
                  if func not in cls.decorator_function_to_instance_map:
                      lowerCAmelCase  =				LRUCache(lowerCAmelCase					)

                  lowerCAmelCase  =				cls.decorator_function_to_instance_map[func].get(args[0]					)
                  if result is None:
                      lowerCAmelCase  =				func(*lowerCAmelCase					)
                      cls.decorator_function_to_instance_map[func].put(args[0]						,						lowerCAmelCase					)
                  return result

              def cache_info() -> LRUCache[T, U]:
                  return cls.decorator_function_to_instance_map[func]

              setattr(lowerCAmelCase						,						"""cache_info"""						,						lowerCAmelCase					)  # noqa: B010

              return cache_decorator_wrapper

          return cache_decorator_inner


if __name__ == "__main__":
  import doctest

  doctest.testmod()











"""simple docstring"""







from queue import PriorityQueue
from typing import Any

import numpy as np





def 							lowercase					(snake_case__   : dict      ,       snake_case__   : str      ,       snake_case__   : set      ,       snake_case__   : set      ,       snake_case__   : dict      ,       snake_case__   : dict      ,       snake_case__   : PriorityQueue      ,       snake_case__   : dict      ,       snake_case__   : float | int      ,       )     ->  float | int:


				'''simple docstring'''






				for nxt, d in graph[v]:
								if nxt in visited_forward:
												continue
								lowerCAmelCase  =				cst_fwd.get(snake_case__      ,       np.inf )
								lowerCAmelCase  =				cst_fwd[v] + d
								if new_cost_f < old_cost_f:
												queue.put((new_cost_f, nxt) )
												lowerCAmelCase  =				new_cost_f
												lowerCAmelCase  =				v
								if nxt in visited_backward:
												if cst_fwd[v] + d + cst_bwd[nxt] < shortest_distance:
																lowerCAmelCase  =				cst_fwd[v] + d + cst_bwd[nxt]
				return shortest_distance





def 							lowercase					(snake_case__   : str      ,       snake_case__   : str      ,       snake_case__   : dict      ,       snake_case__   : dict )     ->  int:


				'''simple docstring'''






				lowerCAmelCase  =				-1

				lowerCAmelCase  =				set()
				lowerCAmelCase  =				set()
				lowerCAmelCase  =				{source: 0}
				lowerCAmelCase  =				{destination: 0}
				lowerCAmelCase  =				{source: None}
				lowerCAmelCase  =				{destination: None}
				lowerCAmelCase  =				PriorityQueue()
				lowerCAmelCase  =				PriorityQueue()

				lowerCAmelCase  =				np.inf

				queue_forward.put((0, source) )
				queue_backward.put((0, destination) )

				if source == destination:
								return 0

				while not queue_forward.empty() and not queue_backward.empty():
								lowerCAmelCase ,						lowerCAmelCase  =				queue_forward.get()
								visited_forward.add(snake_case__ )

								lowerCAmelCase ,						lowerCAmelCase  =				queue_backward.get()
								visited_backward.add(snake_case__ )

								lowerCAmelCase  =				pass_and_relaxation(
								    snake_case__      ,       snake_case__      ,       snake_case__      ,       snake_case__      ,       snake_case__      ,       snake_case__      ,       snake_case__      ,       snake_case__      ,       snake_case__      ,       )

								lowerCAmelCase  =				pass_and_relaxation(
								    snake_case__      ,       snake_case__      ,       snake_case__      ,       snake_case__      ,       snake_case__      ,       snake_case__      ,       snake_case__      ,       snake_case__      ,       snake_case__      ,       )

								if cst_fwd[v_fwd] + cst_bwd[v_bwd] >= shortest_distance:
												break

				if shortest_distance != np.inf:
								lowerCAmelCase  =				shortest_distance
				return shortest_path_distance


a      =							{
    'B': [['C', 1]],
    'C': [['D', 1]],
    'D': [['F', 1]],
    'E': [['B', 1], ['G', 2]],
    'F': [],
    'G': [['F', 1]],
}
a      =							{
    'B': [['E', 1]],
    'C': [['B', 1]],
    'D': [['C', 1]],
    'F': [['D', 1], ['G', 1]],
    'E': [[None, np.inf]],
    'G': [['E', 2]],
}

if __name__ == "__main__":
		import doctest

		doctest.testmod()





