Для решения этой задачи можно использовать алгоритм поиска в ширину (BFS). Алгоритм будет моделировать движение Пети по пешеходным переходам и оценивать время, необходимое для перехода. В каждой вершине графа мы будем хранить информацию о текущем времени и переходе, который был сделан. Основная идея алгоритма заключается в том, чтобы сначала добавить все возможные стартовые состояния в очередь, а затем поочередно извлекать состояния из очереди и генерировать все возможные следующие состояния. Если мы достигаем конечной вершины (например, перехода 4) и время перехода меньше, чем текущее лучшее время, мы обновляем лучшее время. Для начала реализуем класс "Состояние", который будет хранить информацию о текущем времени, переходе и предыдущем состоянии:

python

class State:

    def __init__(self, time, transition, prev_state):

        self.time = time

        self.transition = transition

        self.prev_state = prev_state

Затем реализуем функцию `bfs`, которая будет выполнять алгоритм поиска в ширину:

python

from collections import deque



def bfs(start_transition, end_transition, red_times, green_times, pedestrian_times):

    # Создаем очередь и добавляем стартовый переход в нее

    queue = deque()

    queue.append(State(0, start_transition, None))

    

    # Создаем словарь для хранения лучшего времени для каждого перехода

    best_times = {transition: float('inf') for transition in range(1, 5)}

    

    while queue:

        # Извлекаем состояние из очереди

        current_state = queue.popleft()

        

        # Если достигли конечного перехода и время перехода меньше текущего лучшего времени, обновляем лучшее время

        if current_state.transition == end_transition and current_state.time < best_times[end_transition]:

            best_times[end_transition] = current_state.time

        

        # Генерируем все возможные следующие состояния

        for next_transition in range(1, 5):

            # Если следующий переход отличается от текущего и есть время на переход, добавляем его в очередь

            if next_transition != current_state.transition and current_state.time < pedestrian_times[next_transition]:

                next_time = current_state.time + red_times[current_state.transition]

                if next_time < pedestrian_times[next_transition] and next_time < best_times[next_transition]:

                    queue.append(State(next_time, next_transition, current_state))

    

    return best_times[end_transition]

Теперь мы можем использовать эту функцию, чтобы решить задачу. Вводим значения для начального и конечного переходов, времен красного и зеленого света для каждого перехода и время, за которое Петя может перейти каждый переход:

python

start_transition = 1

end_transition = 4



red_times = {1: 5, 2: 3, 3: 4, 4: 6}

green_times = {1: 3, 2: 3, 3: 2, 4: 4}



pedestrian_times = {1: 20, 2: 10, 3: 15, 4: 18}



result = bfs(start_transition, end_transition, red_times, green_times, pedestrian_times)



print(f"Лучшее время для перехода с перехода {start_transition} на переход {end_transition}: {result}")

Результатом будет лучшее время для перехода с перехода 1 на переход 4, которое можно получить, пройдя по переходам 1 -> 2 -> 3 -> 4. Важно отметить, что в данном решении мы предполагаем, что переходы между пешеходными переходами могут выполняться только по одному направлению. Если это не так, а переходы можно совершать в обоих направлениях, то решение нужно будет модифицировать, добавив соответствующие возможности переходов.