=================================================================
Algoritmos y Estructuras de Datos (VJ1215) - Universitat Jaume I
Evaluacion continua - 2022/2023
16 de diciembre de 2022
Ejercicio 2.a
Borrador
Actualizado 21/1/24 para usar ColaDePrioridad del curso 2023/2024
=================================================================

El problema se puede resolver eficientemente utilizando una sola vez el algoritmo de
Dijkstra desde el vertice destino y recorriendo los arcos de entrada.

Para que el algoritmo de Dijkstra no siga recorriendo el grafo innecesariamente
cuando ya se puede determinar el resultado, se pueden hacer varias cosas:

1) Terminar si no hay mas caminos que no superen la energia dada.

2) Ir contando los jugadores cercanos conforme vamos llegando a ellos, y terminar si
ese contador coincide con la cantidad de jugadores.

3) Ir contando tambien, conforme vamos llegando a ellos, los jugadores que no pueden
llegar al destino sin superar la energia dada. Para saber que esos jugadores no
pueden llegar por ningun otro camino que no hayamos visto, podemos ir contando
cuantos arcos de salida nos falta ver en cada vertice.

La primera de las siguientes dos soluciones incorpora las ideas 1 y 2. En la segunda
solucion se agrega a eso la idea 3. En el examen se obtenia la maxima nota con la primera,
la segunda se proporciona aqui para quien quiera aprender algo mas.



Solucion buena pero mejorable (Dijkstra + Ideas 1 y 2)
======================================================

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

int GrafoDirigido::contarJugadoresCercanos(int destino,
					   float energia,
					   const vector<int> & jugadores) const {

   vector<int> cantidadDeJugadores(vertices.size(), 0);
   for (int v : jugadores)
      cantidadDeJugadores[v]++;
      
   int jugadoresCercanos = cantidadDeJugadores[destino];
   if (jugadoresCercanos == jugadores.size())
      return jugadoresCercanos;

   ColaDePrioridad colaDePrioridad(vertices.size());
   vector<float> pesoCaminoOptimo(vertices.size(), INFINITO);
   pesoCaminoOptimo[destino] = 0;
   for (int v = 0; v < vertices.size(); v++)
      colaDePrioridad.insertar(v, pesoCaminoOptimo[v]);

   while (! colaDePrioridad.estaVacia()) {
      int verticeElegido = colaDePrioridad.eliminarMinimo();

      if (pesoCaminoOptimo[verticeElegido] == INFINITO)
	 return jugadoresCercanos;

      for (Arco * arco = vertices[verticeElegido].primerArcoDeEntrada; arco != nullptr; arco = arco->siguiente) {
	 int vecino = arco->vecino;
	 float nuevoPeso = pesoCaminoOptimo[verticeElegido] + arco->peso;

	 if (nuevoPeso <= energia) {
	    if (pesoCaminoOptimo[vecino] == INFINITO) {
	       jugadoresCercanos += cantidadDeJugadores[vecino];
	       if (jugadoresCercanos == jugadores.size())
		  return jugadoresCercanos;
	    }
	    if (nuevoPeso < pesoCaminoOptimo[vecino]) {
	       pesoCaminoOptimo[vecino] = nuevoPeso;
	       colaDePrioridad.cambiarPrioridad(vecino, nuevoPeso);
	    }
	 }
      }
   }

}

Solucion mejorada (Dijkstra + Ideas 1, 2 y 3)
=============================================

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

int GrafoDirigido::contarJugadoresCercanos(int destino,
					   float energia,
					   const vector<int> & jugadores) const {

   vector<int> cantidadDeJugadores(vertices.size(), 0);
   for (int v : jugadores)
      cantidadDeJugadores[v]++;
      
   int jugadoresCercanos = cantidadDeJugadores[destino];
   if (jugadoresCercanos == jugadores.size())
      return jugadoresCercanos;

   int jugadoresNoCercanos = 0;   
   vector<int> salidasNoVistas(vertices.size());
   for (int v = 0; v < vertices.size(); v++) {
      salidasNoVistas[v] = vertices[v].gradoDeSalida;
      if (v != destino && salidasNoVistas[v] == 0) {
	 jugadoresNoCercanos += cantidadDeJugadores[v];
	 if (jugadoresCercanos + jugadoresNoCercanos == jugadores.size())
	    return jugadoresCercanos;
      }
   }
   
   ColaDePrioridad colaDePrioridad(vertices.size());
   vector<float> pesoCaminoOptimo(vertices.size(), INFINITO);
   pesoCaminoOptimo[destino] = 0;
   for (int v = 0; v < vertices.size(); v++)
      colaDePrioridad.insertar(v, pesoCaminoOptimo[v]);

   while (! colaDePrioridad.estaVacia()) {
      int verticeElegido = colaDePrioridad.eliminarMinimo();

      if (pesoCaminoOptimo[verticeElegido] == INFINITO)
	 return jugadoresCercanos;

      for (Arco * arco = vertices[verticeElegido].primerArcoDeEntrada; arco != nullptr; arco = arco->siguiente) {
	 int vecino = arco->vecino;
	 float nuevoPeso = pesoCaminoOptimo[verticeElegido] + arco->peso;
	 salidasNoVistas[vecino]--;

	 if (nuevoPeso <= energia) {
	    if (pesoCaminoOptimo[vecino] == INFINITO) {
	       jugadoresCercanos += cantidadDeJugadores[vecino];
	       if (jugadoresCercanos + jugadoresNoCercanos == jugadores.size())
		  return jugadoresCercanos;
	    }
	    if (nuevoPeso < pesoCaminoOptimo[vecino]) {
	       pesoCaminoOptimo[vecino] = nuevoPeso;
	       colaDePrioridad.cambiarPrioridad(vecino, nuevoPeso);
	    }
	 } else if (pesoCaminoOptimo[vecino] == INFINITO && salidasNoVistas[vecino] == 0) {
	    // No hemos llegado nunca a vecino sin superar energia y no hay mas formas de llegar
	    jugadoresNoCercanos += cantidadDeJugadores[vecino];
	    if (jugadoresCercanos + jugadoresNoCercanos == jugadores.size())
	       return jugadoresCercanos;
	 }
      }
   }

}