Ford-Bellman AdL

struct edge {
    int a, b, cost;
};

int n, m, v;
vector<edge> e;
const int INF = 1000000000;

void solve() {
    vector<int> d (n, INF);
    d[v] = 0;
    for (int i=0; i<n-1; ++i)
        for (int j=0; j<m; ++j)
            if (d[e[j].a] < INF)
                d[e[j].b] = min (d[e[j].b], d[e[j].a] + e[j].cost);
    // вывод d, например, на экран
}


//Этот алгоритм можно несколько ускорить: зачастую ответ находится уже за несколько фаз,
//а оставшиеся фазы никакой полезной работы не происходит, лишь впустую просматриваются все рёбра.
//Поэтому будем хранить флаг того, изменилось что-то на текущей фазе или нет,
//и если на какой-то фазе ничего не произошло, то алгоритм можно останавливать.
//(Эта оптимизация не улучшает асимптотику, т.е. на некоторых графах по-прежнему будут нужны все n-1 фаза,
//но значительно ускоряет поведение алгоритма "в среднем", т.е. на случайных графах.)

//С такой оптимизацией становится вообще ненужным ограничивать вручную число фаз алгоритма числом n-1 —
//он сам остановится через нужное число фаз.

void solve() {
    vector<int> d (n, INF);
    d[v] = 0;
    for (;;) {
        bool any = false;
        for (int j=0; j<m; ++j)
            if (d[e[j].a] < INF)
                if (d[e[j].b] > d[e[j].a] + e[j].cost) {
                    d[e[j].b] = d[e[j].a] + e[j].cost;
                    any = true;
                }
        if (!any)  break;
    }
    // вывод d, например, на экран
}


//Приведём реализацию Форда-Беллмана с восстановлением пути до какой-то заданной вершины t:

void solve() {
    vector<int> d (n, INF);
    d[v] = 0;
    vector<int> p (n, -1);
    for (;;) {
        bool any = false;
        for (int j=0; j<m; ++j)
            if (d[e[j].a] < INF)
                if (d[e[j].b] > d[e[j].a] + e[j].cost) {
                    d[e[j].b] = d[e[j].a] + e[j].cost;
                    p[e[j].b] = e[j].a;
                    any = true;
                }
        if (!any)  break;
    }

    if (d[t] == INF)
        cout << "No path from " << v << " to " << t << ".";
    else {
        vector<int> path;
        for (int cur=t; cur!=-1; cur=p[cur])
            path.push_back (cur);
        reverse (path.begin(), path.end());

        cout << "Path from " << v << " to " << t << ": ";
        for (size_t i=0; i<path.size(); ++i)
            cout << path[i] << ' ';
    }
}
//Здесь мы сначала проходимся по предкам, начиная с вершины t, и сохраняем весь пройденный путь в списке  path.
//В этом списке получается кратчайший путь от v до t, но в обратном порядке,
//поэтому мы вызываем reverse от него и затем выводим.