Lyceum Contest #2 — 2020 — Разбор

Revision ru3, by klimandr, 2020-02-18 15:07:39

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

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

Задача 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) для обычного.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru5 Russian klimandr 2020-02-18 23:23:27 430 Текст (по мнению автора) теперь отформатирован красивее. Или красивее. Я не разбираюсь в ударениях :(
ru4 Russian klimandr 2020-02-18 23:17:44 2641 (опубликовано)
ru3 Russian klimandr 2020-02-18 15:07:39 676
ru2 Russian klimandr 2020-02-18 14:49:05 456
ru1 Russian klimandr 2020-02-18 14:43:44 915 Первая редакция (сохранено в черновиках)