Задача А. НейТронные сети

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

Задача B. Нейронные сети

Так как здесь ограничения несколько больше, Дейкстра с асимптотикой O(n^2 + m), как в Задаче А, не работает. Однако решению с ускоренным Дейкстрой времени хватает.

Задача C. Безопасная передача данных

Найдем крайтчайшие пути от вершины s и от вершины f до всех остальных. Возьмем кратчайший путь от s до f, и пометим все вершины, которые были на этом пути. Второй по длине путь или имеет какую-то вершину кроме этих, или не имеет какой-то из этих вершин.

Рассмотрим первый случай: тогда пройдемся по каждой НЕ помеченной вершине, минимальный по длине путь, проходящий через вершину i равен сумме кратчайших путей от s до i и от i до f.

Рассмотрим второй случай: тогда для каждой вершины кратчайшего пути (кроме s и f) мы будем запускать Дейкстру из s, и искать кратчайший путь без нее.

Итоговая асимптотика O(n*(n*log n + m*log n)) для ускоренного Дейкстры и O(n*(n^2 + m)) для обычного.

В формате входных данных ошибка, n не должно превышать 500. В этом случае времени хватает

Задача D. Зачем тебе бор?! Строй лес!

Возьмем любую вершину, принадлежащую дереву. Назовем ее v. Найдем вершину, которая максимально удалена от v. Назовем ее a. Для вершины a вновь найдем вершину, которая максимально удалена от нее. Назовем ее b. Тогда расстояние между a и b является диаметром дерева. Так как в дереве между любой парой вершин существует ровно один путь, то он и будет кратчайшим, следовательно длину такого пути мы можем посчитать при помощи BFS.

Доказательство:

Теорема 1. Искомое расстояние — расстояние между двумя листами. Доказательство теоремы 1. Пусть искомое расстояние — расстояние между вершинами a и b, где b не является листом. Так как b не является листом, то её степень больше единицы, следовательно, из неё существует ребро в непосещённую вершину (дважды посетить вершину b мы не можем).

Теорема 2. В дереве BFS не существует ребер между вершинами из разных поддеревьев некоторого их общего предка. Доказательство теоремы 2. Предположим, существует ребро u, v между соседними поддеревьями: Рассмотрим первую вершину, в которую приведет наш алгоритм, пусть это вершина u, тогда в ходе рассмотрения всех смежных вершин u мы добавим в список вершину v, тем самым исключив возможность попадания их в разные поддеревья.

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

Таким образом мы доказали, что нам нужно взять вершину u с наибольшей глубиной после первого BFS, очевидно, что ей в пару надо сопоставить вершину w, такую что dist(u, w) максимально. Вершину w можно найти запуском BFS из u.

Итоговая асимптотика — O(n + m).

Задача E. Лекции от gepardo

Кратчайшие пути можно найти за O(n^3) алгоритмом Флойда-Уоршелла. Формально, он не применим к графам, с ребрами отрицательных весов. Однако если на пути между i и j нет цикла отрицательного веса, то алгоритм Флойда-Уоршелла найдет правильный ответ. Как же проверить, подходит ли ответ нам? Итак, пусть на данном графе отработал обычный алгоритм Флойда. Тогда между вершинами i и j не существует кратчайшего пути (по причине наличия цикла отрицательной длины) тогда и только тогда, когда найдётся такая вершина t, достижимая из i и из которой достижима j, для которой выполняется d[t][t] < 0. Итоговая асимптотика O(n^3).

Надеюсь все смогли узнать для себя что-то новое. Удачи в будущих контестах!