#include <iostream>
#include <stdio.h>
#include <vector>
#include <limits.h>
#include <algorithm>
using namespace std;
int m_size;
int start_index;
struct point
{
    int mark, mark_max=-1;
    int index;
    vector <point *> attainable_points;
    bool stat = false;
};
void FillTriangleMatrix(int **adj, int **arr, int **tmp);
vector <int> triangle_values_order;
bool AllStatic(point **arr);
point **p_array;
point * Min(point **arr);
int Max(int i, int **arr,int start);
int EmptyColumnIndex(int **arr);
void AdjacencyMatrixFill(int** matrix);
void MatrixShow(int **matrix,bool triangle);
void MinDistance(int** matrix, int start);
void MaxDistance (int **arr, int start);
int main()
{
    printf ("Enter the size of matrix NxN: ");
    scanf ("%d", &m_size);

    int **adj_matrix = new int*[m_size];
    for (int i = 0; i < m_size; i++)
        adj_matrix[i] = new int [m_size];

    int **triangle_matrix = new int*[m_size];
    for (int i = 0; i < m_size; i++)
        triangle_matrix[i] = new int [m_size];

    int **tmp = new int*[m_size];
    for (int i = 0; i < m_size; i++)
        tmp[i] = new int [m_size];

    printf ("Enter the start index: ");
    scanf("%d", &start_index);
    AdjacencyMatrixFill(adj_matrix);
    MatrixShow(adj_matrix, false);
    p_array = new point* [m_size]; //array of points
    MinDistance(adj_matrix, start_index);
    for (int i=0; i<m_size; i++)
    {
        printf("%d -> %d)",start_index,i);
        if(p_array[i]->mark!=INT_MAX) printf("%d\n", p_array[i]->mark);
        else printf("SUCH WAY DOESN'T EXIST\n");
    }
    FillTriangleMatrix(adj_matrix, triangle_matrix, tmp);
    printf ("\nTRIANGLE MATRIX\n");
    MatrixShow(triangle_matrix, true);
    MaxDistance(triangle_matrix, start_index);
    for (int i=0; i<m_size; i++)
    {
        if (p_array[i]->mark_max==-1) printf ("%d) SUCH WAY DOESN'T EXIST\n", i);
        else printf ("%d) %d\n", i, p_array[i]->mark_max);
    }
}

void AdjacencyMatrixFill(int **matrix)
{
    printf("\nENTER ADJACENCY MATRIX\n");
    for(int i = 0; i < m_size; ++i)
        for(int j = 0; j < m_size; ++j)
        {
            scanf("%d", &matrix[i][j]);
            if (matrix[i][j]== 0)
                matrix[i][j] = INT_MAX;
        }
    printf("\nADJACENCY MATRIX CREATED\n");
}
void MatrixShow(int **matrix, bool triangle)
{

    printf("\t");
    for (int i=0; i<m_size; i++)
    {
        if (triangle) printf("\tx%d", triangle_values_order[i]);
        else printf("\tx%d", i);
    }
    printf("\n");
    for (int i = 0; i < m_size; ++i, printf("\n"))
    {
        if(triangle) printf("\tx%d", triangle_values_order[i]);
        else printf("\tx%d", i);
        for(int j = 0; j < m_size; ++j)
        {
            if (matrix[i][j]==0 || matrix[i][j]==INT_MAX)
                printf("\t-");
            else
                printf("\t%d ", matrix[i][j]);
        }
    }
}
void MinDistance(int** matrix, int start)
{
    for(int i = 0; i < m_size; i++)
    {
        point* p = new point;
        if(i==start) p->mark = 0;
        else p->mark = INT_MAX;
        p->index = i;
        p_array[i] = p;
    }

    for (int i = 0; i < m_size; i++)
    {
        for(int j = 0; j < m_size; j++)
            if (matrix[i][j] != INT_MAX && i != j)
            {
                p_array[i]->attainable_points.push_back(p_array[j]);
            }
    }

    point * current = p_array[start];
    while (!AllStatic(p_array))
    {
        for (int j = 0; j < current->attainable_points.size(); j++)
        {
            double value  = current->mark + matrix[current->index][current->attainable_points[j]->index];
            if ( value < current->attainable_points[j]->mark)
            {
                current->attainable_points[j]->mark = value;
            }
        }
        current->stat = true;
        current = Min(p_array);
        if (current->mark==INT_MAX)
            break;
    }
}

point * Min(point **arr)
{
    point *p_min;
    for (int i=0; i<m_size; i++)
    {
        if (!arr[i]->stat)
        {
            p_min = arr[i];
            break;
        }
    }
    for (int i = p_min->index; i < m_size; i++)
    {
        if(arr[i]->mark < p_min->mark && arr[i]->stat==false)
            p_min = arr[i];
    }
    return p_min;
}

bool AllStatic(point **arr)
{
    for (int i=0; i<m_size; i++)
        if(arr[i]->stat==false) return false;
    return true;
}

void FillTriangleMatrix(int **adj, int **arr, int **tmp)
{

    for (int i=0; i<m_size; i++)
        for (int j=0; j<m_size; j++)
            tmp[i][j] = adj[i][j];
    int index = EmptyColumnIndex(tmp);
    triangle_values_order.push_back(index);
    int k,p;
    k=0;
    for (int i = 0; i<m_size; i++)
    {
        p = 0;
        for (int j = 0; j<m_size; j++)
        {
            arr[i][j] = adj[triangle_values_order[k]][triangle_values_order[p]];
            p++;
        }
        k++;
    }
}

int EmptyColumnIndex(int **arr)
{
    int index;
    while (triangle_values_order.size()!=m_size)
    {
        for(int i=0; i<m_size; i++)
        {
            int cnt = 0;
            std::vector<int>::iterator it;
            it = find (triangle_values_order.begin(), triangle_values_order.end(), i);
            if (it == triangle_values_order.end())
            {
                for(int j=0; j<m_size; j++)
                {
                    if(arr[j][i]==INT_MAX || arr[j][i]==0)
                        cnt++;
                }
                if (cnt==m_size)
                {
                    triangle_values_order.push_back(i);
                    index = i;
                    for (int j=0; j<m_size; j++)
                    {
                        arr[index][j] = 0;
                        arr[j][index] = 0;
                    }
                }
            }
        }
    }
}

void MaxDistance (int **arr, int start)
{
    p_array[start]->mark_max = 0;
    int i = triangle_values_order[start];
    do
    {
        int status = Max(i, arr,start);
        if (status) p_array[triangle_values_order[i]]->mark_max = status;
        i++;
    }
    while (i<m_size);
}

int Max(int i, int **arr, int start)
{
    int mx = 0;
    int value, j = 0;
    do
    {
        if(arr[j][i]!= INT_MAX && arr[j][i]!=0 && p_array[triangle_values_order[j]]->mark_max!=-1)
        {
            value = arr[j][i] + p_array[triangle_values_order[j]]->mark_max;
            if (mx<value) mx = value;
        }
            j++;

    }
    while (j<m_size);
    return mx;
}

/*
0 5 8 7 18 0
0 0 11 0 0 0
0 0 0 0 0 17
0 10 12 0 6 0
0 7 8 0 0 11
0 0 0 0 0 0
*/

/*
0 6 11 5 0 0
0 0 0 0 7 2
0 5 0 0 6 0
0 0 0 0 4 5
0 0 0 0 0 7
0 0 0 0 0 0
*/