Dijkstra, Floid and Ford-Bellman

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>

using namespace std;

const int inf = 1e9;

int dist[100000];
bool used[100000];
int mas[1000][1000];
vector<pair<int, int>> ans;
int pr[1000][1000];
pair<int, int> put[1000][1000];
vector<pair<int, int>> matr[100000];

int w[1000][1000];

void floid(int n) {
    for (int i = 0; i < n; ++i) {
        fill(w[i], w[i] + n, inf);
        for (auto u : matr[i]) {
            w[i][u.second] = u.first;
        }
    }
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                w[i][j] = min(w[i][j], w[i][k] + w[k][j]);
            }
        }
    }
}

struct S {
    int from;
    int to;
    int cost;
};

vector<S> edges;

void ford_bellman(int v, int n, int m) {
    vector<int> dist(n, inf);
    dist[v] = 0;
    for (int i = 0; i < n - 1; ++i) {
        bool change = false;
        for (int j = 0; j < edges.size(); ++j) {
            int v = edges[j].from;
            int u = edges[j].to;
            if (dist[v] < inf)
                if (dist[u] > dist[v] + edges[j].cost) {
                    dist[u] = dist[v] + edges[j].cost;
                    change = true;
                }
        }
        if (!change)  break;
    }
}

// с восстановлением пути
void ford_bellman_paths(int v, int n, int m) {
    vector<int> pr(n, -1);
    vector<int> dist(n, inf);
    dist[v] = 0;
    for (int i = 0; i < n - 1; ++i) {
        bool change = false;
        for (int j = 0; j < edges.size(); ++j) {
            int v = edges[j].from;
            int u = edges[j].to;
            if (dist[v] < inf) {
                if (dist[u] > dist[v] + edges[j].cost) {
                    dist[u] = dist[v] + edges[j].cost;
                    pr[u] = v;
                    change = true;
                }
            }
        }
        if (!change)  break;
    }
    // check path from v to u
    if (dist[u] == inf) {
        // no path
    }
    else {
        vector<int> path;
        for (int cur_v = u; cur_v != -1; cur_v = pr[cur_v]) {
            path.push_back(cur_v);
        }
        reverse(path.begin(), path.end());

        // path is in path vector
    }
}

void ford_bellman_negative_cycles(int v, int n, int m) {
    vector<int> pr(n, -1);
    vector<int> dist(n, inf);
    dist[v] = 0;
    int changed_v = -1;
    for (int i = 0; i < n; ++i) {
        changed_v = -1;
        for (int j = 0; j < edges.size(); ++j) {
            int v = edges[j].from;
            int u = edges[j].to;
            if (dist[v] < inf) {
                if (dist[u] > dist[v] + edges[j].cost) {
                    dist[u] = dist[v] + edges[j].cost;
                    pr[u] = v;
                    changed_v = u;
                }
            }
        }
    }

    if (changed_v == -1) {
        // no negative cycle
    }
    else {
        for (int i = 0; i < n - 1; ++i) {
            changed_v = pr[changed_v];
        }
        // теперь changed_v на отрицательном цикле
        vector<int> path;
        for (int cur_v = changed_v;; cur_v = pr[cur_v]) {
            if (cur_v == changed_v && path.size() > 0) {
                break;
            }
            path.push_back(cur_v);
        }
        reverse(path.begin(), path.end());

        // cycle is in path vector
    }
}

struct S {
    int dist;
    int v;
    int pr;

    bool operator < (const S& a) const {
        return dist < a.dist;
    }
};

int main() {
#ifdef SYSTEM
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int n;
    fill(dist, dist + n, inf);

    dist[0] = 0;
    while (true) {
        pair<int, int> v = { inf, -1 }; // пара расстояние, номер вершины
        for (int i = 0; i < n; ++i) {
            if (!used[i] && dist[i] < v.first) {
                v = { dist[i], i };
            }
        }
        if (v.second == -1 || v.first == inf) {
            break;
        }
        used[v.second] = 1;
        for (int i = 0; i < matr[v.second].size(); ++i) {
            auto u = matr[v.second][i]; // пара величина ребра, номер вершины, в которую ведет ребро
            if (!used[u.second]) {
                if ()
                    pr[u.second] = v.second;
                dist[u.second] = min(dist[u.second], v.first + u.first);
            }
        }
    }

    fill(dist, dist + n, -1);

    int pr[100000];
    fill(pr, pr + n, -1);
    set<pair<int, pair<int, int>>> s;
    s.insert({ 0, {0, -1} });
    while (s.size()) {
        auto v = *s.begin(); // пара расстояние, номер вершины
        s.erase(s.begin());
        while (dist[v.second.first] != -1 && s.size()) {
            v = *s.begin();
            s.erase(s.begin());
        }
        if (s.empty() && dist[v.second.first] != -1) {
            break;
        }
        dist[v.second.first] = v.first;
        pr[v.second.first] = v.second.second
        for (int i = 0; i < matr[v.second.first].size(); ++i) {
            auto u = matr[v.second.first][i]; // пара величина ребра, номер вершины, в которую ведет ребро
            if (dist[u.second.first] == -1) {
                s.insert({ v.first + u.first, {u.second, v.second.first} });
                pr[u.second] = v.second;
            }
        }
    }
}