#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; // Больше путей нет 
}