#include <stdio.h>
#include <string.h>
#include "stdlib.h"
#include "conio.h"
#include "math.h"
#include <iostream>
using namespace std;
const int inf = 999;

const int vertex = 7;

int M[vertex][vertex] =
{
{ 0 , 1 , inf , 3  , inf,inf,2   },
{ 1,0,4,3,inf,6,inf },
{ inf,4,0,1,inf,2,2 },
{ 3,3,1,0,2,inf,inf},
{ inf,inf,inf,2,0,2,4},
{inf,6,2,inf,2,0,inf },
{2,inf,2,inf,4,inf,0 }
};

int W[vertex] = {0};
int Dw[vertex] = {0};

void print(int M[][vertex], int R[][vertex], int S[vertex]) // вывод
{
    int step = 0;
    printf("\nM:");

    for (int i = 0; i < vertex; i++)
    {
        printf("\n");
         for (int j = 0; j < vertex; j++)
            {
                if (M[i][j] == inf)
                    printf("\t -");
                        else
                         printf("\t%d", M[i][j]);
        }
        printf("\n");
    }

    printf("R:\n\n");
    printf("\tS");
    printf("\t\t\t\tw");
    printf("\tD(w)");

    for (int i = 0;i < vertex; i++)
    printf("\tD(%d)",i);

    for (int i = 0; i < vertex; i++)
    {
        printf("\n");
        printf("(");

      for (int i = 0; i <= step; i++)
      {
        if(S[i] ||  i==0)
            if(i != step)
                printf("%d,", S[i]);
            else
                printf("%d", S[i]);
      }

        printf(")\t");
        printf("\t\t");

      if (step <= vertex / 2)
        printf("\t");

      if(W[i])
        printf("\t%2d",W[i]);
      else
        printf("\t -");

      if(Dw[i])
        printf("\t%2d",Dw[i]);
      else
        printf("\t -");

      for (int j = 0; j < vertex ; j++)
      {
            if (R[i][j] == 0 || R[i][j] == inf)
                printf("\t -");
            else
                printf("\t%2d", R[i][j]);
      }
        printf("\n");
        step++;
    }


}

int getMinimal(int A, int B) // возвращает минимум
{
    if (A <= B)
        return A;
    else
        return B;
}

bool entryVertex(int *Array, int toFind) // смотрит, взяли ли мы уже эту вершину
{
    for (int i = 0; i < vertex; i++)
    {
        if (toFind == Array[i])
            return true;
    }
    return false;
}

int getMinimalLine(int R[][vertex], int *D, int k) // ищет минимальное значение в строке
{
    int minimal = inf;
    int minimalIndex;

    for (int i = 0; i < vertex; i++)
    {
        if (entryVertex(D, i) == false)
          if (R[k][i] <= minimal)
          {
            minimal = R[k][i];
            minimalIndex = i;
          }
    }
    return minimalIndex;
}

int main()
{

    int R[vertex][vertex];
    int D[vertex];

    int s = 0, w = 0, k = 0, d = 0, minimalIndex;

    for (int i = 0; i < vertex; i++) // заполняем все нолями
        for (int j = 0; j < vertex; j++)
            R[i][j] = 0;

    for (int i = 0; i < vertex+1; i++) // это путь, по-моему
        D[i] = 0;

    for (int j = 0; j < vertex; j++)
        R[k][j] = M[k][j];


    minimalIndex = getMinimalLine(R, D, k); // ищем минимальное значение в строке, получаем индекс

    s = R[k][minimalIndex]; // выбираем элемент
    w = minimalIndex; //  запоминаем его иднекс
    D[d] = minimalIndex; // вносим его в наш путь
    d++; // переходим на следующий шаг

    for(k=1;k<vertex;k++) // для всех следующих шагов
    {
        W[k] = w; // добавляемая вершина
        Dw[k] = s; //

        for (int j = 1; j < vertex; j++)
        {
            if (entryVertex(D, j) == false) // если еще не брали вершину
            {
                R[k][j] = getMinimal(R[k - 1][j], Dw[k] + M[W[k]][j]); // добавляем ее, считаем общую стоимость пути (по-моему, хз)
                minimalIndex = getMinimalLine(R, D, k); // ищем минимальный в строчке
            }
        }
        s = R[k][minimalIndex]; // выбираем элемент
        w = minimalIndex; // запоминаем его индекс
        D[d] = minimalIndex; // добавляем в путь
        d++; // следующий шаг
    }
    print(M, R, D);

    return 0;
}