#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<conio.h>
#define MAX_CAR 20
#define NOME_FILE "autostrade.txt"

struct n{
	char nome[MAX_CAR];
   struct a *costo;
   struct n *next;
};
                                    //Struttura dati lista di adiacenza
struct a{
	float  prezzo;
   struct a *next;
   struct n *citta;
};

struct l_t{
	char part[MAX_CAR+1];           //Lista che permette la memorizzazione
   char arr[MAX_CAR+1];            //dei risultati
   struct l_t *next;
};

typedef struct n nodo;
typedef struct a arco;
typedef struct l_t lista_temp;

FILE *fp;
nodo *head=NULL;                                 	// Puntatore alla testa della lista delle cittā
float pedaggio_s=0,pedaggio_bs=0xFFFF;           	//Variabili che memorizzano le soluzioni
                                                  	//parziale e definitiva
lista_temp *testa=NULL,*testa_bs=NULL,*app=NULL; 	//Puntatori alla testa delle liste delle solzioni
																 	//e all'ultimo elemento della lista della soluzione parziale
void caricamento(char *);                        	//Carica da file e costruisce la lista di adiacenza
void check_path(char *,char*);                   	//L'utente passa le due cittā e la funzione provvede
																	//a calcolare il percorso con il minor pedaggio
nodo *posizione(char *);                        	//Scandisce la lista delle cittā e trova il puntatore
																	//a quella desiderata
void stampa_risultato(void);                    	//Stampa il percorso migliore
void free_all(void);                               //Libera la memoria
int alloca(nodo*,arco*);                           //Alloca la memoria per la lista delle soluzioni
void dealloca(void);                               //Cancella l'ultimo elemento della lista della soluzione parziale
void copia_lista(void);                            //Copia la lista del percorso una volta trovata una sol.migliore
void stampa_temp(void);

int main(void)
{
	char citta_p[MAX_CAR+1],citta_a[MAX_CAR+1];
   printf("Inserisci la citta da cui vuoi partire: ");
   gets(citta_p);
   printf("Inserisci la citta in cui vuoi arrivare: ");
   gets(citta_a);
   caricamento(NOME_FILE);
   check_path(citta_p,citta_a);
   stampa_risultato();
   getch();                                    		//Attende che l'utente legga il risultato
   free_all();
   return;
}

void caricamento(char *nome_file)
{
   char stream[81];
   char casello1[MAX_CAR+1],casello2[MAX_CAR+1];
   nodo *p2,*p1;
   arco *p1costo;
   float money;
	if((fp=fopen(nome_file,"r"))==NULL)
   {
   	printf("Impossibile aprire il file: ");
      exit(1);
   }
   while((fgets(stream,81,fp))!=NULL)
   {
   	if(head==NULL)
      {
      	head=(nodo*)calloc(1,sizeof(nodo));       //Alloca la memoria
         head->next=(nodo*)calloc(1,sizeof(nodo));
         head->costo=(arco*)calloc(1,sizeof(arco));
         sscanf(stream,"%s %s %f",head->nome,head->next->nome,&head->costo->prezzo);
         head->costo->citta=head->next;           //Inserisce i valori
      }
      else
      {
      	sscanf(stream,"%s %s %f",casello1,casello2,&money);
         p1=posizione(casello1);                  //Cerca la cittā nella lista
         p2=posizione(casello2);
         if(p1->costo==NULL)
         {
         	p1->costo=(arco*)calloc(1,sizeof(arco));
            p1->costo->prezzo=money;             //Alloca e inserisce i valori
            p1->costo->citta=p2;
         }
         else
         {
         	for(p1costo=p1->costo;p1costo->next!=NULL;p1costo=p1costo->next);
            p1costo->next=(arco*)calloc(1,sizeof(arco));
				p1costo->next->prezzo=money;
            p1costo->next->citta=p2;          //Inserisce i valori in coda

			}
      }
      clrscr();
      printf("Ha allocato\n");
      for(p1=head;p1!=NULL;p1=p1->next)
      {
         printf("%s\n",p1->nome);
         for(p1costo=p1->costo;p1costo!=NULL;p1costo=p1costo->next)
      		printf("%s %.2f\n",p1costo->citta->nome,p1costo->prezzo);
      }
      getch();
   }
}
void check_path(char *partenza,char *arrivo)
{
  	nodo *p1;
   arco *p2;

   for(p1=head;p1!=NULL && (strcmpi(p1->nome,partenza)!=0);p1=p1->next);
	if(p1==NULL)
   {
   	printf("Errore: citta' non in archivio\n");
      getch();
      exit(1);
   }
   for(p2=p1->costo;p2!=NULL;p2=p2->next)
   {
      if(!alloca(p1,p2))
      	return;
      stampa_temp();
   	if(strcmpi(p2->citta->nome,arrivo)==0)
      {
      	if(pedaggio_s<pedaggio_bs)
			{
         	copia_lista();
            pedaggio_bs=pedaggio_s;
         }
      }
      else
      {
      	check_path(p2->citta->nome,arrivo);

      }
     pedaggio_s-=p2->prezzo;
     dealloca();
   }
   return;

}
int alloca(nodo *p1,arco *p2)
{
   lista_temp *p0;
   for(p0=testa;p0!=NULL;p0=p0->next)
   	if(strcmp(p0->part,p2->citta->nome)==0)             //Se si incontra un loop scarta la cittā e procede
      	return 0;
   if(testa==NULL)
   {
   	testa=(lista_temp*)calloc(1,sizeof(lista_temp));    //Si alloca la memoria per il primo elemento della soluzione
   	strcpy(testa->part,p1->nome);
   	strcpy(testa->arr,p2->citta->nome);                 //Copia le informazioni
   	app=testa;
	}
	else
   {
		app->next=(lista_temp*)calloc(1,sizeof(lista_temp)); //Si alloca la memoria in coda alla lista delle soluzioni.
      strcpy(app->next->part,p1->nome);
      strcpy(app->next->arr,p2->citta->nome);             //Copia le informazioni
      app=app->next;
   }
   pedaggio_s+=p2->prezzo;
   return 1;
}
void dealloca(void)
{

   lista_temp *p0;
	for(p0=testa;p0!=NULL && p0->next!=app;p0=p0->next);
   if(p0==NULL)
   {
   	free(testa);             //Se l'elemento č in cima alla lista cancella la testa
      testa=NULL;
   }
   else
   {
		free(p0->next);          //Altrimenti cancella l'ultimo
   	p0->next=NULL;
   	app=p0;
   }

}

void stampa_temp(void){
   lista_temp *p0;
   clrscr();
   for(p0=testa;p0!=NULL;p0=p0->next)
   {
   	printf("%s %s\n",p0->part,p0->arr);
   }
   getch();
}

void copia_lista(void)
{
	lista_temp *p0,*p1,*p2=testa_bs;
   while(p2!=NULL)
   {
   	p1=p2;
      p2=p2->next;                       //Elimina la lista contenente la miglior soluzione
      free(p1);
   }
   testa_bs=NULL;
   for(p0=testa;p0!=NULL;p0=p0->next)
   {
   	if(testa_bs==NULL)
      {
      	testa_bs=(lista_temp*)calloc(1,sizeof(lista_temp));   //E'creato il primo elemento
         strcpy(testa_bs->part,p0->part);
         strcpy(testa_bs->arr,p0->arr);
         p1=testa_bs;
      }
      else
      {
      	p1->next=(lista_temp*)calloc(1,sizeof(lista_temp));
         strcpy(p1->next->part,p0->part);                     //Vengono inseriti in coda
         strcpy(p1->next->arr,p0->arr);
         p1=p1->next;
      }
   }
}
nodo *posizione(char *name)
{
	nodo *p0=NULL,*p1;
   for(p1=head;(p1!=NULL) && (strcmpi(p1->nome,name)!=0);p1=p1->next)
   	p0=p1;
   if(p1==NULL)                                //Se esiste la cittā p1 č il puntatore alla cittā
   {
      p0->next=(nodo*)calloc(1,sizeof(nodo));
      p0=p0->next;
      strcpy(p0->nome,name);                   //Altrimenti alloca la memoria e restituisce
		return p0;                               //il puntatore alla cittā appena creata
   }
   return p1;
}
void stampa_risultato(void)
{
	lista_temp *p1;
   /*if(pedaggio_bs==0xFFFF)
   {
   	printf("Percorso non possibile\n");  //Se la soluzione migliore non viene modificata
      getch();                             //non c'č un collegamento tra le due cittā
      exit(1);
   }
   else
   { */
   	for(p1=testa_bs;p1!=NULL;p1=p1->next)
   		printf("%s %s\n",p1->part,p1->arr);     //Stampa risultati
   	printf("%.2f\n",pedaggio_bs);
   //}
}
void free_all(void)
{
	nodo *p0,*p1=head;
   arco *p2,*p3=head->costo;
   lista_temp *p4,*p5=testa_bs,*p6,*p7=testa;
   while(p1!=NULL)
   {
   	while(p3!=NULL)
      {
      	p2=p3;
         p3=p3->next;
         free(p2);                    //Libera la memoria relativa alla lista di adiacenza
      }
      p0=p1;
      p1=p1->next;
      free(p0);
   }
   while(p5!=NULL)
   {
   	p4=p5;
      p5=p5->next;                    //Libera la memoria della soluzione migliore
      free(p4);
   }
   while(p7!=NULL)
   {
   	p6=p7;
      p7=p7->next;                    //Libera memoria della soluzione parziale
      free(p6);
   }
}