Miketo_prog

Búsqueda de Enkidu

Jun 13th, 2021
730
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <math.h>
  3.  
  4. int visitada(int, int[], int);
  5.  
  6. int main(){
  7.     int N;
  8.  
  9.     scanf("%d", &N);
  10.  
  11.     int matriz[N][N];
  12.     int distancias[N];
  13.     int ciudades[N];
  14.  
  15.     ciudades[0] = 0;
  16.  
  17.     //Leo la matriz e inicio en cero el vector distancias
  18.     for(int i=0; i<N; i++){
  19.         distancias[i] = 0;
  20.  
  21.         for(int j=0; j<N; j++)
  22.             scanf("%d", &matriz[i][j]);
  23.     }
  24.  
  25.     //Cargo la suma de las columnas en el vector distancias
  26.     for(int j=0; j<N; j++)
  27.         for(int i=0; i<N; i++)
  28.             distancias[j] += matriz[i][j];
  29.  
  30.     //Determino la ciudad visitada
  31.     for(int i=0; i<N; i++){
  32.         int ind = visitada(ciudades[i], distancias, N);
  33.  
  34.         ciudades[i+1] = ind;
  35.     }
  36.  
  37.     //Imprimo las ciudades visitadas
  38.     for(int i=1; i<N; i++){
  39.         printf("%d", ciudades[i]+1);
  40.         if( i+1!=N ) printf(" ");
  41.     }
  42.  
  43.     return 0;
  44. }
  45.  
  46.  
  47. int visitada(int ultima, int distancias[], int N){
  48.     int cd;
  49.     int menor = 100000;
  50.  
  51.     for(int i=0; i<N; i++){
  52.         if( distancias[i]==0 ){
  53.             distancias[i] = -1;
  54.             return ultima;
  55.         }
  56.  
  57.         if( ultima!=i && distancias[i]!=-1 ){
  58.             int resta = abs(distancias[i]-distancias[ultima]);
  59.  
  60.             if( resta<menor ){
  61.                 menor = resta;
  62.                 cd = i;
  63.             }
  64.         }
  65.     }
  66.  
  67.     distancias[ultima] = -1;
  68.  
  69.     return cd;
  70. }
  71.  
  72.  
  73.  
  74.  
RAW Paste Data