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

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

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

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

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

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

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

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

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