Всем привет

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

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

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

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

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

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

Всем привет!

Я недавно лицом столкнулся с темой оптимизации дп(Кнута-Яо, Лямбда, Convex Hull Trick, разделяй и властвуй), и она мне показалось часто появлявшейся на олимпиадах моего региона. Однако задачи на эту тему я практически не нашел(не отрицаю тот факт, что я плохо искал). Так вот, если у кого-то есть ссылки на задачи по этой теме или метод поиска таких задач и Вы не против поделиться ими, буду очень вам благодарен!