Представьте, что у нас есть несколько ячеек, и вы можете телепортироваться в другие ячейки через порталы, для каждой ячейки есть время для «телепортации», но есть также некоторые опекуны, в то время как опекуны находятся в той ячейке, в которой вы находитесь. ждать, пока он не уйдет, чтобы вы могли телепортироваться в другую камеру. Найдите минимальное время, потраченное на побег из тюрьмы.
Подведем итог:
У нас есть неориентированный график с затратами, но также есть ограничение: если страж находится в камере, вам нужно подождать, пока он не уйдет, чтобы вы могли телепортироваться.
Что я сделал:
Я сделал обычный алгоритм Дейкстры, но любой обычной ценой я проверил, стоит ли за эту цену: «есть ли в этой камере опекун?» и если да, я бы проверил, сколько секунд, и добавлю это к минимальному времени. Dijkstra реализован с минимальной кучей, и я проверяю опекунов, используя бинарное дерево поиска, основываясь на данных моментах. Также может быть более 1 ячейки, из которой вы можете выйти, и я использую бинарные деревья поиска, чтобы также хранить каждую ячейку, из которой вы можете выйти, чтобы я мог искать «минимум всех минимумов».
Можете ли вы оптимизировать это больше, чем это?
Я имею в виду, я использую бинарные деревья поиска, минимальные кучи, что может занять так много времени? (для графа с 5000 вершинами и около 6000 ребер)