#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>
#include <time.h>
#define MAX 50

typedef struct st{
	int costo;
   int km;
} tabella;

FILE *fp;
tabella **matrix;
char **column;
int n_citta,citta_ts,nodo;
int citta_bs,costo_bs,km_bs;
int citta_s,costo_s,km_s;
int *bs,*s,*km,*cst,*visitato;
void burn_matrix(char *);
void check_path(int,int);
int posizione(char*,int);
void alloca(void);
int randomizza(void);
void printa(void);


int main(void)
{
	char nome_file[50],stream[50];
   int euro;
	printf("Inserisci nome file sorgente: ");
   gets(nome_file);
   printf("Inserisci euro a disposizione: ");
   gets(stream);
   euro=atoi(stream);
   burn_matrix(nome_file);
   alloca();
   nodo=randomizza();
   check_path(nodo,euro);
   printa();
   getch();
   free(matrix);
   free(column);
   return 0;
}

int randomizza(void)
{
	randomize();
   return (random(n_citta));
}

void burn_matrix(char* nome)
{
   int i,j;
   int n_raggiunte,cash,kilometres,indice;
   char stream[MAX];
	if((fp=fopen(nome, "r"))==NULL)
   	printf("File %d non trovato\n");
   fgets(stream,51,fp);
   n_citta=atoi(stream);
   matrix=(tabella**)calloc(n_citta,sizeof(tabella*));
   for(i=0;i<n_citta;i++)
   	matrix[i]=(tabella*)calloc(n_citta,sizeof(tabella));
   for(i=0;i<n_citta;i++)
   	for(j=0;j<n_citta;j++)
      {
      	matrix[i][j].costo=-1;
         matrix[i][j].km=-1;
      }
	column=(char**)calloc(n_citta,sizeof(char*));
   for(i=0;i<n_citta;i++)
   {
   	fscanf(fp,"%s\n",stream);
      column[i]=strdup(stream);
   }
   for(i=0;i<n_citta;i++)
   {
   	fscanf(fp,"*%s\n",stream);
      fscanf(fp,"%d\n",&n_raggiunte);
      indice=posizione(stream,n_citta);
      for(j=0;j<n_raggiunte;j++)
      {
      	fscanf(fp,"%s %d %d\n",&stream,&cash,&kilometres);
         matrix[indice][posizione(stream,n_citta)].costo=cash;
         matrix[indice][posizione(stream,n_citta)].km=kilometres;
      }
   }
   fclose(fp);
}

void check_path(int nodo,int euro)
{
	int i;
   char salva,flag;
   visitato[nodo]=1;
   if(euro<=0)
   {
   	citta_ts=citta_s;
      salva=0;
      if(euro<0)
      {
      	citta_ts--;
         if(km_s-km[citta_ts]>km_bs)
         	salva=1;
      }
      else
      {
      	if(km_s>km_bs)
         	salva=1;
      }
      if(salva==1)
      {
      	km_bs=0;
         costo_bs=0;
         for(i=0;i<citta_ts;i++)
         {
         	bs[i]=s[i];
            km_bs+=km[i];
            costo_bs+=cst[i];
         }
         citta_bs=citta_ts;
      }
      return;
   }
   else
   {
   	flag=0;
      for(i=0;i<n_citta;i++)
      	if(matrix[nodo][i].km!=-1 && visitato[i]==0)
         {
         	flag=1;
            visitato[i]=1;
            s[citta_s]=i;
            cst[citta_s]=matrix[nodo][i].costo;
            km[citta_s]=matrix[nodo][i].km;
            citta_s++;
            euro-=matrix[nodo][i].costo;
            km_s+=matrix[nodo][i].km;
            check_path(i,euro);
            visitato[i]=0;
            citta_s--;
            euro+=matrix[nodo][i].costo;
            km_s-=matrix[nodo][i].km;
         }
      if(flag==0)
      {
      	km_bs=0;
         costo_bs=0;
         for(i=0;i<citta_s;i++)
         {
         	bs[i]=s[i];
            km_bs+=km[i];
            costo_bs+=cst[i];
         }
         citta_bs=citta_s;
      }
   }
}
int posizione(char *stream,int n_citta)
{
	int i;
   for(i=0;i<n_citta;i++)
   	if((strcmp(column[i],stream))==0)
      	return i;
	printf("ERRORE\n");
   getch();
   exit(1);
   return -1;
}

void printa(void)
{
	int i;
   printf("Stazione di partenza %s\n",column[nodo]);
   printf("Km da percorrere %d\n",km_bs);
   printf("Costo viaggio %d\n",costo_bs);
   printf("Itinerario citta' visitate: \n");
   for(i=0;i<citta_bs;i++)
   	printf("%s\n", column[bs[i]]);
}
void alloca(void)
{
	bs = (int *)calloc(n_citta,sizeof(int));
	s = (int *)calloc(n_citta,sizeof(int));
	cst = (int *)calloc(n_citta,sizeof(int));
	km = (int *)calloc(n_citta,sizeof(int));
	visitato = (int *)calloc(n_citta,sizeof(int));
}