Задача А. НейТронные сети
В этой задаче рекомендуется использовать алгоритм Дейкстры. Но необходимо помнить, что в этой конкретной задаче при заходе в некторые вершины длина пути так же увеличивается.
Задача 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) для обычного.