Вам дан взвешенный ориентированный граф с 1 ≤ N ≤ 10 ^ 5 числом узлов от 1 до N, начальный узел S и 1 ≤ M ≤ 10 ^ 5 ребер, которые могут быть трех типов (все с весом):
- Вы можете перейти от узла U к V узел.
- Вы можете перейти от узла U к любому узлу в диапазоне [l, r] .
- Вы можете перейти с любого узлав диапазоне [l, r] до V узел.
Примечание: все веса неотрицательны
Задача состоит в том, чтобынайдите минимальную стоимость (сумму весов в пути), чтобы перейти от S к остальным узлам или сказать, если это не могло произойти.
Значение должно бытьБыстрее, чем сложность O (N * M), сложность, близкая к O (M * log ^ 2 (N)), будет велика.
Мой лучший подход состоял в том, чтобы сделать минимальное количество сегментов с ленивым представлениемответ очереди приоритета, который имеет меньшую стоимость, и узел которого был обновлен для распространения,но это только для ребер типа 1 и 2.
Я не могу придумать, что делать с ребрами третьего типа.Любое решение?