Задача 12 — Цикл отрицательного веса, достижимый из s
Ориентированный взвешенный граф (веса любые). Найти цикл отрицательного веса, достижимый из s, или сообщить, что его нет.
Идея. Беллман-Форд делает |V|−1 раундов релаксации — этого хватает для всех кратчайших путей, если нет отрицательных циклов. Если на |V|-м раунде расстояние всё ещё уменьшается — значит есть отрицательный цикл. Сам цикл восстанавливается по массиву предков.