=================================================================
Algoritmos y Estructuras de Datos (VJ1215) - Universitat Jaume I
Evaluacion continua - 2022/2023
16 de diciembre de 2022
Ejercicio 2.b
Borrador
=================================================================

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

Para que la busqueda en anchura no siga recorriendo el grafo innecesariamente
cuando ya se puede determinar el resultado, podemos:

1) Ir contando los jugadores cercanos conforme vamos llegando a ellos, y terminar si
hemos llegado a todos los jugadores.

2) No insertar en la cola los vertices cuyos jugadores ya han sido contados y que han
sido alcanzados utilizando la maxima cantidad de arcos que se pueden utilizar con la
energia dada.


Solucion
========

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;

   if (vertices[destino].primerArcoDeEntrada == nullptr)
      return jugadoresCercanos;
   int distanciaMaxima = energia / vertices[destino].primerArcoDeEntrada->peso;
   if (distanciaMaxima == 0)
      return jugadoresCercanos;
   
   vector<int> distancia(vertices.size(), -1);
   queue<int> cola;

   distancia[destino] = 0;
   cola.push(destino);
   
   while (! cola.empty()) {
      int v = cola.front();
      cola.pop();
      for (Arco * arco = vertices[v].primerArcoDeEntrada; arco != nullptr; arco = arco->siguiente)
	 if (distancia[arco->vecino] == -1) {
	    jugadoresCercanos += cantidadDeJugadores[arco->vecino];
	    if (jugadoresCercanos == jugadores.size())
	       return jugadoresCercanos;
	    distancia[arco->vecino] = distancia[v] + 1;
	    if (distancia[arco->vecino] < distanciaMaxima)
	       cola.push(arco->vecino);
	 }
   }
   
   return jugadoresCercanos;
}