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

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