




"""simple docstring"""






from __future__ import annotations

from collections import deque
from collections.abc import Iterator
from dataclasses import dataclass






@dataclass
class lowerCAmelCase__	:






			'''simple docstring'''



			lowerCamelCase__      =			42
			lowerCamelCase__      =			42






class lowerCAmelCase__	:






			'''simple docstring'''



			def __init__(  self  ,      lowercase  ):
							_lowerCamelCase     :			list[list[Edge]]    =    [[] for _ in range(lowercase  )]
							_lowerCamelCase     :			List[Any]    =    size
			def __getitem__(  self  ,      lowercase  ):
							return iter(self._graph[vertex]  )
			@property
			def 					A_    (  self  ):
							return self._size
			def 					A_    (  self  ,      lowercase  ,      lowercase  ,      lowercase  ):
							if weight not in (0, 1):
											raise ValueError('Edge weight must be either 0 or 1.'  )

							if to_vertex < 0 or to_vertex >= self.size:
											raise ValueError('Vertex indexes must be in [0; size).'  )

							self._graph[from_vertex].append(Edge(lowercase  ,      lowercase  )  )






			def 					A_    (  self  ,      lowercase  ,      lowercase  ):
							_lowerCamelCase     :			Dict    =    deque([start_vertex]  )
							_lowerCamelCase     :			list[int | None]    =    [None] * self.size
							_lowerCamelCase     :			str    =    0

							while queue:
											_lowerCamelCase     :			Tuple    =    queue.popleft()
											_lowerCamelCase     :			Any    =    distances[current_vertex]
											if current_distance is None:
															continue

											for edge in self[current_vertex]:
															_lowerCamelCase     :			Dict    =    current_distance + edge.weight
															_lowerCamelCase     :			Optional[Any]    =    distances[edge.destination_vertex]
															if (
															    isinstance(lowercase  ,      lowercase  )
															    and new_distance >= dest_vertex_distance
															):
																			continue
															_lowerCamelCase     :			Union[str, Any]    =    new_distance
															if edge.weight == 0:
																			queue.appendleft(edge.destination_vertex  )
															else:
																			queue.append(edge.destination_vertex  )

							if distances[finish_vertex] is None:
											raise ValueError('No path from start_vertex to finish_vertex.'  )

							return distances[finish_vertex]


if __name__ == "__main__":
			import doctest

			doctest.testmod()



'''simple docstring'''


import unittest

from knapsack import greedy_knapsack as kp





class     lowercase__  (						unittest.TestCase					):





							'''simple docstring'''


							def UpperCAmelCase_	(    self  ):
											_SCREAMING_SNAKE_CASE :       str     		=      [10, 20, 30, 40, 50, 60]
											_SCREAMING_SNAKE_CASE :       List[str]     		=      [2, 4, 6, 8, 10, 12]
											_SCREAMING_SNAKE_CASE :       str     		=      100
											self.assertEqual(kp.calc_profit(__snake_case    ,					__snake_case    ,					__snake_case  )    ,					210  )






							def UpperCAmelCase_	(    self  ):
											self.assertRaisesRegex(__snake_case    ,					"""max_weight must greater than zero."""  )






							def UpperCAmelCase_	(    self  ):
											self.assertRaisesRegex(__snake_case    ,					"""Weight can not be negative."""  )






							def UpperCAmelCase_	(    self  ):
											self.assertRaisesRegex(__snake_case    ,					"""Profit can not be negative."""  )






							def UpperCAmelCase_	(    self  ):
											self.assertRaisesRegex(__snake_case    ,					"""max_weight must greater than zero."""  )






							def UpperCAmelCase_	(    self  ):
											self.assertRaisesRegex(
											    __snake_case    ,					"""The length of profit and weight must be same."""  )


if __name__ == "__main__":
				unittest.main()




