#include <stdlib.h>
#include <stdio.h>

#define n 5
#define SIZE 5

typedef struct list
{
    int data;
    struct list *next;
} list_t;

list_t *list_push(list_t *list, int data)
{
    list_t *new_elem = malloc(sizeof(list_t));

    new_elem -> next = NULL;
    new_elem -> data = data;

    if (list == NULL)
        return new_elem;

    list_t *ptr = list;
    for (; (ptr -> next) != NULL; ptr = ptr -> next)
        ;

    ptr -> next = new_elem;

    return list;
}

list_t *list_elem_remove(list_t *list)
{
    if (list -> next == NULL)
    {
        free(list);
        return NULL;
    }

    list_t *ptr = list;
    list_t *ptr_next = list -> next;

    free(ptr);
    return ptr_next;
}

void delete_list(list_t *list)
{
    if (list == NULL)
        return;

    for(list_t *ptr = list; ptr != NULL;)
    {
        list_t *tmp = ptr -> next;
        free(ptr);
        ptr = tmp;
    }

    return;
}


int deikstra(int a[n][n], int b[n][n], int begin_index, int finite_index)
{
      int d[SIZE]; // минимальное расстояние
      int v[SIZE]; // посещенные вершины
      int r[SIZE];
      int temp, minindex, min, mini, temp_help;

      //Инициализация вершин и расстояний
      for (int i = 0; i<SIZE; i++)
      {
        d[i] = 10000;
        v[i] = 1;
        r[i] = 10000;
      }
      d[begin_index] = 0;
      r[begin_index] = 0;
      // Шаг алгоритма
      do {
        minindex = 10000;
        min = 10000;
        mini = 10000;
        for (int i = 0; i<SIZE; i++)
        { // Если вершину ещё не обошли и вес меньше min
          if ((v[i] == 1) && (d[i]<min))
          { // Переприсваиваем значения
            min = d[i];
            mini = r[i];
            minindex = i;
          }
        }
        // Добавляем найденный минимальный вес
        // к текущему весу вершины
        // и сравниваем с текущим минимальным весом вершины
        if (minindex != 10000)
        {
          for (int i = 0; i<SIZE; i++)
          {
            if (a[minindex][i] > 0)
            {
              temp = min + (a[minindex][i] + b[minindex][i]);
              temp_help = mini + a[minindex][i];
              if (temp < d[i])
              {
                d[i] = temp;
                r[i] = temp_help;
              }
            }
          }
          v[minindex] = 0;
        }
      } while (minindex < 10000);

      // Вывод кратчайших расстояний до вершин
        printf(" %d ", r[finite_index]);

        for (int i = 0; i < n; i++)
            printf(" %d ", r[i]);

        // Восстановление пути
          int ver[SIZE]; // массив посещенных вершин
          int end = SIZE - 1; // индекс конечной вершины = 5 - 1
          ver[0] = end + 1; // начальный элемент - конечная вершина
          int k = 1; // индекс предыдущей вершины
          int weight = r[end]; // вес конечной вершины

          while (end != begin_index) // пока не дошли до начальной вершины
          {
            for (int i = 0; i < SIZE; i++) // просматриваем все вершины
              {//printf("%d Ok", i);
                if (a[end][i] != 0)   // если связь есть
                {
                  int temp = weight - a[end][i]; // определяем вес пути из предыдущей вершины

                  if (temp == r[i]) // если вес совпал с рассчитанным
                  {                   // значит из этой вершины и был переход
                    weight = temp; // сохраняем новый вес
                    end = i;       // сохраняем предыдущую вершину

                    ver[k] = i + 1; // и записываем ее в массив
                    k++;
                  }
                }
            }
          }

          // Вывод пути (начальная вершина оказалась в конце массива из k элементов)
          printf("\nВывод кратчайшего пути\n");
          for (int i = k - 1; i >= 0; i--)
            printf("%3d ", ver[i]);


    return 0;
}


int main()
{

    int matrix_way[n][n];
    int matrix_cost[n][n];
    //int res_matrix[n][n];

    int begin_index;
    int finite_index;

    FILE *f = fopen("matrix_way.txt", "r");

    if (!f)
        return -1;

    for (int i = 0; i < n && !feof(f); i++)
        for (int j = 0; j < n && !feof(f); j++)
            fscanf(f, "%d", &matrix_way[i][j]);

    FILE *file = fopen("matrix_cost.txt", "r");

    if (!file)
        return -1;

    for (int i = 0; i < n && !feof(file); i++)
        for (int j = 0; j < n && !feof(file); j++)
            fscanf(file, "%d", &matrix_cost[i][j]);

    if (scanf("%d", &begin_index) != 1)
        return -1;
    if (scanf("%d", &finite_index) != 1)
        return -1;

    //check(matrix_way);
    deikstra(matrix_way, matrix_cost, begin_index - 1, finite_index - 1);
    //find_matrix()

    fclose(f);
    fclose(file);

    return 0;
}