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