// Descomenta la version que quieras probar

#include <iostream>
#include <vector>

using namespace std;

#include <limits>
#define INFINITO numeric_limits<float>::infinity()

/***************************************************************************
 VERSION 1: RECURSIVA, INEFICIENTE
 ***************************************************************************/

/*
float minimoCoste(const vector<vector<float> > & costeAlquiler,
                  int aldea) {
   
   // Minimo coste de llegar desde esa aldea hasta la ultima aldea

   float resultado;

   int ultimaAldea = costeAlquiler.size() - 1;

   if (aldea == ultimaAldea)
      resultado = 0;
   else {
      float minimo = INFINITO;
      for (int siguienteAldea = aldea + 1; siguienteAldea <= ultimaAldea; siguienteAldea++) {
         float intento = minimoCoste(costeAlquiler, siguienteAldea) + costeAlquiler[aldea][siguienteAldea];
         if (intento < minimo)
            minimo = intento;
      }
      resultado = minimo;
   }

   return resultado;

}

float minimoCoste(const vector<vector<float> > & costeAlquiler) {

   return minimoCoste(costeAlquiler, 0);

}
*/

/***************************************************************************
 VERSION 2: RECURSIVA, EFICIENTE
 ***************************************************************************/

/*
#define DESCONOCIDO -1

float minimoCoste(const vector<vector<float> > & costeAlquiler,
                  int aldea,
                  vector<float> & resultado) {
   
   if (resultado[aldea] == DESCONOCIDO) {

      int ultimaAldea = costeAlquiler.size() - 1;
      
      if (aldea == ultimaAldea)
	 resultado[aldea] = 0;
      else {
	 float minimo = INFINITO;
	 for (int siguienteAldea = aldea + 1; siguienteAldea <= ultimaAldea; siguienteAldea++) {
	    float intento = minimoCoste(costeAlquiler, siguienteAldea, resultado) + costeAlquiler[aldea][siguienteAldea];
	    if (intento < minimo)
	       minimo = intento;
	 }
	 resultado[aldea] = minimo;
      }
   }

   return resultado[aldea];

}

float minimoCoste(const vector<vector<float> > & costeAlquiler) {

   vector<float> resultado(costeAlquiler.size(), DESCONOCIDO);

   return minimoCoste(costeAlquiler, 0, resultado);

}
*/

/***************************************************************************
 VERSION 3: NO RECURSIVA, EFICIENTE
 ***************************************************************************/

/*
float minimoCoste(const vector<vector<float> > & costeAlquiler) {

   vector<float> resultado(costeAlquiler.size());

   int ultimaAldea = costeAlquiler.size() - 1;
      
   for (int aldea = ultimaAldea; aldea >= 0; aldea--)
      if (aldea == ultimaAldea)
	 resultado[aldea] = 0;
      else {
	 float minimo = INFINITO;
	 for (int siguienteAldea = aldea + 1; siguienteAldea <= ultimaAldea; siguienteAldea++) {
	    float intento = resultado[siguienteAldea] + costeAlquiler[aldea][siguienteAldea];
	    if (intento < minimo)
	       minimo = intento;
	 }
	 resultado[aldea] = minimo;
      }

   return resultado[0];

}
*/

/***************************************************************************
 EJEMPLO
 ***************************************************************************/

int main() {

   vector<vector<float> > ejemplo = {{0, 70, 30, 20, 90},
				     {0,  0,  0, 60, 10},
				     {0,  0,  0, 50, 40},
				     {0,  0,  0,  0, 80},
				     {0,  0,  0,  0,  0}
   };

   float resultado = minimoCoste(ejemplo);
   cout << "Coste minimo: " << resultado << endl;
   if (resultado == 70)
      cout << "OK" << endl;
   else
      cout << "MAL" << endl;
				     
}