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

Тогда нам просто нужно написать не $\operatorname{dist}[n]$, а $\operatorname{dist}[n][type]$, то есть мы следующим шагом идем по графу $type$, например $type = 0$ --- обычный граф, и $type = 1$ с измененными ребрами.