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

/*
	treni.c
*/

typedef struct T {
	int	costo;
	int	Km;
} TRAINTABLE;

TRAINTABLE	**graph;        /* Matrice di adiacenza */
int	n_graph;	/* Numero di nodi nel grafo */
char	**nomi;		/* Nomi dei nodi */

int	n_bs;		/* Soluzione ottima */
int	costo_bs;
int	km_bs;
int	*bs;

int	n_s;		/* Soluzione corrente */
int     costo_s;
int	km_s;
int	*s;
int	*km;		/* Km percorsi in ogni tratta della sol. corrente */
int	*cst;		/* costo di ogni tratta della sol. corrente */

int	*visitato;

int	get_index( char *v )
{
	int	i;

	for( i = 0; i < n_graph; i++ )
		if( strcmp( v, nomi[i]) == 0 )
			return( i );

	exit( 1 );
	return( -1 );
}

void	read_graph( char *s )
{
	FILE	*fp;
	int	i, j;

	int	n_adj;
	int	n_v;
	int	c;
	int	km;
	char	tmp[80];

	/*
		Apro il file, se esiste
	*/
	if( (fp = fopen( s, "r" )) == NULL )
	{
		printf( "Impossibile aprire %s\n", s );
		exit( 1 );
	}

	/*
		Leggo il numero di nodi nel grafo
	*/
	fscanf( fp, "%d\n", &n_graph );

	/*
		Alloco la memoria per la matrice
	*/
	graph = (TRAINTABLE **)malloc( sizeof( TRAINTABLE * )*n_graph );
	if( graph == NULL )
	{
		printf( "Impossibile allocare la memoria\n" );
		exit( 1 );
	}

	for( i = 0; i < n_graph; i++ )
	{
		graph[i] = (TRAINTABLE *)malloc( sizeof( TRAINTABLE )*n_graph );
		if( graph[i] == NULL )
		{
			printf( "Impossibile allocare la memoria\n" );
			exit( 1 );
		}
	}

	/*
		Inizializzo la matrice
	*/
	for( i = 0; i < n_graph; i++ )
	{
		for( j = 0; j < n_graph; j++ )
		{
			graph[i][j].costo = -1;
			graph[i][j].Km = -1;
		}
	}

	/*
		Alloco memoria per i nomi dei nodi
	*/
	nomi = (char **)malloc( sizeof( char *)*n_graph );
	if( nomi == NULL )
	{
		printf( "Impossibile allocare la memoria\n" );
		exit( 1 );
	}
	for( i = 0; i < n_graph; i++ )
	{
		fscanf( fp, "%s\n", tmp );
		nomi[i] = (char *)strdup( tmp );
	}

	/*
		Leggiamo il grafo
	*/
	for( i = 0; i < n_graph; i++ )
	{
		fscanf( fp, "*%s\n", tmp );
		fscanf( fp, "%d\n", &n_adj );

		n_v = get_index( tmp );
		for( j = 0; j < n_adj; j++ )
		{
			fscanf( fp, "%s %d %d\n", tmp, &c, &km );
			graph[n_v][get_index(tmp)].costo = c;
			graph[n_v][get_index(tmp)].Km = km;
		}

	}

	fclose( fp );
}

void	print_graph( void )
{
	int	i, j;

	for( i = 0; i < n_graph; i++ )
	{
		printf( "%3s: ", nomi[i] );
		for( j = 0; j < n_graph; j++ )
			if( graph[i][j].Km != -1 )
				printf( "%4s(%4d, %4d) ", nomi[j],
							  graph[i][j].costo,
							  graph[i][j].Km );
		printf( "\n" );
	}
}

void	visita( int node, int euro )
{
	int	i;
	int	tmp_n_s;
	char	salva;
	char	flag;

	if( euro <= 0 )		/* Ho finito i soldi */
	{
		tmp_n_s = n_s;
		salva = 0;

		if( euro < 0 )
		{
			/* Ho speso pi— di quanto posso spendere */
			/* Tolgo l'ultima citt… visitata */
			tmp_n_s--;
			if( km_s-km[tmp_n_s] > 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 < tmp_n_s; i++ )
			{
				bs[i] = s[i];
				km_bs += km[i];
				costo_bs += cst[i];
			}
			n_bs = tmp_n_s;
		}

		return;
	}
	else
	{
		flag = 0;
		for( i = 0; i < n_graph; i++ )
			if( graph[node][i].Km != -1 && visitato[i] == 0 )
			{
				/* Aggiungo il nodo alla soluzione corrente
				   e riduco la somma disponibile in euro */
				flag = 1;
				visitato[i] = 1;
				s[n_s] = i;
				cst[n_s] = graph[node][i].costo;
				km[n_s] = graph[node][i].Km;
				n_s++;

				euro -= graph[node][i].costo;
				km_s += graph[node][i].Km;

				visita( i, euro );

				/* Backtrack */

				visitato[i] = 0;
				n_s--;

				euro += graph[node][i].costo;
				km_s -= graph[node][i].Km;
			}
	}

	if( flag == 0 )
	{
		/* Non sono riuscito ad aggiungere nulla e quindi
		   verifico se ho trovato una soluzione ottima senza
		   finire i soldi */
		if( km_s > km_bs )
		{
			km_bs = 0;
			costo_bs = 0;
			for( i = 0; i < n_s; i++ )
			{
				bs[i] = s[i];
				km_bs += km[i];
				costo_bs += cst[i];
			}
			n_bs = n_s;
		}

	}
}

int	main( int argc, char **argv )
{
	int	i;
	int	euro;

	if( argc < 3 )
	{
		printf( "Uso: treni nomegrafo soldi\n" );
		return( 1 );
	}

	read_graph( argv[1] );
	print_graph();

	sscanf( argv[2], "%d", &euro );

	n_bs = 0;
	km_bs = 0;
	costo_bs = 0;

	n_s = 0;

	bs = (int *)malloc( sizeof( int )*n_graph );
	s = (int *)malloc( sizeof( int )*n_graph );
	cst = (int *)malloc( sizeof( int )*n_graph );
	km = (int *)malloc( sizeof( int )*n_graph );
	visitato = (int *)malloc( sizeof( int )*n_graph );
	if( s == NULL || bs == NULL || visitato == NULL ||
	    cst == NULL || km == NULL )
	{
		printf( "Impossibile allocare la memoria\n" );
		exit( 1 );
	}


	for( i = 0; i < n_graph; i++ )
		visitato[i] = 0;

	visita( 0, euro );

	printf( "Il percorso ottimo Š: " );
	for( i = 0; i < n_bs;i++ )
		printf( "%s, ", nomi[bs[i]] );
	printf( "\nKm percorsi = %d\n", km_bs );
	printf( "Costo = %d\n", costo_bs );

	free( nomi );
	free( s );
	free( bs );
	for( i = 0; i < n_graph; i++ )
		free( graph[i] );
	free( graph );
	free( cst );
	free( km );

	return( 0 );
}