[Задача А. НейТронные сети](https://codeforces.com/gym/269718/problem/A)↵
------------------------------------------------------------------------↵
В этой задаче рекомендуется использовать [алгоритм Дейкстры](https://e-maxx.ru/algo/dijkstra). Но необходимо помнить, что в этой конкретной задаче при заходе в некторые вершины длина пути так же увеличивается.↵
[Задача B. Нейронные сети](https://codeforces.com/gym/269718/problem/B)↵
-----------------------------------------------------------------------↵
Так как здесь ограничения несколько больше, Дейкстра с асимптотикой O(n^2 + m), как в Задаче А, не работает. Однако решению с [ускоренным Дейкстрой](https://e-maxx.ru/algo/dijkstra_sparse) времени хватает.↵
[Задача C. Безопасная передача данных](https://codeforces.com/gym/269718/problem/C)↵
-----------------------------------------------------------------------------------↵
Найдем крайтчайшие пути от вершины s и от вершины f до всех остальных. Возьмем кратчайший путь от s до f, и пометим все вершины, которые были на этом пути. Второй по длине путь или имеет какую-то вершину кроме этих, или не имеет какой-то из этих вершин. ↵
↵
Рассмотрим первый случай: тогда пройдемся по каждой НЕ помеченной вершине, минимальный по длине путь, проходящий через вершину i равен сумме кратчайших путей от s до i и от i до f.↵
↵
Рассмотрим второй случай: тогда для каждой вершины кратчайшего пути (кроме s и f) мы будем запускать Дейкстру из s, и искать кратчайший путь без нее.↵
↵
Итоговая асимптотика O(n^2*log n) для ускоренного Дейкстры и O(n^3) для обычного.*(n*log n + m*log n)) для ускоренного Дейкстры и O(n*(n^2 + m)) для обычного.↵
↵
**В формате входных данных ошибка, n не должно превышать 500. В этом случае времени хватает**↵
[Задача D. Зачем тебе бор?! Строй лес!](https://codeforces.com/gym/269718/problem/D)↵
------------------------------------------------------------------------------------↵
Возьмем любую вершину, принадлежащую дереву. Назовем ее v. Найдем вершину, которая максимально удалена от v. Назовем ее a. Для вершины a вновь найдем вершину, которая максимально удалена от нее. Назовем ее b. Тогда расстояние между a и b является диаметром дерева.↵
↵
Доказательство:↵
↵
Теорема 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](https://codeforces.com/gym/269718/problem/E)↵
--------------------------------------------------------------------------↵
Кратчайшие пути можно найти за O(n^3) алгоритмом Флойда-Уоршелла. Формально, он не применим к графам, с ребрами отрицательных весов. Однако если на пути между i и j нет цикла отрицательного веса, то алгоритм Флойда-Уоршелла найдет правильный ответ. Как же проверить, подходит ли ответ нам?↵
Итак, пусть на данном графе отработал обычный алгоритм Флойда. Тогда между вершинами i и j не существует кратчайшего пути (по причине наличия цикла отрицательной длины) тогда и только тогда, когда найдётся такая вершина t, достижимая из i и из которой достижима j, для которой выполняется d[t][t] < 0.↵
Итоговая асимптотика O(n^3).↵
↵
Надеюсь все смогли узнать для себя что-то новое. Удачи в будущих контестах!
------------------------------------------------------------------------↵
В этой задаче рекомендуется использовать [алгоритм Дейкстры](https://e-maxx.ru/algo/dijkstra). Но необходимо помнить, что в этой конкретной задаче при заходе в некторые вершины длина пути так же увеличивается.↵
[Задача B. Нейронные сети](https://codeforces.com/gym/269718/problem/B)↵
-----------------------------------------------------------------------↵
Так как здесь ограничения несколько больше, Дейкстра с асимптотикой O(n^2 + m), как в Задаче А, не работает. Однако решению с [ускоренным Дейкстрой](https://e-maxx.ru/algo/dijkstra_sparse) времени хватает.↵
[Задача C. Безопасная передача данных](https://codeforces.com/gym/269718/problem/C)↵
-----------------------------------------------------------------------------------↵
Найдем крайтчайшие пути от вершины s и от вершины f до всех остальных. Возьмем кратчайший путь от s до f, и пометим все вершины, которые были на этом пути. Второй по длине путь или имеет какую-то вершину кроме этих, или не имеет какой-то из этих вершин. ↵
↵
Рассмотрим первый случай: тогда пройдемся по каждой НЕ помеченной вершине, минимальный по длине путь, проходящий через вершину i равен сумме кратчайших путей от s до i и от i до f.↵
↵
Рассмотрим второй случай: тогда для каждой вершины кратчайшего пути (кроме s и f) мы будем запускать Дейкстру из s, и искать кратчайший путь без нее.↵
↵
Итоговая асимптотика O(n
↵
**В формате входных данных ошибка, n не должно превышать 500. В этом случае времени хватает**↵
[Задача D. Зачем тебе бор?! Строй лес!](https://codeforces.com/gym/269718/problem/D)↵
------------------------------------------------------------------------------------↵
Возьмем любую вершину, принадлежащую дереву. Назовем ее v. Найдем вершину, которая максимально удалена от v. Назовем ее a. Для вершины a вновь найдем вершину, которая максимально удалена от нее. Назовем ее b. Тогда расстояние между a и b является диаметром дерева.↵
↵
Доказательство:↵
↵
Теорема 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](https://codeforces.com/gym/269718/problem/E)↵
--------------------------------------------------------------------------↵
Кратчайшие пути можно найти за O(n^3) алгоритмом Флойда-Уоршелла. Формально, он не применим к графам, с ребрами отрицательных весов. Однако если на пути между i и j нет цикла отрицательного веса, то алгоритм Флойда-Уоршелла найдет правильный ответ. Как же проверить, подходит ли ответ нам?↵
Итак, пусть на данном графе отработал обычный алгоритм Флойда. Тогда между вершинами i и j не существует кратчайшего пути (по причине наличия цикла отрицательной длины) тогда и только тогда, когда найдётся такая вершина t, достижимая из i и из которой достижима j, для которой выполняется d[t][t] < 0.↵
Итоговая асимптотика O(n^3).↵
↵
Надеюсь все смогли узнать для себя что-то новое. Удачи в будущих контестах!
