
'''simple docstring'''







from typing import TYPE_CHECKING

from ...utils import (
    OptionalDependencyNotAvailable,
    _LazyModule,
    is_tf_available,
    is_tokenizers_available,
    is_torch_available,
)


lowercase__     :  Union[str, Any]    					=			{
    'configuration_dpr': ['DPR_PRETRAINED_CONFIG_ARCHIVE_MAP', 'DPRConfig'],
    'tokenization_dpr': [
        'DPRContextEncoderTokenizer',
        'DPRQuestionEncoderTokenizer',
        'DPRReaderOutput',
        'DPRReaderTokenizer',
    ],
}


try:
      if not is_tokenizers_available():
            raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
      pass
else:
      lowercase__     :  Tuple    					=			[
          'DPRContextEncoderTokenizerFast',
          'DPRQuestionEncoderTokenizerFast',
          'DPRReaderTokenizerFast',
      ]

try:
      if not is_torch_available():
            raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
      pass
else:
      lowercase__     :  Optional[int]    					=			[
          'DPR_CONTEXT_ENCODER_PRETRAINED_MODEL_ARCHIVE_LIST',
          'DPR_QUESTION_ENCODER_PRETRAINED_MODEL_ARCHIVE_LIST',
          'DPR_READER_PRETRAINED_MODEL_ARCHIVE_LIST',
          'DPRContextEncoder',
          'DPRPretrainedContextEncoder',
          'DPRPreTrainedModel',
          'DPRPretrainedQuestionEncoder',
          'DPRPretrainedReader',
          'DPRQuestionEncoder',
          'DPRReader',
      ]

try:
      if not is_tf_available():
            raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
      pass
else:
      lowercase__     :  Optional[Any]    					=			[
          'TF_DPR_CONTEXT_ENCODER_PRETRAINED_MODEL_ARCHIVE_LIST',
          'TF_DPR_QUESTION_ENCODER_PRETRAINED_MODEL_ARCHIVE_LIST',
          'TF_DPR_READER_PRETRAINED_MODEL_ARCHIVE_LIST',
          'TFDPRContextEncoder',
          'TFDPRPretrainedContextEncoder',
          'TFDPRPretrainedQuestionEncoder',
          'TFDPRPretrainedReader',
          'TFDPRQuestionEncoder',
          'TFDPRReader',
      ]


if TYPE_CHECKING:
      from .configuration_dpr import DPR_PRETRAINED_CONFIG_ARCHIVE_MAP, DPRConfig
      from .tokenization_dpr import (
          DPRContextEncoderTokenizer,
          DPRQuestionEncoderTokenizer,
          DPRReaderOutput,
          DPRReaderTokenizer,
      )

      try:
            if not is_tokenizers_available():
                  raise OptionalDependencyNotAvailable()
      except OptionalDependencyNotAvailable:
            pass
      else:
            from .tokenization_dpr_fast import (
                DPRContextEncoderTokenizerFast,
                DPRQuestionEncoderTokenizerFast,
                DPRReaderTokenizerFast,
            )

      try:
            if not is_torch_available():
                  raise OptionalDependencyNotAvailable()
      except OptionalDependencyNotAvailable:
            pass
      else:
            from .modeling_dpr import (
                DPR_CONTEXT_ENCODER_PRETRAINED_MODEL_ARCHIVE_LIST,
                DPR_QUESTION_ENCODER_PRETRAINED_MODEL_ARCHIVE_LIST,
                DPR_READER_PRETRAINED_MODEL_ARCHIVE_LIST,
                DPRContextEncoder,
                DPRPretrainedContextEncoder,
                DPRPreTrainedModel,
                DPRPretrainedQuestionEncoder,
                DPRPretrainedReader,
                DPRQuestionEncoder,
                DPRReader,
            )

      try:
            if not is_tf_available():
                  raise OptionalDependencyNotAvailable()
      except OptionalDependencyNotAvailable:
            pass
      else:
            from .modeling_tf_dpr import (
                TF_DPR_CONTEXT_ENCODER_PRETRAINED_MODEL_ARCHIVE_LIST,
                TF_DPR_QUESTION_ENCODER_PRETRAINED_MODEL_ARCHIVE_LIST,
                TF_DPR_READER_PRETRAINED_MODEL_ARCHIVE_LIST,
                TFDPRContextEncoder,
                TFDPRPretrainedContextEncoder,
                TFDPRPretrainedQuestionEncoder,
                TFDPRPretrainedReader,
                TFDPRQuestionEncoder,
                TFDPRReader,
            )

else:
      import sys

      lowercase__     :  Tuple    					=			_LazyModule(__name__, globals()['__file__'], _import_structure, module_spec=__spec__)









'''simple docstring'''







import heapq





def 						snake_case__ (lowerCAmelCase_					,  lowerCAmelCase_					,  lowerCAmelCase_	):
    UpperCamelCase__      =			[(0, start)]  # cost from start node,end node
    UpperCamelCase__      =			set()
    while heap:
        ((UpperCamelCase__)    ,  (UpperCamelCase__))      =			heapq.heappop(lowerCAmelCase_	)
        if u in visited:
            continue
        visited.add(lowerCAmelCase_	)
        if u == end:
            return cost
        for v, c in graph[u]:
            if v in visited:
                continue
            UpperCamelCase__      =			cost + c
            heapq.heappush(lowerCAmelCase_					,  (next_item, v)	)
    return -1


lowercase__     :  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]],
}
lowercase__     :  Optional[int]    					=			{
    'B': [['C', 1]],
    'C': [['D', 1]],
    'D': [['F', 1]],
    'E': [['B', 1], ['F', 3]],
    'F': [],
}
lowercase__     :  Union[str, Any]    					=			{
    'B': [['C', 1]],
    'C': [['D', 1]],
    'D': [['F', 1]],
    'E': [['B', 1], ['G', 2]],
    'F': [],
    'G': [['F', 1]],
}

lowercase__     :  Union[str, Any]    					=			dijkstra(G, 'E', 'C')
print(short_distance)  # E -- 3 --> F -- 3 --> C == 6

lowercase__     :  Optional[int]    					=			dijkstra(Ga, 'E', 'F')
print(short_distance)  # E -- 3 --> F == 3

lowercase__     :  Any    					=			dijkstra(Ga, 'E', 'F')
print(short_distance)  # E -- 2 --> G -- 1 --> F == 3

if __name__ == "__main__":
      import doctest

      doctest.testmod()




