va32

#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;
            }
        }
    }

    while (true) {

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

        if (algo == 3) {
            break;
        }

        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] << " ";
                    }
                }
            }

            delete[] path;
            delete[] visited;
            delete[] from;

        } else {

            //  флойд

            int **spm_tmp = new int*[n];
            for (int i = 0; i < n; ++i) {
                spm_tmp[i] = new int[n];
                for (int j = 0; j < n; ++j) {
                    spm_tmp[i][j] = spm[i][j];
                }
            }

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

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

            for (int i = 0; i < n; ++i) {
                delete[] spm_tmp[i];
            }
            delete[] spm_tmp;

        }

        cout << "\n";

    }

}