// 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 la aldea 0 hasta esa aldea

   float resultado;

   if (aldea == 0)
      resultado = 0;
   else {
      float minimo = INFINITO;
      for (int anteriorAldea = 0; anteriorAldea < aldea; anteriorAldea++)
	 minimo = min(minimo,
		      minimoCoste(costeAlquiler, anteriorAldea) + costeAlquiler[anteriorAldea][aldea]);
      resultado = minimo;
   }

   return resultado;

}

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

   int cantidadDeAldeas = costeAlquiler.size();

   return minimoCoste(costeAlquiler, cantidadDeAldeas - 1);

}
*/

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

/*
#define DESCONOCIDO -1

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

      if (aldea == 0)
	 resultado[aldea] = 0;
      else {
         float minimo = INFINITO;
	 for (int anteriorAldea = 0; anteriorAldea < aldea; anteriorAldea++)
	    minimo = min(minimo,
			 minimoCoste(costeAlquiler, anteriorAldea, resultado) + costeAlquiler[anteriorAldea][aldea]);
	 resultado[aldea] = minimo;
      }

   return resultado[aldea];

}

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

   int cantidadDeAldeas = costeAlquiler.size();

   vector<float> resultado(cantidadDeAldeas, DESCONOCIDO);

   return minimoCoste(costeAlquiler, cantidadDeAldeas - 1, resultado);

}
*/

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

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

   int cantidadDeAldeas = costeAlquiler.size();

   vector<float> resultado(cantidadDeAldeas);

   for (int aldea = 0; aldea < cantidadDeAldeas; aldea++) 

      if (aldea == 0)
	 resultado[aldea] = 0;
      else {
         float minimo = INFINITO;
	 for (int anteriorAldea = 0; anteriorAldea < aldea; anteriorAldea++)
	    minimo = min(minimo,
			 resultado[anteriorAldea] + costeAlquiler[anteriorAldea][aldea]);
	 resultado[aldea] = minimo;
      }

   return resultado[cantidadDeAldeas - 1];

}
*/

/***************************************************************************
 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;
				     
}