wevfq

#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

int main() {

    cout << "Enter vertex count: ";
    int n;
    cin >> n;

    const int INF = 1e9;

    //  ввод графа
    cout << "Enter sprase matrix (n*n):\n";
    int **spm = new int*[n];
    for (int i = 0; i < n; ++i) {
        spm[i] = new int[n];
        for (int j = 0; j < n; ++j) {
            cin >> spm[i][j];
            if (spm[i][j] <= 0) {
                spm[i][j] = INF;
            }
            if (i == j) {
                spm[i][j] = 0;
            }
        }
    }

    //  выбор алгоритма
    int algo = -1;
    while (algo != 0 && algo != 1 && algo != 2) {
        cout << "Choose algorithm.\n"
                "0 -> dijkstra\n"
                "1 -> floyd\n"
                "2 -> dijkstra + limit\n"
                "Your choice: ";
        cin >> algo;
    }

    if (algo == 0 || algo == 2) {

        //  дейкстра

        int limit = -1;
        if (algo == 2) {
            while (limit < 0) {
                cout << "Enter limit: ";
                cin >> limit;
            }
        }

        cout << "Enter start vertex number: ";
        int s;
        cin >> s;

        int *path = new int[n], *visited = new int[n], *from = new int[n];
        for (int i = 0; i < n; ++i) {
            path[i] = INF;
            visited[i] = false;
            from[i] = -1;
        }

        path[s] = 0;
        for (int i = 0; i < n; ++i) {
            int cur = -1;
            for (int j = 0; j < n; ++j) {
                if (!visited[j] && (cur == -1 || path[cur] > path[j])) {
                    cur = j;
                }
            }
            if (path[cur] == INF) {
                break;
            }
            visited[cur] = true;
            for (int i = 0; i < n; ++i) {
                if (spm[cur][i] != INF && path[cur] + spm[cur][i] < path[i]) {
                    from[i] = cur;
                    path[i] = path[cur] + spm[cur][i];
                }
            }
        }

        if (algo == 2) {
            cout << "Path list lower than " << limit << ":\n";
            for (int i = 0; i < n; ++i) {
                if (s != i && path[i] < limit) {
                    int tmp = i;
                    while (tmp != s) {
                        cout << tmp << " <- ";
                        tmp = from[tmp];
                    }
                    cout << s << " = " << path[i] << "\n";
                }
            }
        } else {
            for (int i = 0; i < n; ++i) {
                if (path[i] == INF) {
                    cout << "INF ";
                } else {
                    cout << path[i] << " ";
                }
            }
        }

    } else {

        //  флойд

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                for (int l = 0; l < n; ++l) {
                    spm[i][j] = min(spm[i][j], spm[i][l] + spm[l][j]);
                }
            }
        }

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (spm[i][j] >= INF) {
                    cout << "INF ";
                } else {
                    cout << spm[i][j] << " ";
                }
            }
            cout << "\n";
        }

    }

    cout << "\n";

}