Путь Пети в школу пролегает через оживлённый перекресток. На этом перекрёстке есть светофоры для пешеходов и светофоры для автомобилей.
Пешеходы могут переходить дорогу только по пешеходным переходам.
Пронумеруем пешеходные переходы числами от 1 до 4 так, как показано на рисунке.
Углы перекрёстка будем обозначать комбинациями цифр 12
23
34
и 41
по номерам переходов, которыми можно воспользоваться, находясь на этом углу.
Для каждого перехода известно время RJ
в течение которого пешеходам горит красный свет, и время GJ
в течение которого пешеходам горит зелёный свет J=1
2 3
4
Ответ напиши на языке пайтон
python
graph = {
'12': {'1', '2'},
'23': {'2', '3'},
'34': {'3', '4'},
'41': {'4', '1'}
}
python
from queue import Queue
def find_shortest_path():
start = '12' # начальный угол перекрестка
end = '1' # конечный угол перекрестка (школа)
visited = set() # множество посещенных узлов
q = Queue() # очередь для обработки узлов
q.put(start) # положить начальный узел в очередь
while not q.empty():
curr = q.get() # извлечь текущий узел из очереди
if curr == end:
# достигли школы, вернуть путь
return visited
visited.add(curr) # добавить текущий узел в множество посещенных
# пройти по всем соседним узлам
for neighbor in graph[curr]:
if neighbor not in visited:
q.put(neighbor) # добавить соседний узел в очередь для обработки
return None # если путь не найден
path = find_shortest_path()
python
total_time = 0
for i in range(len(path) - 1):
from_corner = path[i] # начальный угол перекрестка
to_corner = path[i+1] # конечный угол перекрестка
# найдем пешеходный переход между углами перекрестка
pedestrian_crossing = ''
for crossing, corners in graph.items():
if from_corner in corners and to_corner in corners:
pedestrian_crossing = crossing
break
# добавить время перехода для пешеходного перехода
total_time += time[pedestrian_crossing]
python
from queue import Queue
# граф с описанием светофоров для пешеходов
graph = {
'12': {'1', '2'},
'23': {'2', '3'},
'34': {'3', '4'},
'41': {'4', '1'}
}
# время RJ и GJ для пешеходных переходов
time = {
'12': 30,
'23': 20,
'34': 15,
'41': 25
}
def find_shortest_path():
start = '12' # начальный угол перекрестка
end = '1' # конечный угол перекрестка (школа)
visited = set() # множество посещенных узлов
q = Queue() # очередь для обработки узлов
q.put(start) # положить начальный узел в очередь
while not q.empty():
curr = q.get() # извлечь текущий узел из очереди
if curr == end:
# достигли школы, вернуть путь
return visited
visited.add(curr) # добавить текущий узел в множество посещенных
# пройти по всем соседним узлам
for neighbor in graph[curr]:
if neighbor not in visited:
q.put(neighbor) # добавить соседний узел в очередь для обработки
return None # если путь не найден
path = find_shortest_path()
if path:
total_time = 0
for i in range(len(path) - 1):
from_corner = path[i] # начальный угол перекрестка
to_corner = path[i+1] # конечный угол перекрестка
# найдем пешеходный переход между углами перекрестка
pedestrian_crossing = ''
for crossing, corners in graph.items():
if from_corner in corners and to_corner in corners:
pedestrian_crossing = crossing
break
# добавить время перехода для пешеходного перехода
total_time += time[pedestrian_crossing]
print("Путь до школы:", path)
print("Общее время:", total_time)
else:
print("Путь до школы не найден")
Нажимая «Регистрация» или «Войти через Google», вы соглашаетесь с Публичной офертой, даете Согласие на обработку персональных данных, а также подтверждаете что вам есть 18 лет
Нажимая «Регистрация» или «Войти через Google», вы соглашаетесь с Публичной офертой, даете Согласие на обработку персональных данных, а также подтверждаете что вам есть 18 лет