Решение задачи

Самые дешевые авиабилеты в пределах K остановок

Интуиция данной проблемы

Мы можем решить эту задачу различными способами:

Алгоритм Дейкстры - сложность по времени - O(V^2)
Алгоритм Флойда-Уоршалла - сложность по времени - O(v^3)
Алгоритм Беллмана-Форда - сложность по времени - O(V^3)

Для решения задачи я использовал простой BFS. Для более глубокой оптимизации в этом решении можно использовать приоритетную очередь. Но в данном решении я этого не делал.

ПРИМЕЧАНИЕ - ПОЖАЛУЙСТА, СНАЧАЛА ПРОЧИТАЙТЕ ПОДХОД, А ЗАТЕМ ПОСМОТРИТЕ КОД. ПОСЛЕ ОЗНАКОМЛЕНИЯ С ПОДХОДОМ ВЫ ОБЯЗАТЕЛЬНО ПОЙМЕТЕ КОД ПОСТРОЧНО.

Подход к решению данной задачи

1. Инициализируем список смежности с заданной информацией о рейсах, где каждый индекс i представляет узел i, а соответствующее значение является списком пар (сосед, цена), представляющих ребра от узла i к его соседним узлам и цену рейса.

2. Инициализируем очередь с узлом-источником и его стоимостью (0) и вектор minCost с размером, равным количеству узлов, где каждый индекс i представляет минимальную стоимость достижения узла i, а соответствующее значение инициализируется в INT_MAX.

3. Создайте переменную stop и инициализируйте ее значением 0.

4. Запустить цикл while до тех пор, пока очередь не будет пустой, а количество остановок не станет меньше или равно k (максимально допустимое количество остановок).

5. В цикле while создайте переменную size, равную размеру очереди.

6. Запустите еще один цикл while с размером очереди.

7. Во внутреннем цикле while извлечь из очереди передний элемент и присвоить его переменной (currNode, cost).

8. Итерация по соседям и стоимости текущего узла из списка смежности.

9. Если суммарная стоимость достижения соседа больше или равна минимальной стоимости достижения соседа, переходим к следующей итерации.

10. В противном случае минимальная стоимость достижения соседа обновляется как общая стоимость и сосед и его стоимость помещаются в очередь.

11. Завершить внутренний цикл while и увеличить стопы на 1.

12. Завершить внешний цикл while.

13. Если минимальная стоимость достижения пункта назначения по-прежнему равна INT_MAX, то возвращается -1, в противном случае возвращается минимальная стоимость достижения пункта назначения.

КОД:

Python

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        adj = [[] for _ in range(n)]
        for flight in flights:
            adj[flight[0]].append((flight[1], flight[2]))
        
        q = [(src, 0)]
        minCost = [float('inf') for _ in range(n)]
        stops = 0
        
        while q and stops <= k:
            size = len(q)
            for i in range(size):
                currNode, cost = q.pop(0)
                for neighbour, price in adj[currNode]:
                    if price + cost >= minCost[neighbour]:
                        continue
                    minCost[neighbour] = price + cost
                    q.append((neighbour, minCost[neighbour]))
            stops += 1
        
        return -1 if minCost[dst] == float('inf') else minCost[dst]

Временная сложность и пространственная сложность

Временная сложность: O(V + E*K)
Временная сложность данного кода составляет O(V + E*K), где E - количество рейсов, а V - количество городов. Это объясняется тем, что внешний цикл while выполняется не более чем за V итераций, и на каждой итерации внутренний цикл while выполняется не более чем за E итераций. Однако максимальное количество раз, которое может быть обработано ребро, ограничено K.
Пространственная сложность: O(V + E)
пространственная сложность этого кода составляет O(V + E), так как он использует две структуры данных для хранения графа (список списков) и минимальной стоимости достижения каждой вершины (массив целых чисел). Очередь, используемая для отслеживания следующего узла, который необходимо посетить, также занимает O(V) места.

Решение задачи

Report Page