Desafío Dal Lago #3: Charly y Nito (N3)

Me pareció que era hora de publicar mi problema favorito :heart_eyes:.
Este problema sería para un nivel 3. Por eso el N3.
No por eso dejen de intentarlo. Tampoco es tan difícil, y ciertamente no es un problema difícil de implementar, solo de pensar.


No conseguí el enunciado en español, aunque debe estar por ahí. Si algo no se entiende pregunten.
Por otro lado, dejo este álbum muy relevante que también me gusta mucho. https://www.youtube.com/watch?v=aDycKexo-3Q

2 Me gusta

No existe enunciado oficial en castellano (las “locales de UBA”, que existieron hasta 2010 y son la fuente original de este problema, siempre fueron en inglés). Cualquier traducción que haya o que se haga es fan fiction.

1 me gusta

Acá está el enunciado en castellano traducido recién:

Charly y Nito son amigos y les gusta pasar tiempo en un lindo bar de Palermo Hollywood. Alrededor de las 3 a.m. empieza a tener sueño y se quieren ir a casa. Quieren llegar lo más rápido posible, para eso cada uno usa un camino que minimiza la distancia desde el bar hasta sus respectivas casas. Sin embargo, también les gusta caminar juntos mientras hablan de “los viejos tiempos”, así que quieren caminar juntos la mayor distancia posible.
Charly y Nito viven en una ciudad que se puede modelar como un conjunto de calles y esquinas. Cada calle conecta dos esquinas distintas y se puede caminar en ambas direcciones. No hay dos calles que conecten las mismas dos esquinas. Charly y Nito no viven juntos, y tampoco viven en el bar. Hay por lo menos un camino desde el bar hasta la casa de Charly, y también por lo menos un camino hasta la casa de Nito.
Dada la información sobre las calles y las esquinas de la calle, y en qué esquinas están el bar, la casa de Charly y la de Nito, debes indicarles a Charly y Nito la máxima distancia que pueden caminar juntos sin forzarlos a caminar una distancia mayor a lo mínimo que pueden desde el bar hasta sus respectivas casas. También Charly y Nito quieren saber cuánto tienen que caminar solos.

\large Input

La entrada consiste en varios casos, cada uno descripto por varias líneas. La primera línea de cada caso contiene cinco enteros, J, B, C, N, S separados por espacios. El valor de J es la cantidad de esquinas en la ciudad (3 \leq J \leq 5000); cada esquina estará identificada por una valor entre 1 y J inclusive. Los valores B, C y N representan la esquina del bar, la casa de Charly y la de Nito respectivamente (1 \leq B,C,N \leq J); estos tres números son distintos entre sí. El valor de S representa la cantidad de calles en la ciudad (2 \leq S \leq 150000). Cada una de las siguiente S líneas contiene la descripción de cada calle. Cada calle se la representa por tres enteros E1 E2 y L, separados por espacios. donde E1 y E2 representan las esquinas que conecta la calle (1 \leq E1,E2 \leq J), y L es la longitud de la misma (1 \leq L \leq 10000). Podés asumir que cada calle conecta dos esquinas distintas, y que existe al menos un camino entre la esquina B y cada una de las esquinas C y N. La última línea de la entrada contiene un -1 cinco veces separados por espacios y no debe procesarse como un caso.

\large Output

Para cada caso de prueba imprimir una línea con tres enteros T, C y N separados por un espacio, donde T es la máxima distancia que pueden caminar juntos, y C y N son las distancias que deben caminar Charly y Nito solos respectivamente.

\large Ejemplo
Ver ejemplo en el link

Sé que es de hace bastante este desafío pero nadie publicó respuesta, así que quería reactivarlo.

2 Me gusta

Para revivir el post aca va una solucion(es fea):

Solucion
#include <iostream>
#include <vector>
#include <stdio.h>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
using namespace std;
#define ll long long
int main() {
	ll bar, x, charly, nito, y, w;
	while (cin >> x >> bar >> charly >> nito >> y) {
		if (x == -1) {
			break;
		}
		ll index, max, a, b;
		max = 0;
		priority_queue<pair<ll, ll> > q;
		vector <ll> e(x + 1);
		vector <int> z(x + 1, 0);
		vector <ll> e1(x + 1);
		vector <int> z1(x + 1, 0);
		vector <ll> e2(x + 1, 0);
		vector <int> z2(x + 1, 0);
		vector<vector <pair<int, int> > > v(x + 1);
		for (int i = 0; i < y; i++) {
			cin >> a >> b >> w;
			v[a].push_back(make_pair(b, w));
			v[b].push_back(make_pair(a, w));
		}
		//cout << "a";
		for (int i = 1; i <= x; i++) e[i] = 100000000000;
		e[charly] = 0;
		q.push({ 0,charly });
		while (!q.empty()) {
			int a = q.top().second; q.pop();
			if (z[a]) continue;
			z[a] = 1;
			for (auto b : v[a]) {
				if (e[a] + b.second < e[b.first]) {
					e[b.first] = e[a] + b.second;
					q.push({ -e[b.first],b.first });
				}
			}
		}
		//cout << "a";
		for (int i = 1; i <= x; i++) e1[i] = 100000000000;
		e1[nito] = 0;
		q.push({ 0,nito });
		while (!q.empty()) {
			int a = q.top().second; q.pop();
			if (z1[a]) continue;
			z1[a] = 1;
			for (auto b : v[a]) {
				if (e1[a] + b.second < e1[b.first]) {
					e1[b.first] = e1[a] + b.second;
					q.push({ -e1[b.first],b.first });
				}
			}
		}
		for (int i = 1; i <= x; i++) e2[i] = 100000000000;
		e2[bar] = 0;
		q.push({ 0,bar });
		while (!q.empty()) {
			int a = q.top().second; q.pop();
			if (z2[a]) continue;
			z2[a] = 1;
			for (auto b : v[a]) {
				if (e2[a] + b.second < e2[b.first]) {
					e2[b.first] = e2[a] + b.second;
					q.push({ -e2[b.first],b.first });
				}
			}
		}
		for (int i = 1; i <= x; i++) {
			if (e2[i] + e1[i] == e1[bar] && e2[i] + e[i] == e[bar]) {
				if (e2[i] > max) {
					max = e2[i];
				}
			}
		}
		cout << max << " " << e[bar]-max << " " << e1[bar]-max << endl;
	}
	return 0;
}
2 Me gusta

Quizá puedas contar un poco de “la idea” que hay atrás de la implementación. :slight_smile:

No sé si es “tan larga” la implementación, sino que a simple vista veo bastante código repetido.

Creo que este post de la wiki te puede venir bien: Funciones

2 Me gusta

Hice una solucion mas linda(supongo) pero por alguna razon cuando mando me tira un error que no se que significa, esta detallado cada cosa, espero que se entienda:

Solucion(Detallada)
#include <iostream>
#include <vector>
#include <stdio.h>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
using namespace std;
#define ll long long
priority_queue<pair<ll, ll> > q;
vector<vector <pair<int, int> > > v;
void dijkstra(int a, vector <ll> &v1) {
	vector <int> z(v1.size(), 0);
	v1[a] = 0;
	q.push({ 0,a });
	while (!q.empty()) {
		int s = q.top().second; q.pop();
		if (z[s]) continue;
		z[s] = 1;
		for (auto b : v[s]) {
			if (v1[s] + b.second < v1[b.first]) {
				v1[b.first] = v1[s] + b.second;
				q.push({ -v1[b.first],b.first });
			}
		}
	}
}
int main() {
	ll bar, x, charly, nito, y, w;
	while (cin >> x >> bar >> charly >> nito >> y) {
		if (x == -1) {
			break;
		}
		vector <pair<int,int> > v2;
		for (int i = 0; i <= x; i++) {
			v.push_back(v2);
		}
		ll index, max, a, b;
		max = 0;
		vector <ll> e(x + 1, 100000000000);
		vector <ll> e1(x + 1, 100000000000);
		vector <ll> e2(x + 1, 100000000000);
		for (int i = 0; i < y; i++) {
			cin >> a >> b >> w;
			v[a].push_back(make_pair(b, w));
			v[b].push_back(make_pair(a, w));
		}
		//Hacer Dijsktra en los tres lugares que nos da el enunciado
		dijkstra(charly, e);
		dijkstra(nito, e1);
		dijkstra(bar, e2);
		//En el for(abajo) buscamos un nodo n tal que, hasta ese nodo recorran el camino juntos..
		// y como sabemos la distancia de ese nodo hasta el bar y hasta ambas casas,..
		//Podemos verificar si se cumple la distancia minima (1)
		
		for (int i = 1; i <= x; i++) {
		//(1) En este if.
		//Sabemos que la distancia minima de la casa de charly y nito hasta el bar es e[bar] y e1[bar] respectivamente..
		//Por ende si la distancia desde el bar hasta en nodo buscado e2[i]..
		//Y la distancia de la casa(de charly en este caso) al nodo es e[i]
		//Si se cumple que e[i]+e2[i]==e[bar] entonces es un camino minimo
		// El AND se debe a que los dos deben cumplir lo anteriormente dicho.
		if (e2[i] + e1[i] == e1[bar] && e2[i] + e[i] == e[bar]) {
				if (e2[i] > max) {
					//Vemos cual es la mayor distancia
					max = e2[i];
				}
			}
		}
		cout << max << " " << e[bar] - max << " " << e1[bar] - max << endl;
	}
	return 0;
}
4 Me gusta

La idea está perfecta :slight_smile:

El error que contás al mandar la Solución(Detallada) es que no estás limpiando v entre casos (fijate que no hace falta limpiar q porque al terminar de correr el Dijkstra q sale vacío, y es algo que usás al usar el mismo q global en las 3 corridas de Dijkstra). Se arregla por ejemplo agregando la línea: v = {} al comenzar cada caso.

Ya que estoy, un par de comentarios:

  • El primero:
while (cin >> x >> bar >> charly >> nito >> y) {
  if (x == -1) {
     break;
  }
....
}

Se puede escribir como:

while (cin >> x >> bar >> charly >> nito >> y && x != -1) {
   ....
}

Hacen lo mismo, pero creo que es más compacto e igual de claro. Como siempre estas cosas son más de estilo.

  • El segundo, y este sí me parece importante: La línea #define ll long long me hace mucho ruido. Si no entiendo mal el #define hace un reemplazo en tu código y cada vez que aparezca ll en tu código se va a cambiar por long long. Por suerte ninguna variable ni nada en tu código usa ll.

    En estos casos es aconsejable usar un typedef de la siguiente forma:

typedef long long ll;

De paso, si hacés el typedef tu editor probablemente te haga syntax highlighting (te lo pinte de colorcito como a int). Al menos el editor geany lo hace.

Casi te doy una Insignia Ryckeboer, pero este es un Desafío Dal Lago, jeje :stuck_out_tongue:

2 Me gusta