Пособие/«Цикл отрицательного веса»

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

struct Edge { // Создаём структуру ребра, которая содержит его начало, конец и вес
    int a, b, w;
};

const int INF = 1e9; // INF - это очень большое значение, которое превосходит модуль любого кратчайшего расстояния

void solve() {
    int n;
    cin >> n; // Считываем кол-во вершин в графе
    vector<Edge> ve; // Создаём массив рёбер
    for (int i = 0; i < n; ++i) { // Итерируемся по строкам матрицы смежности
        for (int j = 0; j < n; ++j) { // Итерируемся по столбцам
            int w;
            cin >> w; // считываем вес ребра i->j
            if (w == 100000) continue; // Если ребра нет (По условию в таком случае вес равен 100000), то пропускаем добавление этого ребра в массив
            ve.push_back({i, j, w}); // Добавляем ребро в массив рёбер
        }
    }
    vector<int> d(n, INF), p(n); // d[i] = x, означает, что  вес кратчайшего пути от 0-ой вершины до i-ой равен x
                                 // p[i] = j обозначает, что в легчайшем пути, ведущем в i-ую вершину, есть ребро j -> i.
    d[0] = 0; // расстояние от 0-ой вершины до самой себя равно 0
    int start; // start - вершина, вес кратчайшее расстояние до которой изменится на n-ой (по счёту) фазе, если есть цикл отрицательного веса
    for (int phase = 0; phase < n; ++phase) { // Перебираем фазу
        start = -1; // устанавливаем в start какое-либо значение, которое не может быть номером вершины (В данном случае -1)
        for (Edge edge : ve) { // Перебираем ребро, вдоль которого мы попытаемся сделать релаксацию
            if (d[edge.b] > d[edge.a] + edge.w) { // Если кратчайшее расстояние до edge.b-ой вершины больше, чем кратчайшее расстояние до edge.a-ой вершины плюс вес ребра a->b, то можно успешно выполнить релаксацию
                d[edge.b] = max(-INF, d[edge.a] + edge.w); // Присваиваем новое известное кратчайшее расстояние до edge.b-ой вершины.
                                                           // Нужно ограничить присваиваемое значений по нижней границе числом -INF, так как, если есть отрицательный цикл, то кратчайшее расстояние может чрезвычайно быстро стремиться к минус бесконечности, что может привести к числам, которые невозможно записать с помощью int/long long/...
                p[edge.b] = edge.a; // Указываем предка для edge.a-ой вершины
                start = edge.b; // Присваиваем номер вершины, для которой изменилось кратчайшее расстояние, start-у
            }
        }
    }
    if (start != -1) { // Если на n-ой (по счёту) фазе были изменения среди кратчайших расстояний, то цикл отрицательного веса существует
        vector<int> path; // path - это вершины отрицательного цикла в порядке обхода
        for (int i = 0; i < n; ++i) { // n раз "шагаем" назад, чтобы попасть в какую вершину отрицательного цикла
            start = p[start];
        }
        int at = start; // at - текущая вершины отрицательного цикла
        while (p[at] != start) { // Пока следующая вершина в порядке обхода не является изначальной --- продолжаем
            path.push_back(at); // Добавляем в вершины цикла текущую вершину
            at = p[at]; // Переход к следующей вершине (В обратном порядке, ведь мы "шагаем" назад) отрицательного цикла
        }
        path.push_back(at); // Добавляем последнюю вершину
        reverse(path.begin(), path.end()); // Инвертируем вершины отрицательного цикла, так как мы записывали их в обратном порядке, а нам нужно вывести вершины в порядке обхода
        cout << "YES\n"; // Выводим "YES", так как отрицательный цикл в графе есть
        cout << path.size() << '\n'; // Выводим кол-во вершин в этом цикле
        for (auto el : path) { // Выводим вершины отрицательного цикла
            cout << el + 1 << ' ';
        }
    } else { // Если на n-ой (по счёту) фазе не было изменений среди кратчайших расстояний, то отрицательного цикла нет
        cout << "NO";
    }
}

int main() {
    solve();
    return 0;
}