Bellman Ford, Levet

https://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Левита

#include<iostream>
#include<vector>
#include<queue>

#define mp(X, Y)  make_pair(X, Y)

using namespace std;

int main() {
    int N = 0, M = 0;
    cin >> N >> M;
    N++;
    vector< vector< pair<int, int> > > G(N);
    vector<int> R(N, 30000);
    for(int i = 0; i < M; i++) {
        int from =0, to = 0, w = 0;
        cin >> from >> to >> w;
        G[from].push_back(mp(to, w));
    }
    R[1] = 0;
    queue<int> q;
    q.push(1);
    while(!q.empty()){
        int from = q.front();
        q.pop();
        for(int i = 0; i < G[from].size(); i++){
            int to = G[from][i].first;
            int w = G[from][i].second;
            if (R[from] + w < R[to]) {
                q.push(to);
                R[to] = R[from] + w;
            }
        }
    }
    for (int i = 1; i < R.size(); i++){
        cout << R[i] << " ";
    }
    system("pause");
    return 0;
}


#include<iostream>
#include<vector>
#include<deque>

#define mp(X, Y)  make_pair(X, Y)

using namespace std;

int main() {
    int N = 0, M = 0;
    cin >> N >> M;
    N++;
    vector< vector< pair<int, int> > > G(N);
    vector<int> R(N, 30000);
    for(int i = 0; i < M; i++) {
        int from =0, to = 0, w = 0;
        cin >> from >> to >> w;
        G[from].push_back(mp(to, w));
    }
    R[1] = 0;
    deque<int> q;
    q.push_back(1);
    while(!q.empty()){
        int from = q.front();
        q.pop_front();
        for(int i = 0; i < G[from].size(); i++){
            int to = G[from][i].first;
            int w = G[from][i].second;
            if (R[from] + w < R[to]) {
                if(R[to] == 30000)
                    q.push_back(to);
                else
                    q.push_front(to);
                R[to] = R[from] + w;
            }
        }
    }
    for (int i = 1; i < R.size(); i++){
        cout << R[i] << " ";
    }
    system("pause");
    return 0;
}


#include<iostream>
#include<vector>
#include<deque>
#include<queue>
#define mp(X, Y)  make_pair(X, Y)

using namespace std;

int main() {
    int N = 0, M = 0;
    cin >> N >> M;
    N++;
    vector< vector< pair<int, int> > > G(N);
    vector<int> R(N, 30000); // расстояния
    for(int i = 0; i < M; i++) {
        int from =0, to = 0, w = 0;
        cin >> from >> to >> w;
        G[from].push_back(mp(to, w));
    }
    // Инициализация, строим дерево от вершины 1
    R[1] = 0;
    queue<int> q1, q2; // q1 - основная, q2 - срочной
    q1.push(1);
    while(!q1.empty() || !q2.empty()){
        int from = 0;
        if (!q2.empty()){
            from = q2.front();
            q2.pop();
        } else {
            from = q1.front();
            q1.pop();
        }
        for(int i = 0; i < G[from].size(); i++){ // просмотр инцидентных вершин
            int to = G[from][i].first; // инцидентная вершина
            int w = G[from][i].second; // вес дуги
            if (R[from] + w < R[to]) { // проверяем, можем ли улучьшить путь
                if(R[to] == 30000){
                    q1.push(to);
                } else {
                    q2.push(to);
                }
                R[to] = R[from] + w; // улучшаем
            }
        }
    }
    for (int i = 1; i < R.size(); i++){
        cout << R[i] << " ";
    }
    system("pause");
    return 0;
}