unilecs116_train

unilecs116_train.py

# вспоминаем динамическое программирование и алгоритм Дейкстры

def task_116(oil_costs, train_roads):
    
    # граф представим в удобном виде - массив, в i-м элементе будет множество городов, в какие можно попасть из i-го
    # пока создаём пустой граф
    graph = [set() for i in range(0, len(oil_costs))]
    
    # множество непосещённых алгоритмом городов, сразу наполняем всем городами, 1-й город здесь будет 0-м (и далее)
    not_visited = set(range(0, len(oil_costs)))
    
    # массив наименьшей стоимости проезда из 1-го города до i-го, пока наполняем условной бесконечностью
    prices = [max(oil_costs) * len(oil_costs) + 1] * len(oil_costs)
    # мы уже в 1м городе, и ничего не заплатили
    prices[0] = 0
    
    # массив путей - показывает из какого города нужно придти в i-й, чтобы оптимально добраться до последнего
    path = [-1] * len(oil_costs)

    # наполняем граф, теперь, чтобы узнать, куда можно пойти из i-го города, нужно взять i-й элемент этого массива
    for i in range(0, len(train_roads)):
        graph[train_roads[i][0] - 1].add(train_roads[i][1] - 1)
        graph[train_roads[i][1] - 1].add(train_roads[i][0] - 1)
    
    # объявляем функцию, которая ищет нам город для рассмотрения
    # в такие города мы будем отправлять чтобы пробовать через них проложить оптимальный путь
    def find_next():
        # если нет непосещённых городов, возвращаем -1
        if not_visited == set():
            return -1
        # если мы не рассматривали первый город, то рассмотрим сначала его
        if 0 in not_visited:
            return 0
        # если i-й город не посещён и из него можно отправиться в непосещённые города, то выбираем его!
        for i in range(1, len(oil_costs)):
            if i in not_visited and graph[i] - not_visited > set():
                return i
        # если пути из первого в послений город вообще нет, то мы попадём когда-нибудь сюда
        return -1

    # решение подзадачи: находясь в определённом городе, проверяем, не выгодно ли из него добраться до соседних и если выгоднее ранее рассмотренных вариантов, то записываем найденный
    def count_cost(a):
        # перебираем все города, которые можно посетить в окрестности
        for i in graph[a]:
            # если город i непосещённый и в него выгоднее добраться через рассматриваемый a, то бинго!
            if i in not_visited and prices[i] > prices[a] + oil_costs[a]:
                # запишем новую стоимость добирания до этого города i
                prices[i] = prices[a] + oil_costs[a]
                # запишем в пути, откуда и куда мы пришли (из a в i)
                path[i] = a
        # удалим город из посещённых
        not_visited.discard(a)
    
    # пока сможем находить новые города, будем считать путь
    while find_next() != -1:
        count_cost(find_next())
    
    # задача уже решена, но нужно напечатать ответ, для этого чуть-чуть спагетти
    i = len(path) - 1
    # если путь найден
    if path[i] > -1:
        answer = str(i + 1)
        i = path[i]
        # то нужно идти от последнего города в тот, откуда в него выгоднее придти
        while i > -1:
            answer = str(i + 1) + " -> " + answer # ответ пишем задом-наперёд!
            # и дальше мы пойдём в тот, откуда выгоднее придти в данный
            i = path[i]
        print(answer)
    else:
        print("No path!")
    print()

oil_costs = [5, 10, 1]
train_roads = [(1, 3), (1, 2), (3, 2)]
task_116(oil_costs, train_roads)
    
oil_costs = [1, 2, 3, 4, 5, 6]
train_roads = [(1, 5)]
task_116(oil_costs, train_roads)
    
oil_costs = [1, 2, 3, 4, 5, 6]
train_roads = [(1, 6)]
task_116(oil_costs, train_roads)

oil_costs = [1, 200, 3, 4, 5, 6]
train_roads = [(1, 2), (2, 6), (3, 1), (3, 4), (4, 5), (5, 6), (2, 5)]
task_116(oil_costs, train_roads)

oil_costs = [1, 2, 3, 4, 5, 6, 7]
train_roads = [(1, 2), (1, 3), (3, 4), (2, 4), (4, 5), (4, 6), (5, 7), (6, 7), (3, 6)]
task_116(oil_costs, train_roads)