Problema 1004. Sightseeing Trip (Ruta Turística) de acm.timus.ru

  1004. Sightseeing Trip

Este problema lo resolví utilizando un algoritmo de recorrido de un grafo, que represento por medio de una matriz y varios vectores. El grafo lo recorro por medio de una rutina que utiliza backtraking.  Debe compilarse con g++


// Compilar con g++

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


int no_se_ha_escogido_el_nodo(int vertic, int lim );
void guarda_vector(int vert_i, int lim);
void recorrido_minimo(int nivel, int distancia_recorrida) ;

int calcula_distancia (int lim, int indi);
int ind_vector(int vector, int lim);


int vert[100][10000];     // matriz que enlaza un vertice con otro
int cam[100][100];      // matriz que indica la distancia entre cada camino
int ind[100], i;    // matriz que indica el indice de los caminos que parten de un vertice
int vertices[100];     // matriz que indica el vertice que se esta recorriendo para un determinado nivel de profundidad
int vect_guardado[100]; // matriz en donde se guarda el recorrido de la solucion
int orden[100];        // matriz que indica el orden en el que se dieron los vertices o nodos
int se_dio[101];
int lim_vector_guardado;     // el tamaño del vector que se guardo
int vertice_i;



int distancia_minima = 0x7fffffff;
int N, M;

int main (void) {
  int i;
  int ni; int nk; int distancia;

  int distancia_min, distancia_recorrida;
 




  do {
    memset(vert, 0, sizeof(int)*1000000);
    memset(cam, 0, sizeof(int)*10000);
    memset(ind, 0, sizeof(int)*100);
    memset(orden, 0, sizeof(int)*100);
    memset(se_dio, 0, sizeof(int)*101);

    scanf("%d", &N);  // toma vertices
    if(N==-1) break;
    scanf("%d", &M);  // toma el numero de caminos
    int j=0;
    for(i=0; i < M; i++) {
   
      scanf("%d%d%d", &ni, &nk, &distancia);
      if(cam[ni-1][nk-1] == 0) {
        vert[ni-1][ind[ni-1]] = nk;
        vert[nk-1][ind[nk-1]] = ni;

        if(se_dio[ni-1]== 0 ) {

          se_dio[ni-1]=1;
          orden[j] = ni;j++; 
        } 
        if(se_dio[nk-1] ==0) {
          se_dio[nk-1]=1;    
          orden[j] = nk;j++;        
        }

        ind[ni-1]++;
        ind[nk-1]++;
        cam[ni-1][nk-1] = distancia;
        cam[nk-1][ni-1] = distancia;   
      }
      else if(cam[ni-1][nk-1] > distancia) {
        cam[ni-1][nk-1] = distancia;
        cam[nk-1][ni-1] = distancia;   

      }
     

    }

    // debido a que el grafo puede ser inconexo se chequean todos los vertices utilizando la matriz orden[k]... saltando de 2 en dos porque basta con
    // chequear uno de la pareja de cada camino dado
    //vertice_i=orden[0];
   

    for(int k=0; k < N; k+=2) {
      vertice_i = orden[k];
      recorrido_minimo(0, 0);

    }


    if(distancia_minima != 0x7fffffff) {
      for(i=0; i < lim_vector_guardado-1; i++) {
        printf("%d ", vect_guardado[i]);
      }

      printf("%d\n", vect_guardado[lim_vector_guardado-1]);
      distancia_minima = 0x7fffffff;
    }

    else {
      printf("No solution.\n");
    }

  } while(1);



}


void recorrido_minimo(int nivel, int distancia_recorrida) {
   int j, distancia;

  
   if(distancia_recorrida >= distancia_minima) return;
   if(nivel==0) {
     vertices[nivel] = vertice_i;

     recorrido_minimo(1, distancia_recorrida);
   }

   else {

     j=0;

    
     while(vert[vertices[nivel-1]  -1 ][j]!=0  )  {
       distancia = no_se_ha_escogido_el_nodo(vert[vertices[nivel-1] -  1][j] , nivel );   
      
       if(!distancia) {
        
         vertices[nivel] = vert[vertices[nivel-1] -1 ][j];

         recorrido_minimo(nivel+1, distancia_recorrida + cam[vertices[nivel-1] -1 ][vertices[nivel] - 1]);  

       }  
       else if(nivel - ind_vector(vert[vertices[nivel-1] -  1][j], nivel) > 2){

      if(distancia < distancia_minima) {

            distancia_minima = distancia;
            guarda_vector(vert[vertices[nivel-1] -  1][j], nivel);
          }

       }
       j++;


     }



   }
    


}

int ind_vector(int vector, int lim) {
  int i;
  for(i=0; i < lim; i++ ) {
    if(vector == vertices[i]) {  
      return i;
    }    

  }
}

int no_se_ha_escogido_el_nodo(int vertic, int lim ) {
  int i;
  for(i=0; i < lim; i++ ) {
    if(vertic == vertices[i]) {       
      return calcula_distancia (lim, i);
    }

  }

  return 0;
}


void guarda_vector(int vert_i, int lim) {
  int i;
  for(i=0; i < lim; i++){
     if(vertices[i] == vert_i)  {
       for(int j=i; j < lim; j++) {
         vect_guardado[j-i] = vertices[j] ;


       }
       break;
     }

  }
  lim_vector_guardado = lim - i;

}

int calcula_distancia (int lim, int indi) {
  int distancia=0;
  for(int i=indi+1; i < lim; i++) {
    distancia = distancia + cam[vertices[i-1] -1 ][vertices[i] - 1];
  }
  distancia = distancia + cam[vertices[indi] -1 ][vertices[lim-1] - 1];
  return distancia;

}