Solución de karel-obscuro-vs-karel

karelobscuro.cpp

#include <algorithm>
#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

#define IOI 2

struct Arco {
	int u;
	int v;
	int a;
	int b;
};

// Min-heap de pares de enteros.
priority_queue<pair<int, int>,
               vector<pair<int, int> >,
               greater<pair<int, int> > > q;

// La lista de arcos. Esto lo vamos a usar porque Karel Oscuro nos dice el
// índice del arco que tomó en cada paso.
vector<Arco> arcos;

vector<Arco> grafo[1025];
int costo_min[1025];
int costo_max[1025];

int main() {
	int N, M, P;
	scanf("%d %d %d\n", &N, &M, &P);

	for (int i = 0; i < M; i++) {
		Arco a;
		scanf("%d %d %d %d\n", &a.u, &a.v, &a.a, &a.b);
		arcos.push_back(a);
		grafo[a.u].push_back(a);
	}

	for (int i = 1; i <= N; i++) {
		costo_max[i] = 1 << 30;
	}

	int ciudad_actual = 1, costo_actual = 0, arco_actual;

	// Una ruta óptima se define como un camino tal que su distancia en el mejor
	// caso sea mejor que la ruta óptima usando solamente los costos máximos.
	// Intentaremos tomar todos los arcos que tomó Karel Oscuro hasta que
	// intentemos tomar un arco barato que haría que el costo acumulado de todo
	// el camino exceda el de la ruta óptima usando los costos máximos.
	for (int p = 0; p < P; p++) {
		// Hacemos Dijkstra a partir de la ciudad actual y con el costo actual
		// hacia todas las demás ciudades, usando los costos máximos para cada
		// ruta.
		q.push(make_pair(costo_actual, ciudad_actual));
		while (!q.empty()) {
			int costo = q.top().first;
			int ciudad = q.top().second;
			q.pop();

			if (costo_max[ciudad] <= costo) continue;
			costo_max[ciudad] = costo;

			for (int i = 0; i < grafo[ciudad].size(); i++) {
				q.push(make_pair(costo + grafo[ciudad][i].b, grafo[ciudad][i].v));
			}
		}

		// Ahora nos vamos por la ruta que nos indicó Karel Oscuro. Recuerda
		// que lo que nos indica son los números de arco que tomó, y que todas
		// las transiciones las hace utilizando el costo mínimo del arco.
		scanf("%d", &arco_actual);
		ciudad_actual = arcos[arco_actual - 1].v;
		costo_actual += arcos[arco_actual - 1].a;

		for (int i = 1; i <= N; i++) {
			costo_min[i] = costo_max[i] + 1;
		}

		// Ahora hacemos un Dijkstra, nuevamente con el costo actual y la
		// ciudad actual, pero ahora usando los costos mínimos de cada ruta.
		q.push(make_pair(costo_actual, ciudad_actual));
		while (!q.empty()) {
			int costo = q.top().first;
			int ciudad = q.top().second;
			q.pop();

			if (costo_min[ciudad] <= costo) continue;
			costo_min[ciudad] = costo;

			for (int i = 0; i < grafo[ciudad].size(); i++) {
				q.push(make_pair(costo + grafo[ciudad][i].a, grafo[ciudad][i].v));
			}
		}

		if (costo_min[IOI] > costo_max[IOI]) {
			// Usando el camino actual que indicó Karel Oscuro hasta el momento, no
			// existió un camino tal que usando los mínimos costos posibles sea
			// posible llegar a la IOI con un costo menor a la ruta más corta usando
			// los costos máximos posibles. Eso quiere decir que el arco que acabamos
			// de tomar definitivamente no está en ninguna ruta óptima y Karel Oscuro
			// nos llevó a dar una vuelta de más.
			printf("%d\n", arco_actual);
			return 0;
		}
	}

	// Si llegamos hasta acá, quiere decir que la ruta que tomó Karel Oscuro es
	// una posible ruta óptima.
	printf("Karel Obscuro le gustan los grafos\n");

	return 0;
}