#include <iostream>
#include <omp.h>
#include <vector>
#include <fstream>
#include <time.h>
#include <algorithm>

using namespace std;

const int numberOfThreads = 8;

vector < vector <int> > readArrayFromFile(string filename) {
    int m;

    ifstream fin(filename);
    fin >> m;

    vector < vector <int> > matrix(m);

    for (int i = 0; i < m; i++) {
        matrix[i].resize(m);
        for (int j = 0; j < m; j++) {
            fin >> matrix[i][j];
        }
    }
    return matrix;
}

void createMatrixFile(string filename, int m) {
    ofstream fout;
    fout.open(filename);
    fout << m << endl;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            if (i != j) {
                fout << rand() % 9 + 1 << " ";
            }
            else {
                fout << 0 << " ";
            }
        }
        fout << endl;
    }
}

void writeMatrixInFile(string filename, vector <int>&matrix) {
    ofstream fout;
    fout.open(filename);
    fout << matrix.size() << endl;

    for (int i = 0; i < matrix.size(); i++) {
        fout << matrix[i] << endl;
    }
}

vector <int> dijkstra_seq(vector < vector <int> >&graph, int start) {
    vector <int> dist(graph.size());
    bool *used = new bool[graph.size()];

    for (int i = 0; i < graph.size(); ++i) {
        dist[i] = INT_MAX;
        used[i] = false;
    }
    dist[start] = 0;

    for (int j = 0; j < graph.size(); ++j) {
        int v = -1;
        int currentDist = INT_MAX;

        #pragma omp parallel
        {
            int localV = -1;
            int localDist = INT_MAX;

            #pragma omp for nowait
            for (int i = 0; i < graph.size(); ++i) {
                if (!used[i] && localDist > dist[i]) {
                    localV = i;
                    localDist = dist[i];
                }
            }

            #pragma omp critical
            {
                if (localDist < currentDist) {
                    currentDist = localDist;
                    v = localV;
                }
            }
        }

        used[v] = true;

        #pragma omp parallel for
        for (int i = 0; i < graph.size(); ++i) {
            if (!used[i] && graph[v][i] < INT_MAX && graph[v][i] >= 0) {
                dist[i] = min(dist[i], dist[v] + graph[v][i]);
            }
        }
    }

    delete[](used);
    return dist;
}

int main(int argc, char **argv)
{
    createMatrixFile("matrix.txt", 3000);
    vector < vector <int> > matrix = readArrayFromFile("matrix.txt");

    vector <int> result(matrix.size());

    omp_set_num_threads(numberOfThreads);

    time_t start = time(NULL);

    result = dijkstra_seq(matrix, 1);

    cout << "Execution time: " << time(NULL) - start << " sec." << endl;

    writeMatrixInFile("result.txt", result);

    return 0;
}