



import heapq


def 	_UpperCAmelCase       (   snake_case			,		snake_case			,		snake_case    ):





					"""simple docstring"""

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


A__			   = {
    """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]],
}
A__			   = {
    """B""": [["""C""", 1]],
    """C""": [["""D""", 1]],
    """D""": [["""F""", 1]],
    """E""": [["""B""", 1], ["""F""", 3]],
    """F""": [],
}
A__			   = {
    """B""": [["""C""", 1]],
    """C""": [["""D""", 1]],
    """D""": [["""F""", 1]],
    """E""": [["""B""", 1], ["""G""", 2]],
    """F""": [],
    """G""": [["""F""", 1]],
}

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

A__			   = dijkstra(Ga, """E""", """F""")
print(short_distance)  # E -- 3 --> F == 3

A__			   = dijkstra(Ga, """E""", """F""")
print(short_distance)  # E -- 2 --> G -- 1 --> F == 3

if __name__ == "__main__":
	import doctest

	doctest.testmod()








from __future__ import annotations


def 	_UpperCAmelCase       (   snake_case    ):





					"""simple docstring"""

					_lowerCAmelCase      			=					sorted(snake_case    )
					_lowerCAmelCase      			=					len(snake_case    )
					_lowerCAmelCase      			=					length >> 1
					return (
					    (sorted_list[mid_index] + sorted_list[mid_index - 1]) / 2
					    if length % 2 == 0
					    else sorted_list[mid_index]
					)


def 	_UpperCAmelCase       (   ):





					"""simple docstring"""

					import doctest

					doctest.testmod()


if __name__ == "__main__":
	main()



