






from __future__ import annotations


class 				__a				:





		'''simple docstring'''



		def __init__(    self			,     UpperCamelCase__							):
						SCREAMING_SNAKE_CASE_ :						Union[str, Any]    				= vertices
						SCREAMING_SNAKE_CASE_ :						Union[str, Any]    				= [[0] * vertices for _ in range(UpperCamelCase__							)]


		def 	__snake_case      (    self			,     UpperCamelCase__							):
						print('Vertex \t Distance from Source'							)
						for vertex in range(self.vertices							):
										print(UpperCamelCase__			,     '\t\t'			,     distances_from_source[vertex]							)


		def 	__snake_case      (    self			,     UpperCamelCase__			,     UpperCamelCase__							):
						SCREAMING_SNAKE_CASE_ :						Union[str, Any]    				= 1E7
						SCREAMING_SNAKE_CASE_ :						Optional[Any]    				= 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 	__snake_case      (    self			,     UpperCamelCase__							):
						SCREAMING_SNAKE_CASE_ :						Any    				= [int(1E7							)] * self.vertices  # distances from the source
						SCREAMING_SNAKE_CASE_ :						int    				= 0
						SCREAMING_SNAKE_CASE_ :						Any    				= [False] * self.vertices

						for _ in range(self.vertices							):
										SCREAMING_SNAKE_CASE_ :						Tuple    				= self.minimum_distance(UpperCamelCase__			,     UpperCamelCase__							)
										SCREAMING_SNAKE_CASE_ :						Dict    				= 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_ :						Tuple    				= distances[u] + self.graph[u][v]

						self.print_solution(UpperCamelCase__							)


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)







import json
import os
import unittest

from transformers import HerbertTokenizer, HerbertTokenizerFast
from transformers.models.herbert.tokenization_herbert import VOCAB_FILES_NAMES
from transformers.testing_utils import get_tests_dir, require_tokenizers, slow

from ...test_tokenization_common import TokenizerTesterMixin


@require_tokenizers
class 				__a				(	__A			,						unittest.TestCase    ):





		'''simple docstring'''



		UpperCAmelCase__   :					Optional[Any]					     =    HerbertTokenizer
		UpperCAmelCase__   :					List[Any]					     =    HerbertTokenizerFast
		UpperCAmelCase__   :					Optional[Any]					     =    True


		def 	__snake_case      (    self							):
						super().setUp()

						# Use a simpler test file without japanese/chinese characters
						with open(F'''{get_tests_dir()}/fixtures/sample_text_no_unicode.txt'''			,     encoding='utf-8'							) as f_data:
										SCREAMING_SNAKE_CASE_ :						Dict    				= f_data.read().replace('\n\n'			,     '\n'							).strip()

						SCREAMING_SNAKE_CASE_ :						str    				= [
						    '<s>',
						    '</s>',
						    'l',
						    'o',
						    'w',
						    'e',
						    'r',
						    's',
						    't',
						    'i',
						    'd',
						    'n',
						    'w</w>',
						    'r</w>',
						    't</w>',
						    'lo',
						    'low',
						    'er</w>',
						    'low</w>',
						    'lowest</w>',
						    'newer</w>',
						    'wider</w>',
						    ',</w>',
						    '<unk>',
						]
						SCREAMING_SNAKE_CASE_ :						str    				= dict(zip(UpperCamelCase__			,     range(len(UpperCamelCase__							)							)							)							)
						SCREAMING_SNAKE_CASE_ :						Optional[int]    				= ['l o 123', 'lo w 1456', 'e r</w> 1789', '']

						SCREAMING_SNAKE_CASE_ :						int    				= os.path.join(self.tmpdirname			,     VOCAB_FILES_NAMES['vocab_file']							)
						SCREAMING_SNAKE_CASE_ :						int    				= os.path.join(self.tmpdirname			,     VOCAB_FILES_NAMES['merges_file']							)
						with open(self.vocab_file			,     'w'							) as fp:
										fp.write(json.dumps(UpperCamelCase__							)							)
						with open(self.merges_file			,     'w'							) as fp:
										fp.write('\n'.join(UpperCamelCase__							)							)


		def 	__snake_case      (    self			,     UpperCamelCase__							):
						SCREAMING_SNAKE_CASE_ :						Union[str, Any]    				= 'lower newer'
						SCREAMING_SNAKE_CASE_ :						int    				= 'lower newer'
						return input_text, output_text


		def 	__snake_case      (    self							):
						SCREAMING_SNAKE_CASE_ :						List[Any]    				= self.tokenizer_class(vocab_file=self.vocab_file			,     merges_file=self.merges_file							)

						SCREAMING_SNAKE_CASE_ :						Optional[int]    				= 'lower'
						SCREAMING_SNAKE_CASE_ :						Optional[Any]    				= ['low', 'er</w>']
						SCREAMING_SNAKE_CASE_ :						int    				= tokenizer.tokenize(UpperCamelCase__							)
						self.assertListEqual(UpperCamelCase__			,     UpperCamelCase__							)

						SCREAMING_SNAKE_CASE_ :						Union[str, Any]    				= tokens + ['<unk>']
						SCREAMING_SNAKE_CASE_ :						List[Any]    				= [16, 17, 23]
						self.assertListEqual(tokenizer.convert_tokens_to_ids(UpperCamelCase__							)			,     UpperCamelCase__							)


		def 	__snake_case      (    self							):
						if not self.test_rust_tokenizer:
										return

						SCREAMING_SNAKE_CASE_ :						Optional[Any]    				= self.get_tokenizer()
						SCREAMING_SNAKE_CASE_ :						Optional[Any]    				= self.get_rust_tokenizer()

						SCREAMING_SNAKE_CASE_ :						List[str]    				= 'lower,newer'

						SCREAMING_SNAKE_CASE_ :						Optional[int]    				= tokenizer.tokenize(UpperCamelCase__							)
						SCREAMING_SNAKE_CASE_ :						Tuple    				= rust_tokenizer.tokenize(UpperCamelCase__							)
						self.assertListEqual(UpperCamelCase__			,     UpperCamelCase__							)

						SCREAMING_SNAKE_CASE_ :						Optional[Any]    				= tokenizer.encode(UpperCamelCase__			,     add_special_tokens=UpperCamelCase__							)
						SCREAMING_SNAKE_CASE_ :						Any    				= rust_tokenizer.encode(UpperCamelCase__			,     add_special_tokens=UpperCamelCase__							)
						self.assertListEqual(UpperCamelCase__			,     UpperCamelCase__							)

						SCREAMING_SNAKE_CASE_ :						Union[str, Any]    				= self.get_rust_tokenizer()
						SCREAMING_SNAKE_CASE_ :						Dict    				= tokenizer.encode(UpperCamelCase__							)
						SCREAMING_SNAKE_CASE_ :						Optional[int]    				= rust_tokenizer.encode(UpperCamelCase__							)
						self.assertListEqual(UpperCamelCase__			,     UpperCamelCase__							)






		@slow
		def 	__snake_case      (    self							):
						SCREAMING_SNAKE_CASE_ :						Optional[int]    				= self.tokenizer_class.from_pretrained('allegro/herbert-base-cased'							)

						SCREAMING_SNAKE_CASE_ :						List[str]    				= tokenizer.encode('konstruowanie sekwencji'			,     add_special_tokens=UpperCamelCase__							)
						SCREAMING_SNAKE_CASE_ :						Optional[int]    				= tokenizer.encode('konstruowanie wielu sekwencji'			,     add_special_tokens=UpperCamelCase__							)

						SCREAMING_SNAKE_CASE_ :						Any    				= tokenizer.build_inputs_with_special_tokens(UpperCamelCase__							)
						SCREAMING_SNAKE_CASE_ :						Dict    				= tokenizer.build_inputs_with_special_tokens(UpperCamelCase__			,     UpperCamelCase__							)

						assert encoded_sentence == [0] + text + [2]
						assert encoded_pair == [0] + text + [2] + text_a + [2]