#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct Arc
{
	int from;     //индекс исходящей вершины
	int to;       //индекс входящей вершины
    double weight;
} ;
struct Way
{
    bool exist;       //существование пути
    double sumWeight;  //суммарный вес
    int refPrev;      //индекс узла, через который проходит путь
};
struct Graph
{
	int numNodes;      //число вершин
	int numArcs;       //число дуг
	struct Arc *arcs;         //указатель на массив дуг

	struct Way *pMinWay;        //Адрес первого элемента массива и инфрмацией о минималном пути от start до finish
	                    //pMinWay[i] минимальная стоимость из i в start
};

void FindWay(struct Graph g, int, int);

int main(){
    FILE *edge;
    int i, edge_number;
    struct edge_struct *edge_items;
    struct edge_item *items;
    struct Graph *g;
    edge = fopen("edge.txt", "r");
    if (!edge)
        return 1;
    fscanf(edge, "%d", &edge_number);
    g = calloc(edge_number, sizeof(*g));
    for (i = 0; i < edge_number; ++i)
        fscanf(edge, "%d%d%d%d", &g[i].numNodes, &g[i].numArcs);
    fclose(edge);
        //ForStep(struct edge_struct *edge_items, struct edge_item *items, int edge_number);
    free(edge_items);
    return 0;
}

// Шаг по дуге ixArc к вершине, смежной с вершиной transit
void ForStep(struct Graph g, int ixArc)
{
     int transit = g.arcs[ ixArc ].from; // Транзитная вершина
     int step    = g.arcs[ ixArc ].to; // Смежная вершина
     int finish  = g.arcs[ ixArc ].from; // Транзитная вершина ////////////

     // Вычисляем новый суммарный вес пути через transit до step
     double newSumWeight = g.pMinWay[ transit ].sumWeight + g.arcs[ ixArc ].weight;

     if( !g.pMinWay[ step ].exist )
     {
     // Эта вершина раскрыта впервые
     g.pMinWay[ step ].exist = true;

     g.pMinWay[ step ].sumWeight = newSumWeight;

     g.pMinWay[ step ].refPrev = transit;
      FindWay( g, step, finish );
     }
     else
     {
         // Эта вершина раньше встречалась
         if( g.pMinWay[ step ].sumWeight > newSumWeight )
         {
          // Новый путь короче
         g.pMinWay[ step ].sumWeight = newSumWeight;
         g.pMinWay[ step].refPrev = transit;
         FindWay( g, step, finish );               //////////////////////////
         }
         // Здесь: прежний путь лучше, то есть дальше искать
         // нечего, поэтому игнорируем этот шаг
     }
}

// Поиск кратчайшего пути от transit до finish
void FindWay(struct Graph g, int transit, int finish )
{
   int ixArc;
   if( transit == finish ) return;

   // Находим дуги, исходящие из transit и
   // выполняем шаг по каждой найденной дуге
   for( ixArc=0; ixArc < g.numArcs; ixArc++ )
   {
   // Рассматриваем случай орграфа, поэтому анализируем
   // только исходящую вершину дуги
   if( g.arcs[ ixArc ].from == transit )
   ForStep( g, ixArc );
  }
  return; // Больше путей нет
}