Floyd–Warshall algorithm

#include <iostream>
#include <vector>
#include <climits>
#include <iomanip>

#define toversh first
#define dist second
int n;
using namespace std;

int main() {
    cin >> n; //считываем кол-во вершин
    int m;
    cin >> m;  // считчывем односторонних связей
    vector<pair<int, int> > graph[n];   // vector - динамическая структура (массив с неопределенной размерностью), pair - структура у которой есть два параметра (first и second)
    int distance[n][n];     //массив в котором будем хранить растояние от i к j вершине
    int vtorayatab[n][n];   //там на лекции была ещё одна таблица, не запомнил её название, вообщем вот она
    /*
     * Cчитываем граф
     *
     * Формат ввода данных: от вершини к верине такая-то цена ребра
     * Пример: 1 2 60
     * От вершини 1 к вершине 2 есть ребро с ценой в 60
     *
     */
    for (int i = 0; i < m; i++) {
        int from, to, price, type;
        cin >> from >> to >> price;// >> type;
        graph[from - 1].push_back(make_pair(to - 1, price));
        //if (type == 0) {
        //  a[to].push_back(make_pair(from, price));
        //}
    }

    /*
     * Подготавливаем все для алгоритма Флойда
     *
     * Все не найденные дистанции помечаем бесконечностью, дистанции в теже точки (из 1 в 1) помечаем 0
     * а так-же отмечаем растояния между известными рёбрами
     *
     */
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            distance[i][j] = INT_MAX;
            vtorayatab[i][j] = j + 1;
            if (i == j) {
                distance[i][j] = 0;
            }
                vtorayatab[i][j] = 0;

        }
        for (int j = 0; j < graph[i].size(); j++) {
            distance[i][graph[i][j].toversh] = graph[i][j].dist;
            vtorayatab[i][graph[i][j].toversh] = graph[i][j].toversh+1;
        }
    }

    //Вывод данных для проверки ввода
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (distance[i][j] == INT_MAX){
                cout << setw(5) << "-";     // setw() - для красивого вывода таблиц   ;)
            }else
                cout << setw(5) <<  distance[i][j];
        }
        cout << "     ";
        for (int j = 0; j < n; j++) {
            cout << setw(3) << vtorayatab[i][j];
        }
        cout << endl;
    }
    cout << endl << endl;

    /*
     * Тут ниже сам алгоритм Флойда
     *
     * Ну на каждой итерации выбираем вершину по которой строим столбец и строку
     * Если есть дистанция в i,j вершину короче то записываем её
     *
     *
     */
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                int m = min(distance[i][j], distance[i][k] + distance[k][j]);
                int tmp = distance[i][j];
                distance[i][j] = m < 0 ? distance[i][j] : m;                            //  ? :   - выражение,   условие ? если истина : если ложь
                vtorayatab[i][j] = tmp != distance[i][j] ? k + 1 : vtorayatab[i][j];
        }


        //Ну я решил выводить полученные данные на каждой итерации, что бы можно было увидеть как меняется таблица с каждой итерацией
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (distance[i][j] == INT_MAX)
                    cout << setw(5) << "-";
                else
                    cout << setw(5) << distance[i][j];
            }
            cout << "     ";
            for (int j = 0; j < n; j++) {
                cout << setw(3) <<  vtorayatab[i][j];
            }
            cout << endl;
        }
        cout << endl << endl;
    }

    return 0;
}


/*
 * Примеры входящих данных для графов
-------------------------------------
6
13
1 2 60
1 6 30
2 3 50
2 4 20
3 2 50
3 4 70
3 6 40
4 3 70
4 5 80
5 4 80
5 6 15
6 3 40
6 5 15
------------------------------------
5
9
1 2 30
1 4 20
2 3 8
2 5 22
2 1 30
3 5 25
3 2 8
4 1 20
5 4 17
 ----------------------------------
 */