Идея автора изначального сообщения выглядит не очень верно, похоже, она будет где-то выбирать место сбора за стражей.

Задача в версии 3 великолепна, спасибо Ивану Метельскому (ivan.metelsky)
Похоже, решение я придумал, но я бы не хотел писать его на живом контесте :)

Понятно, что случай пути длины 1 и 2 можно рассмотреть за O(M) отдельно. Кроме того, нужно сделать все веса ребер различными.

Рассмотрим некоторое ребро u->v. Будем считать, что на этом ребре у нас возьмут пошлину, т.е. оно одно из худших на пути, причем вдоль этого пути оно второе из таких. Тогда на пути A->u и v->B должно быть не более одного ребра длиннее u->v. Таким образом, задача сведена к обработке двух запросов (для В симметрично):
1) Изменить флаг для ребра с "запрещено" на "разрешено".
2) Найти путь с минимальным максимальным весом ребра, использующий не более одного запрещенного ребра, от А до u.
Причем гарантируется, что вес любого разрешенного ребра не больше веса любого запрещенного. (После этого понятно - обрабатываем ребра в порядке возрастания веса и т.д.)
Запросы можно выполнять так. Будем хранить связные компоненты разрешенных ребер (например, при помощи disjoint-set, причем с модификацией, позволяющей за размер компоненты ее перечислить - это можно сделать, храня весь список компоненты вместо ранга и объединяя с перекидыванием меньшей). Далее, если A и u в одной такой компоненте, то ответ - решение задачи (1) для (A,u), и он предпросчитан. Если они в разной, то единственный запрещенный переход является худшим. Осталось найти его длину. Для этого будем хранить расстояние от компоненты, содержащей А, до всех всех остальных компонент, или бесконечность, если для этого потребуется два и более запрещенных перехода. Обрабатывать это будем так:
1) Соединяются две компоненты с расстоянием бесконечность - игнорировать
2) Соединяются две компоненты, расстояние до одной не бесконечность, а до другой бесконечность. Весь состав "бесконечной" компоненты необходимо проверить на предмет улучшения расстояния "конечной".
3) Соединяются две компоненты, расстояние до обеих конечно. Ответ новой - минимум из бывших ответов.
4) Группа соединяется с содержащей А. Весь состав присоединяющейся группы необходимо проверить на предмет улучшения до некоторого соседа А.
Update. Здесь пропущен важный случай. Необходимо также проверять в главном цикле, что не происходит ситуации, что два ребра пути v->B больше, чем самое длинное на пути A->u. Для этого в этом пункте необходимо выбросить из главного цикла все будущие ребра, ведущие из присоединяемой компоненты в вершину, такую, что из В до нее нельзя добраться, используя не более одного "запрещенного" ребра.

Заметим, что в сумме проверки 2) и 4) потребуют O(M) времени (каждая вершина пройдет эту фазу не более 1 раза). Проверки 1) и 3) выполняются за О(1).

Ответом на запрос здесь будет расстояние от компоненты, содержащей A, до компоненты, содержащей u.

Итоговая сложность O(M*log(M))
Как-то так...