

from typing import TYPE_CHECKING

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


a_         =      {
    '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:
			a_         =      [
			    'DPRContextEncoderTokenizerFast',
			    'DPRQuestionEncoderTokenizerFast',
			    'DPRReaderTokenizerFast',
			]

try:
			if not is_torch_available():
						raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
			pass
else:
			a_         =      [
			    '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:
			a_         =      [
			    '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

			a_         =      _LazyModule(__name__, globals()['__file__'], _import_structure, module_spec=__spec__)


from __future__ import annotations






class _UpperCamelCase							:
			'''simple docstring'''







			def __init__(     self							:	List[Any] , a							:	int		)							->    None:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE				: List[str]			       =    vertices
				SCREAMING_SNAKE_CASE				: Tuple			       =    [[0] * vertices for _ in range(a		)]
			def 							__UpperCamelCase	(     self							:	Dict , a							:	list[int]		)							->    None:

				"""simple docstring"""

				print("Vertex \t Distance from Source"		)
				for vertex in range(self.vertices		):
					print(a , "\t\t" , distances_from_source[vertex]		)
			def 							__UpperCamelCase	(     self							:	Tuple , a							:	list[int] , a							:	list[bool]		)							->    int:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE				: Dict			       =    1e7
				SCREAMING_SNAKE_CASE				: int			       =    0

				# Search not nearest vertex not in the shortest path tree
				for vertex in range(self.vertices		):
					if distances_from_source[vertex] < minimum and visited[vertex] is False:
						SCREAMING_SNAKE_CASE				: Optional[int]			       =    distances_from_source[vertex]
						SCREAMING_SNAKE_CASE				: Optional[Any]			       =    vertex
				return min_index






			def 							__UpperCamelCase	(     self							:	Any , a							:	int		)							->    None:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE				: List[str]			       =    [int(1e7		)] * self.vertices  # distances from the source
				SCREAMING_SNAKE_CASE				: Tuple			       =    0
				SCREAMING_SNAKE_CASE				: List[Any]			       =    [False] * self.vertices

				for _ in range(self.vertices		):
					SCREAMING_SNAKE_CASE				: Union[str, Any]			       =    self.minimum_distance(a , a		)
					SCREAMING_SNAKE_CASE				: List[str]			       =    True

					# Update dist value of the adjacent vertices
					# of the picked vertex only if the current
					# distance is greater than new distance and
					# the vertex in not in the shortest path tree
					for v in range(self.vertices		):
						if (
						    self.graph[u][v] > 0
						    and visited[v] is False
						    and distances[v] > distances[u] + self.graph[u][v]
						):
							SCREAMING_SNAKE_CASE				: int			       =    distances[u] + self.graph[u][v]

				self.print_solution(a		)


if __name__ == "__main__":
			a_         =      Graph(9)
			a_         =      [
			    [0, 4, 0, 0, 0, 0, 0, 8, 0],
			    [4, 0, 8, 0, 0, 0, 0, 11, 0],
			    [0, 8, 0, 7, 0, 4, 0, 0, 2],
			    [0, 0, 7, 0, 9, 14, 0, 0, 0],
			    [0, 0, 0, 9, 0, 10, 0, 0, 0],
			    [0, 0, 4, 14, 10, 0, 2, 0, 0],
			    [0, 0, 0, 0, 0, 2, 0, 1, 6],
			    [8, 11, 0, 0, 0, 0, 1, 0, 7],
			    [0, 0, 2, 0, 0, 0, 6, 7, 0],
			]
			graph.dijkstra(0)