Минимальная стоимость пути между заданными узлами, содержащими не более K узлов в ориентированном и взвешенном графе

Опубликовано: 20 Сентября, 2022

Дан направленный взвешенный граф, представленный двумерным графом-массивом[][] размера n и тремя целыми числами src, dst и k , представляющими исходную точку, конечную точку и доступное количество остановок. Задача состоит в том, чтобы минимизировать стоимость пути между двумя узлами, содержащими не более K узлов, в ориентированном и взвешенном графе. Если такого маршрута нет, верните -1 .

Примеры:

Input: n=6, graph[][] = [[0, 1, 10], [1, 2, 20], [1, 3, 10], [2, 5, 30], [3, 4, 10], [4, 5, 10]], src=0, dst=5, k=2
Output: 60
Explanation:

Src = 0, Dst = 5 and k = 2

There can be a route marked with a green arrow that takes cost =  10+10+10+10=40 using three stops. And route marked with red arrow takes cost = 10+20+30=60 using two stops. But since there can be at most 2 stops, the answer will be 60.

Input: n=3, graph[][] = [[0, 1, 10], [0, 2, 50], [1, 2, 10], src=0, dst=2, k=1
Output:  20
Explanation:

Src=0 and Dst=2

Since the k is 1, then the green-colored path can be taken with a minimum cost of 20.

Подход: увеличьте k на 1 , потому что при достижении пункта назначения будет израсходовано k+1 остановок. Используйте поиск в ширину для запуска цикла while, пока очередь не станет пустой. Каждый раз выталкивайте все элементы из очереди и уменьшайте k на 1 , проверяйте их соседний список элементов и проверяйте, не посещались ли они ранее или их стоимость больше, чем стоимость родительского узла + стоимость этого узла , затем отметьте их цены ценами [родительский] + стоимость этого узла . Если k становится равным 0 , цикл while прерывается, потому что либо рассчитывается стоимость, либо мы израсходовали k+1 остановок. Выполните следующие шаги, чтобы решить проблему:

  • Увеличьте значение k на 1.
  • Инициализируйте вектор пары adj[n] и создайте список смежности для графа.
  • Инициализируйте вектор price[n] со значениями -1.
  • Инициализировать очередь пары q[].
  • Поместите пару {src, 0} в очередь и установите значение price[0] равным 0 .
  • Пройдите в цикле while, пока очередь не станет пустой, и выполните следующие шаги:
    • Если k равно 0 , то разбить.
    • Инициализируйте переменную sz как размер очереди.
    • Пройдите в цикле while, пока sz не станет больше 0 , и выполните следующие задачи:
      • Инициализируйте узел переменных как первое значение передней пары очереди и стоимость как второе значение передней пары очереди.
      • Перебрать диапазон [0, adj[node].size()) с помощью переменной it и выполнить следующие задачи:
        • Если Prices[it.first] равно -1 или cost + it.second меньше, чем Prices[it.first] , тогда установите значение Prices[it.first] как cost + it.second и нажмите пару {it.first , cost + it.second} в очередь.
    • Уменьшите значение k на 1.
  • После выполнения вышеуказанных шагов выведите в качестве ответа значение price[dst] .

Ниже приведена реализация вышеуказанного подхода:


Временная сложность: O(n*k)
Вспомогательное пространство: O(n)

РЕКОМЕНДУЕМЫЕ СТАТЬИ