#include <clocale>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <limits>
#include <vector>
#include <windows.h>

using namespace std;

const int V = 4;
ofstream  file("C:\\Users\\Ilya\\Desktop\\Alg_Dijkstra.txt"); //Запись в файл

//структура для ребра
struct VERTEX {
    double depTime;
    double travelTime;
    double arrTime;
};

//алгоритм Дейкстры
double Dijkstra(VERTEX vertex[V][V], int st)
{
    double deadline = 2;
    double distance[V];
    double dis[V];
    double arr[V];
    double dep[V];
    double result[V];
    double d_max = 0;
    int    count, index = 0, i, u, m = st + 1;
    bool   visited[V];

    static const double INF = std::numeric_limits<double>::infinity();
    for (i = 0; i < V; i++) {
        distance[i] = INF;
        dis[i]      = INF;
        arr[i]      = INF;
        dep[i]      = INF;
        visited[i]  = false;
    }
    distance[st] = 0;

    //Первый шаг алгоритма
    double min = INF;
    for (i = 0; i < V; i++) {
        if (!visited[i] && distance[i] <= min) {
            min   = distance[i];
            index = i;
        }
    }
    u          = index;
    visited[u] = true;

    for (i = 0; i < V; i++) {
        if (!visited[i] && vertex[u][i].travelTime > 0 && distance[u] < INF &&
            distance[u] + vertex[u][i].travelTime < INF) {

            distance[i] = vertex[u][i].travelTime;
            arr[i]      = vertex[u][i].arrTime;
            dep[i]      = vertex[u][i].depTime;
        }
    }
    //-----------------------------------------—
    // Второй шаг алгоритма
    for (count = 1; count < V - 1; count++) {
        double min = INF;
        for (i = 0; i < V; i++) {
            if (!visited[i] && distance[i] <= min) {
                min   = distance[i];
                index = i;
            }
        }
        u          = index;
        visited[u] = true;
        for (i = 0; i < V; i++) {
            if (!visited[i] && vertex[u][i].travelTime > 0 && distance[u] < INF &&
                distance[u] + (vertex[u][i].depTime - arr[u]) + vertex[u][i].travelTime < distance[i] &&
                vertex[u][i].depTime - arr[u] >= 0.5) {

                distance[i] = distance[u] + (vertex[u][i].depTime - arr[u]) + vertex[u][i].travelTime;
                arr[i]      = vertex[u][i].arrTime;
                dep[i]      = vertex[u][i].depTime;
            }
        }
    }


    // ОПТИМАЛЬНЫЙ ПО ВРЕМЕНИ
    for (i = 0; i < V; i++) {
        arr[i]     = 0;
        dep[i]     = 0;
        visited[i] = false;
        dis[i]     = INF;
    }
    dis[st] = 0;

    //Первый шаг алгоритма

    for (i = 0; i < V; i++) {
        if (!visited[i] && dis[i] <= min) {
            min   = dis[i];
            index = i;
        }
    }
    u          = index;
    visited[u] = true;
    for (i = 0; i < V; i++) {
        if (!visited[i] && vertex[u][i].travelTime > 0 && dis[u] < INF && dis[u] + vertex[u][i].travelTime < dis[i]) {
            dis[i] = dis[u] + vertex[u][i].travelTime;
            arr[i] = vertex[u][i].arrTime;
            dep[i] = vertex[u][i].depTime;
        }
    }
    //-----------------------------------------—
    // Второй шаг алгоритма
    for (count = 1; count < V - 1; count++) {
        double min = INF;
        for (i = 0; i < V; i++) {
            if (!visited[i] && dis[i] <= min) {
                min   = dis[i];
                index = i;
                // cout<<min<<endl;
            }
        }
        u          = index;
        visited[u] = true;
        for (i = 0; i < V; i++) {
            if (!visited[i] && vertex[u][i].travelTime > 0 && dis[u] < INF && vertex[u][i].depTime - arr[u] >= 0.5 &&
                vertex[u][i].depTime - arr[u] <= deadline) {
                dis[i] = dis[u] + (vertex[u][i].depTime - arr[u]) + vertex[u][i].travelTime;
                arr[i] = vertex[u][i].arrTime;
                dep[i] = vertex[u][i].depTime;
            }
        }
    }

    for (i = 0; i < V; i++) {
        result[i] = distance[i];
        if (dis[i] <= distance[i]) {
            result[i] = dis[i];
        }
    }


    // ВЫВОД АЛГОРТИМА
    file << "Distance from the initial vertex to the others:\t\n";
    for (i = 0; i < V; i++) {
        if (result[i] > d_max) {
            d_max = result[i];
        }
        file << m << " -> " << i + 1 << " = " << result[i] << endl;
    }
    file << "Maximum distance:= " << d_max << endl;
    return 0;
}
//главная функция
int main()
{
    int    start;
    VERTEX vertex[V][V] = {{{0, 0, 0}, {5, 3, 8}, {4, 4.5, 8.5}, {0, 0, 0}},
                           {{16, 2.5, 18.5}, {0, 0, 0}, {6, 2.5, 8.5}, {0, 0, 0}},
                           {{13, 6, 18}, {12, 2, 14}, {0, 0, 0}, {9.5, 2, 11.5}},
                           {{0, 0, 0}, {0, 0, 0}, {8, 3, 11}, {0, 0, 0}}};
    for (start = 0; start < V; start++) {
        file << "First vertex " << start << endl;
        Dijkstra(vertex, start);
    }
    system("pause");
    return 0;
}