Минимальное время для достижения от узла 1 до N, если движение разрешено только тогда, когда узел зеленый

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

Дан неориентированный связный граф из N узлов и M ребер. У каждого узла есть свет, но одновременно он может быть либо зеленым, либо красным. Изначально все узлы зеленого цвета. Через каждые T секунд цвет света меняется с зеленого на красный и наоборот. Переместиться из узла U в узел V можно только в том случае, если цвет узла U зеленый. Время, затрачиваемое на пересечение любых ребер, равно C секунд. Найдите минимальное время, необходимое для перемещения из узла 1 в узел N.

Примеры:

Input: N = 5, M = 5, T = 3, C = 5
           Edges[] = {{1, 2}, {1, 3}, {1, 4}, {2, 4}, {2, 5}}
Output: 11
Explanation: At 0sec, the color of node 1 is green, so travel from node 1 to node 2 in 5sec.
Now at 5sec, the color of node 2 is red so wait 1sec to change into green.
Now at 6sec, the color of node 2 is green, so travel from node 2 to node 5 in 5sec.
Total time = 5(from node 1 to node 2) + 1(wait at node 2) + 5(from node 2 to node 5) = 11 sec.

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

  • Инициализируйте очередь, скажем, Q , в которой хранятся узлы, которые необходимо пройти, и время, необходимое для достижения этого узла.
  • Создайте логический массив, скажем, V , в котором хранится информация о том, посещен ли текущий узел или нет.
  • Поместите узел 1 и время 0 как пару в очередь Q .
  • Учтите, что всегда есть зеленый свет, а для прохождения через ребра требуется 1 секунда, тогда просто запустите BFS и найдите кратчайшее время, необходимое для достижения от узла 1 до узла N, и сохраните его в переменной, скажем, time .
  • Создайте функцию findTime , которая находит время, если для перемещения по краям требуется C секунд, а цвет света меняется через T секунд, выполнив следующие шаги:
    • Инициализируйте переменную an как 0, которая будет хранить минимальное время, необходимое для достижения от узла 1 до узла N.
    • Выполните итерацию в диапазоне [0, время], используя переменную i , и выполните следующие шаги:
      • Если (ans/T) %2 = 1 , тогда измените значение ans как (ans/T + 1)* T + C.
      • В противном случае добавьте C к переменной ans .
  • В качестве ответа выведите ответ.

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

Временная сложность: O(N + M)
Космическая сложность: O(N + M)

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