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

/*
	Matrice di adiacenza di un grafo orientato pesato, con pesi
	non negativi.
	L'elemento graph[i][j] = -1 se non esiste l'arco da i a j,
	altrimenti e` uguale al peso dell'arco.
	Il file dati ha il seguente formato:
	Numero nodi
	nome nodo 1
	nome nodo 2
	.
	.
	.
	nomde nodo n
	*nome nodo 1
	numero nodi adiacenti
	nodo adiacente 1	costo
	nodo adiancente 2	costo
	.
	.
	.

	Per esempio:
	8
	I
	A
	B
	C
	D
	E
	F
	L
	*I
	1
	A 1
	*A
	2
	B 2
	C 4
	*B
	2
	A 2
	E 1
	*C
	2
	A 1
	D 2
	*D
	3
	C 2
	E 4
	F 3
	*E
	3
	B 1
	D 4
	L 2
	*F
	2
	D 3
	E 5
	*L
	2
	E 2
	F 5
*/
int	**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	*bs;

int	n_s;		/* Soluzione corrente */
int     costo_s;
int	*s;

char	*visitato;

int	get_index( char v )
{
	int	i;

	for( i = 0; i < n_graph; i++ )
		if( v == nomi[i] )
			return( i );
	exit( 1 );
	return( 0 );
}

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

	int	n_adj;
	int	n_v;
	char	v_name;
	char	v;
	int	w;

	/*
		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 = (int **)malloc( sizeof( int * )*n_graph );
	if( graph == NULL )
	{
		printf( "Impossibile allocare la memoria\n" );
		exit( 1 );
	}

	for( i = 0; i < n_graph; i++ )
	{
		graph[i] = (int *)malloc( sizeof( int )*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] = -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, "%c\n", &(nomi[i]) );

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

		n_v = get_index( v_name );
		for( j = 0; j < n_adj; j++ )
		{
			fscanf( fp, "%c %d\n", &v, &w );
			graph[n_v][get_index(v)] = w;
		}

	}

	fclose( fp );
}

void	print_graph( void )
{
	int	i, j;

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

void	visita( int start, int stop )
{
	int	i;

	if( start == stop )
	{
		if( costo_bs == -1 || costo_s < costo_bs )
		{
			costo_bs = costo_s;
			for( i = 0; i < n_s; i++ )
				bs[i] = s[i];
			n_bs = n_s;
		}
	}
	else
	{
		for( i = 0; i < n_graph; i++ )
			if( graph[start][i] != -1 && visitato[i] == 0 )
			{
				visitato[i] = 1;
				costo_s += graph[start][i];
				s[n_s++] = i;

				visita( i, stop );

				visitato[i] = 0;
				costo_s -= graph[start][i];
				n_s--;
			}
	}

}

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

	/*if( argc < 2 )
	{
		printf( "Uso: spia nomegrafo\n" );
		return( 1 );
	}              */

	read_graph( "treni.txt" );
	print_graph();

	n_bs = 0;
	costo_bs = -1;

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

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

	visita( 0, 7 );

	printf( "Il percorso ottimo Š: " );
	for( i = 0; i < n_bs;i++ )
		printf( "%c, ", nomi[bs[i]] );
	printf( "\nNumero di serrature = %d\n", costo_bs );

	free( nomi );
	free( s );
	free( bs );
	for( i = 0; i < n_graph; i++ )
		free( graph[i] );
	free( graph );
   getch();
	return( 0 );
}