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

#define	MAX_FLOAT 100000

int	main(int argc, char	**argv,	char **env)
{
	FILE* fd;
	char buf[50];
	char *p;
	int	buflen,i,j,numnodos=0,nodopartida,indicearco=0;
	char *mode="r";
	float f,g;
	float **matriz;
	typedef	struct NC
	{
		int	i;
		int	j;
		float f;
	} nc;
	
	nc nodo;
	nc *resultado;
	
	//Chequea sintaxis
	if (argv[1]==NULL)
	{
		printf("Uso: %s	<Archivo de	datos>",argv[0]);
		exit(1);
	}
	
	//Cuenta cuántos nodos hay
	if ((fd=fopen(argv[1],mode))<0)	
	{
		perror(argv[1]);
		exit(1);
	}
	
	while (fgets(buf,sizeof(buf),fd)>0)
	{
		i=atoi(buf);
		if (i>numnodos)	numnodos=i;
		p=buf+1;
		while (*p>45 &&	*p<58) p++;
		j=atoi(p);
		if (j>numnodos)	numnodos=j;
	}
	numnodos++;
	fclose(fd);
	
	//Crea la matriz con el	numero de nodos
	matriz=new float*[numnodos];
	resultado=new nc[numnodos-1];
	
	for	(i=0;i<numnodos;i++)
	{
		matriz[i]=new float[numnodos+1];
		for	(j=0;j<numnodos+1;j++) matriz[i][j]=MAX_FLOAT;
	}
	
	
	//Llena	la matriz con los arcos
	if ((fd=fopen(argv[1],mode))<0)	
	{
		perror(argv[1]);
		exit(1);
	}
	
	while (fgets(buf,sizeof(buf),fd)>0)
	{
		i=atoi(buf);
		p=buf+1;
		while (*p>45 &&	*p<58) p++;
		j=atoi(p);
		p++;
		while (*p>45 &&	*p<58) p++;
		f=atof(p);
		matriz[i][j]=f;
	}
	fclose(fd);
	
	//Dijkstra
	nodopartida=0;
	matriz[0][numnodos]=0;
	//Busca el nodo más chico dentro de los posibles
	for	(int k=0;k<numnodos-1;k++)
	{
		nodo.f=MAX_FLOAT;
		for	(i=0;i<numnodos;i++)
		{
			if (matriz[i][numnodos]==0)
			{
				for	(j=0;j<numnodos;j++)
					if (nodo.f>matriz[i][j] && matriz[j][numnodos]!=0) 
					{
						nodo.f=matriz[i][j];
						nodo.i=i;
						nodo.j=j;
					}
			}
		}
	//Guarda el nodo y lo deja marcado en la matriz como "usado"
	
		resultado[indicearco].i=nodo.i;
		resultado[indicearco].j=nodo.j;
		resultado[indicearco].f=nodo.f;
		indicearco++;
		matriz[nodo.i][nodo.j]+=MAX_FLOAT;
		matriz[nodo.j][numnodos]=0;
	}
	
	for	(i=0;i<numnodos-1;i++)
		{
		int k;
		j=i;
		float t=resultado[j].f;
		printf("%i\t<--\t%i\t%f\n",resultado[i].j,resultado[i].i,resultado[i].f);
		while(resultado[j].i!=nodopartida)
		{
			for(k=0;resultado[k].j!=resultado[j].i;k++);
			j=k;
			t+=resultado[j].f;
			printf("%i\t<--\t%i\t%f\n",resultado[k].j,resultado[k].i,resultado[k].f);
		}
		printf("\t\t\t--------\n");
		printf("%i\t-->\t%i\t%f",nodopartida,resultado[i].j,t);
		printf("\n\n");
	
		}
	
	
	
	
	//Devueve la memoria pedida
	for	(int j=0;j<numnodos;j++)
		delete matriz[j];
	delete matriz;
	delete resultado;
}