Всем привет

Недавно встречался с несколькими задачами (в голове) и не мог придумать решение.

1 Дан граф, состоящий из взвешенных неориентированных ребер. Существует два типа запросов.

1. ребро между двумя вершинами.
2. Найти кратчайший путь между двумя вершинами.

Насколько я понимаю, если бы было сказано, что дан лес, задача решалась бы с помощью СНМ или Link-cut tree, но с произвольными графами становится намного сложнее, и вопрос в том, есть ли что-то лучше, чем запуск Дейкстры для каждого запроса второго типа.

2 Дан ориентированный граф и запросы двух типов.

1. добавить в граф ориентированное ребро
2. сказать, есть ли путь между двумя вершинами u, v