Нужна структура поддерживающая следующее:
- добавление нового значения за O(logN)
- узнать минимальный элемент за O(1)
- удалить минимальный элемент за O(logN)
- изменить значение элемента за O(logN)
Будем хранить кроме стандартной кучи, массив valueToIndex[v] = index , в котором для каждой вершины v, храниться указатель/индекс на элемент в куче, где храниться значение времени для этой вершины.
Когда требуется изменить значение в какой то вершине:
- получаем ссылку на элемент в куче, используя массив valueToIndex
- изменяем значение
- т.к. для дейкстры значение может только
уменьшится, то необходимо пропихнуть вверх данный элемент по
рекурсии (не более logN подъемов)
Так же во всех стандартных функциях кучи, при изменении расположения элементов необходимо обновлять значения массива valueToIndex[].
Если реализовывать кучу не на массивах, то необходимо хранить ссылку на предка.
Если какой то момент не понятен, то распишу подробней.