#include <stdio.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.
*/
int	**graph;
int	n_graph;	/* Numero di nodi nel grafo */

int	*Q;		/* coda per Dijkstra */
int	*pi;		/* elenco nodi visitati */
int	*flag;		/* indica i nodi gia` estratti */

void	read_graph( char *s )
{
	FILE	*fp;
	int	i, j;
	int	n_adj;
	int	n_v;
	int	v, 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;
	}

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

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

	}

	fclose( fp );
}

void	print_graph( void )
{
	int	i, j;

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

int	extract_min( int *Q )
{
	int	i;
	int	min;

	for( i = 0; i < n_graph; i++ )
		if( Q[i] != -1 && Q[i] != 0 && flag[i] == 0 )
			break;

	if( i == n_graph )
		return( -1 );

	min = i;

	for( i = min+1; i < n_graph; i++ )
		if( Q[i] != -1 && Q[i] != 0 && flag[i] == 0 && Q[i] < Q[min] )
			min = i;

	return( min );
}

void	print_v( int *v, int n )
{
	int	i;

	printf( "NODI: " );
	for( i = 0; i < n; i++ )
		printf( "%2d ", i+1 );
	printf( "\n" );
	printf( "W:    " );
	for( i = 0; i < n; i++ )
		printf( "%2d ", v[i] );
	printf( "\n" );
	printf( "PI:   " );
	for( i = 0; i < n; i++ )
		printf( "%2d ", pi[i]+1 );
}

void	dijkstra( int s )
{
	int	i, u, n;

	s--;	/* Nella matrice i nodi partono da 0, ma nella realta` da 1 */

	/*
		Inizializzo la struttura dati
	*/
		
	/*
		Memorizza i nodi gia` toccati
	*/
	flag = (int *)malloc( sizeof( int )*n_graph );
	if( flag == NULL )
	{
		printf( "Impossibile allocare la memoria\n" );
		exit( 1 );
	}

	for( i = 0; i < n_graph; i++ )
		Q[i] = -1;
	for( i = 0; i < n_graph; i++ )
		flag[i] = 0;
	Q[s] = 0;	/* Costo per il nodo di partenza = 0 */
	flag[s] = 1;	/* Ho gia` toccato il nodo di partenza */
	pi[s] = s;	/* Il nodo di partenza non ha predecessore */

	/*
		Inizializzo i costi: Q[i] = -1 per ogni nodo non connesso ad s,
		altrimenti Q[i] = graph[s][i]
	*/
	for( i = 0; i < n_graph; i++ )
		if( graph[s][i] != -1 )
		{
			Q[i] = graph[s][i];
			pi[i] = s;
		}

	n = 1;
	while( n < n_graph )
	{
		printf( "Passo %d\n", n );

		u = extract_min( Q );	
		if( u == -1 )
			break;

		printf( "Estratto: %d\n", u+1 );

		flag[u] = 1;

		for( i = 0; i < n_graph; i++ )
			if( graph[u][i] != -1 )
				if( Q[i] > Q[u] + graph[u][i] || Q[i] == -1 )
				{
					Q[i] = Q[u] + graph[u][i];
					pi[i] = u;
				}
		n++;

		print_v( Q, n_graph );
		printf( "\n\n\n" );
	}

	free( flag );
}

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

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

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

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

	Q = (int *)malloc( sizeof( int )*n_graph );
	if( Q == NULL )
	{
		printf( "Impossibile allocare la memoria\n" );
		exit( 1 );
	}
	pi = (int *)malloc( sizeof( int )*n_graph );
	if( pi == NULL )
	{
		printf( "Impossibile allocare la memoria\n" );
		exit( 1 );
	}

	dijkstra( s );
}