/* Item.h */
typedef int Item;

/*
 * QUEUE.h 
 * INTERFACE: funcoes para manipular a fila 
 */

void QUEUEinit(int);
 int QUEUEempty();
void QUEUEput(Item);
Item QUEUEget();
void QUEUEfree();


/*
 *  distancias.c
 */

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

void
distancias (int n, int **a, int c, int *d)
{
  int j;
 
  QUEUEinit(n); /* inicializa a fila */

  /* inicializa o vetor de distancias */  
  for (j = 0; j < n; j++)  
    d[j] = n; /* distancia n = infinito */
  d[c] = 0;
  
  QUEUEput(c); /* coloca c na fila */
  
  /* QUEUEempty(): a fila esta vazia */ 
  while (!QUEUEempty()) 
    {
      int i, di;

      i = QUEUEget(); /* i recebe o 1o. elemento da fila */
  
      di = d[i];
      for (j = 0; j < n; j++)
	if (a[i][j] == 1 && d[j] > di+1) 
	  {
	    d[j] = di + 1;
            
            QUEUEput(j); /* coloca j na fila */
	  }
    }
  
  QUEUEfree();
}


int 
main(int argc, char *argv[]) 
{  
  FILE *fp_e; /* arquivo de estradas */
  FILE *fp_s; /* aqruivo de saida */

  char *nome_arq_e = NULL; /* nome do arquivo de estradas */
  char *nome_arq_s = NULL; /* nome do arquivo de saida    */
  
  int **a; /* a[i][j] == 1 se existe estrada de i a j */
  int no_c; /* numero de cidades */
  int origem = 0; /* cidade origem, default e' 0 */
  int *dist; /* dist[i] = comprimento do menor caminho de c a i */
  int i, j;
  
  
  if (argc == 1) 
    {
      fprintf(stdout,"Uso: %s -c<cid_origem> -f <arq_estradas> [-s <arq-saida>]\n", 
	      argv[0]);
      return 0;
    }
  
  /* Examina os argumentos na linha de comando */
  for (i = 1; i < argc; i++) 
    {
      if (sscanf(argv[i],"-c%d",&origem)==1);
      else if (strncmp(argv[i],"-f",2)==0) nome_arq_e = argv[++i];
      else if (strncmp(argv[i],"-s",2)==0) nome_arq_s = argv[++i];
      else 
	{
	  fprintf(stderr,
		  "Uso: %s -c<cid_origem> -f <arq_estradas> [-s <arq-saida>]\n",
		  argv[0]);
	  return -1;
	}
    }

  if ((fp_e = fopen(nome_arq_e,"r")) == NULL) 
    {
      fprintf(stderr,"\n%s: nao posso abrir arquivo %s.\n",
	      argv[0], nome_arq_e);
      return -1;
    }

  if (nome_arq_s == NULL) fp_s = stdout; /* saida default e' a padrao */
  else 
    if((fp_s = fopen(nome_arq_s,"w")) == NULL)
      {
	fprintf(stderr,
		"%s: arquivo de saida %s nao pode ser criado.\n", 
		argv[0], nome_arq_s);
	return errno;
      }

  /* le numero de cidades */
  fscanf(fp_e,"%d ", &no_c);
    
  /* aloca matriz de estradas */
  a = (int**) malloc(no_c * sizeof(int*));
  for (i = 0; i < no_c; i++)
    a[i] = (int*) malloc(no_c * sizeof(int));

  /* aloca vetor de distancias */
  dist = (int*) malloc(no_c * sizeof(int));
  
  /* leitura das estradas */  
  for (i = 0; i < no_c; i++) 
    for (j = 0; j < no_c; j++)
      if (fscanf(fp_e,"%d ", &a[i][j]) != 1)
	{
	  fprintf(stderr,"\n%s: faltam dados no arquivo %s.\n",
		  argv[0], nome_arq_e);
	  return -1;
	}
  fclose(fp_e);
  
  distancias(no_c, a, origem, dist);

  /* escreve a resposta */
  fprintf(fp_s, "\nDistancias a partir da cidade %d:\n", origem);

  for (i=0; i < 6; i++) 
    fprintf(fp_s, "%d: %d\n", i, dist[i]);

  fclose(fp_s);
  
  /* free memoria alocada */
  for (i = 0; i < no_c; i++)
    free(a[i]);
  
  free(a);
  return (0);
}

/* QUEUE.c: IMPLEMENTACAO DA FILA */
/*
#include <stdlib.h>
#include "Item.h"
#include "QUEUE.h"
*/

/*
 * FILA: uma implementacao circular
 */

Item *q;
int N, inicio, fim;
/*
 * Teremos que 0 <= inicio < N e 0 <= fim < N, mas em geral nao teremos 
 * que inicio <= fim 
 */


void QUEUEinit(int maxN)
{ 
  N =maxN+1;   /* necessitamos de uma posicao extra */
  q = (Item*) malloc(N*sizeof(Item));
  inicio = 0; 
  fim = 0;
}

int QUEUEempty()
{ 
  return inicio == fim; 
}

void QUEUEput(Item item)
{
  if ((fim+1) % N == inicio) 
    {
      fprintf (stderr,"Fila vai transbordar!\n");
      exit (-1);
    }
  q[fim++] = item;
  if (fim == N) fim = 0; 
}

Item QUEUEget()
{
  int i = inicio;
  inicio = (inicio + 1) % N;
  return q[i]; 
}

void QUEUEfree()
{
  free(q);
}