#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <conio.h>
#include <string.h>
#define MaxNodos 47

typedef struct nodo_ {
    int etiqueta;
    float peso;
    struct nodo_ *sig;
}Tnodo;

/** variables globales */
Tnodo *Lista[MaxNodos]; //lista de adyacencia
int marca[MaxNodos]; //visitados
int predecesores[MaxNodos]; //ruta
float d[MaxNodos]; // distancia - peso
int Num_Vertices; //numero de vertices
int tipo; //1 no dirigido, 0 dirigido
 char uanl[250][250]; //Arreglo de nombres UANL
/** ------------------ */

/* Inicializa la lista de adyacencia a NULL */
void init() {
    int i;
    for (i = 0; i < MaxNodos; i++)
        Lista[i] = NULL;
}

int lista (int tipo)/*FUNCION QUE DESPLIEGA LA LISTA PARA SELECCIONAR LA OPCION DEL USUARIO*/
{
 int val=0;
do
{
 printf("\n\n\tSeleccione una opcion");
 int j=0;
 switch(tipo)
 {
  case 1: printf("\n\n\tCIUDAD UNIVERSITARIA");

  			for(j=1;j<=28;j++)
  			 	printf("%s\n",uanl[j]);

         break;
  case 2:printf("\n\n\tPREPARATORIAS");
  			for(j=29;j<=47;j++)
  			 	printf("%s\n",uanl[j]);

         break;
 };
 printf("\n\n\tIntroduzca el numero de la lista que desee...");
 scanf("%d",&val);
 clrscr();
}while(val<1 || val > 47);
 return val;
 }

/* Inserta los vertices en la lista de adyacencia */
void inserta (int Vorigen, int Vfinal, float peso) {
    Tnodo *q;
    q = (Tnodo*) malloc (sizeof(Tnodo) * 1);
    if (!q) return; //hubo un error
    q->etiqueta = Vfinal-1;
    q->peso     = peso;
    q->sig      = NULL;
    if (Lista[Vorigen-1] != NULL)
       q->sig = Lista[Vorigen-1];
    Lista[Vorigen-1] = q; 
}

/* Libera la lista de adyacencia */
void liberar_lista (void) {
   Tnodo *q;
   int i;
   for (i = 0; i <  Num_Vertices; i++) {
      if (Lista[i] != NULL) {
         while (Lista[i] != NULL) {
            q = Lista[i];
            Lista[i] = Lista[i]->sig;
            free(q);
         }
      } //--fin si (no necesarias las llaves)
   } //--fin for (no necesaria las llaves)
}

/* Carga el grafo desde un fichero */
void cargar_grafo (char *fn) {
  FILE *fp;
  int v_in, v_fn; //vertice inicial y final
  float peso;
  if ((fp = fopen (fn, "r")) == NULL) {
       printf ("El archivo %s no existe o no se puede abrir\n", fn);
       getche();
       exit(0);
   }
   fscanf (fp, "%d\n", &tipo); //tipo es una vble global
   fscanf (fp, "%d\n", &Num_Vertices); //Num_Vertices es una vble global 
   while (!feof(fp)){
         fscanf(fp, "%d %d %f\n", &v_in, &v_fn, &peso);
         inserta(v_in, v_fn, peso);
         inserta (v_fn, v_in, peso);
   }
   fclose (fp);
} // fin cargar_grafo
void cargar_nombres (char *fn) {
  FILE *fp;
    if ((fp = fopen (fn, "r")) == NULL) {
       printf ("El archivo %s no existe o no se puede abrir\n", fn);
       getche();
       exit(0);
   }

        int i=1;
        char caracteres[150];

        printf("\nEl contenido del archivo de prueba es \n\n");
        while (feof(fp) == 0)
        {
        			 fgets(caracteres,100,fp);
                strcpy(uanl[i], caracteres);
                i++;
        }
         fclose (fp);
} // fin cargar_nombres


/* Retorna el peso de la arista que une dos nodos */
float return_peso (int origen, int destino) {
   Tnodo *p;
   int encontrado;

   encontrado = 0;
   p = Lista[origen];
   while (p != NULL && !encontrado) {
      if (p->etiqueta == destino)
        encontrado = 1;
      else
        p = p->sig;
   }
   return p->peso;
}


int menor_valor() {
   int i, verticeMenor;
   float menor;
   menor = INT_MAX;
   for (i = 0; i < Num_Vertices; i++) {
      if (marca[i] == 0 )
         if (menor > d[i]) {
            menor = d[i];
            verticeMenor = i;
         }
   } // fin for
   return verticeMenor;
}

/* Dijkstra */
void dijkstra (int origen, int destino)
{
   int i, last, x;
   Tnodo *p;
   // inicializacion
   for (i = 0; i < MaxNodos; i++) {
      d[i] = INT_MAX; //"infinito"
      marca[i] = 0;
      predecesores[i] = -1;
   }
   // --
   d[origen] = 0;
   marca[origen] = 1;
   last = origen;
   while (marca[destino] == 0) { //hasta que no lleguemos al destino
      p = Lista[last];
      while (p != NULL){   //para todos los nodos adyacendes
          if (marca[p->etiqueta] == 0) //si no ha sido visitado
	          if (d[p->etiqueta] > d[last] + return_peso(last, p->etiqueta))
              {
	              d[p->etiqueta] = d[last] + return_peso(last, p->etiqueta);
	              predecesores[p->etiqueta] = last;
	          } // fin si
           p = p->sig;
      } // fin mientras
      x = menor_valor();
      marca[x] = 1;
      last = x;
   } // fin mientras
}

/* Imprime la ruta por pantalla */
void ImprimirCamino(int v) {
   if (v != -1)
      ImprimirCamino(predecesores[v]);
   if (v != -1) //evitamos que se imprima el -1
      {

                 printf("%s\n",uanl[v+1]);

      }
}

/* Menu de opciones */
int menu() {
    int opcion;
    do {
        printf ("\n\n\t[0] Salir\n\t");
        printf ("[1] Calcular ruta\n\n");
        printf ("Opcion:_");
        scanf("%d", &opcion);
    }while (opcion < 0 || opcion > 1);
    return opcion;
}

/* Funcion principal */
int main () {
    char file[25];
    int origen, destino,opi,tipo=0;
    int salir = 0;
    printf("\n\n\n\tBIENVENIDO\n\n\t...Presione cualquier tecla para comenzar..._");
    getche();
    init();
    cargar_grafo("GrafoUANL.txt");
    cargar_nombres("ListadoUANL.txt");
    clrscr();
    printf("\n\n\tSeleccione una opcion...");
    do {
        switch(menu())
        {
            case 0:
                 		salir = 1;
                 		break;
            case 1:
                     while(tipo!=1&&tipo!=2)
     							{
      							clrscr();
                           printf("\n\tSi desea partir de una facultad introduzca 1\n\tSi desea partir de una preparatoria introduca 2....._");
                           scanf("%d",&tipo);

     							}
                        	origen = lista (tipo);
     								tipo=0;
							while(tipo!=1&&tipo!=2)
     							{
      							clrscr();
									printf("\n\tSi desea llegar de una facultad introduzca 1\n\tSi desea llegar de una preparatoria introduca 2....._");
                           scanf("%d",&tipo);
                        }
                      		destino= lista (tipo);
                     dijkstra(origen-1, destino-1);
                    	printf("\n\n\tLA RUTA MAS RAPIDA ES....\n\n");
                 		ImprimirCamino(destino-1);
                  	break;
        }; //final switch
    tipo=0;
    }while(!salir);
    liberar_lista();

    }