


'''simple docstring'''



import heapq




def       _a      (		_lowercase   :      Union[str, Any]     ,   _lowercase   :      Optional[Any]     ,   _lowercase   :      Union[str, Any]    ):





     '''simple docstring'''






     __UpperCAmelCase      :					Optional[Any]    				=     [(0, start)]  # cost from start node,end node
     __UpperCAmelCase      :					List[Any]    				=     set()
     while heap:
          ((__UpperCAmelCase)				,  (__UpperCAmelCase))      :					Tuple    				=     heapq.heappop(_lowercase    )
          if u in visited:
               continue
          visited.add(_lowercase    )
          if u == end:
               return cost
          for v, c in graph[u]:
               if v in visited:
                    continue
               __UpperCAmelCase      :					int    				=     cost + c
               heapq.heappush(_lowercase     ,   (next_item, v)    )
     return -1


__UpperCAmelCase     :Any												=  {
    """A""": [["""B""", 2], ["""C""", 5]],
    """B""": [["""A""", 2], ["""D""", 3], ["""E""", 1], ["""F""", 1]],
    """C""": [["""A""", 5], ["""F""", 3]],
    """D""": [["""B""", 3]],
    """E""": [["""B""", 4], ["""F""", 3]],
    """F""": [["""C""", 3], ["""E""", 3]],
}
__UpperCAmelCase     :Union[str, Any]												=  {
    """B""": [["""C""", 1]],
    """C""": [["""D""", 1]],
    """D""": [["""F""", 1]],
    """E""": [["""B""", 1], ["""F""", 3]],
    """F""": [],
}
__UpperCAmelCase     :str												=  {
    """B""": [["""C""", 1]],
    """C""": [["""D""", 1]],
    """D""": [["""F""", 1]],
    """E""": [["""B""", 1], ["""G""", 2]],
    """F""": [],
    """G""": [["""F""", 1]],
}

__UpperCAmelCase     :int												=  dijkstra(G, "E", "C")
print(short_distance)  # E -- 3 --> F -- 3 --> C == 6

__UpperCAmelCase     :Optional[Any]												=  dijkstra(Ga, "E", "F")
print(short_distance)  # E -- 3 --> F == 3

__UpperCAmelCase     :List[str]												=  dijkstra(Ga, "E", "F")
print(short_distance)  # E -- 2 --> G -- 1 --> F == 3

if __name__ == "__main__":
      import doctest

      doctest.testmod()






from typing import TYPE_CHECKING

from ...utils import OptionalDependencyNotAvailable, _LazyModule, is_tokenizers_available, is_torch_available


UpperCamelCase__ :			Any       	=			{
    """configuration_splinter""": ["""SPLINTER_PRETRAINED_CONFIG_ARCHIVE_MAP""", """SplinterConfig"""],
    """tokenization_splinter""": ["""SplinterTokenizer"""],
}

try:
				if not is_tokenizers_available():
								raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
				pass
else:
				UpperCamelCase__ :			Any       	=			["""SplinterTokenizerFast"""]

try:
				if not is_torch_available():
								raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
				pass
else:
				UpperCamelCase__ :			Union[str, Any]       	=			[
				    """SPLINTER_PRETRAINED_MODEL_ARCHIVE_LIST""",
				    """SplinterForQuestionAnswering""",
				    """SplinterForPreTraining""",
				    """SplinterLayer""",
				    """SplinterModel""",
				    """SplinterPreTrainedModel""",
				]


if TYPE_CHECKING:
				from .configuration_splinter import SPLINTER_PRETRAINED_CONFIG_ARCHIVE_MAP, SplinterConfig
				from .tokenization_splinter import SplinterTokenizer

				try:
								if not is_tokenizers_available():
												raise OptionalDependencyNotAvailable()
				except OptionalDependencyNotAvailable:
								pass
				else:
								from .tokenization_splinter_fast import SplinterTokenizerFast

				try:
								if not is_torch_available():
												raise OptionalDependencyNotAvailable()
				except OptionalDependencyNotAvailable:
								pass
				else:
								from .modeling_splinter import (
								    SPLINTER_PRETRAINED_MODEL_ARCHIVE_LIST,
								    SplinterForPreTraining,
								    SplinterForQuestionAnswering,
								    SplinterLayer,
								    SplinterModel,
								    SplinterPreTrainedModel,
								)


else:
				import sys

				UpperCamelCase__ :			List[str]       	=			_LazyModule(__name__, globals()["""__file__"""], _import_structure, module_spec=__spec__)


