Para guardar el grafo, tomé las galerías que no están obstruídas y las numeré desde 1 hasta G, y guardé el destino y el peso para cada uno de los nodos involucrados. Luego, tomé las galerías que están obstruídas, y las numeré desde -O hasta -1. De esta forma diferencio entre galería obstruída y no obstruída.
Para procesar la información, recorro con dijkstra, y por cada nodo guardo su distancia desde el nodo 1 y los números de las galerías obstruídas que se debieron abrir para hacer ese camino en un vector (el valor absoluto de ellas. Recordemos que las numeré negativamente).
Finalmente, muestro el caso correspondiente en base a las galerías obstruídas que se necesitaron reabrir, muestro las galerías y la longitud del camino.
Esta solución me dió 70/100 puntos. Los casos en los cuales falla, son todos Outputs incorrectos, y me gustaría poder encontrar el caso que no estoy tomando en cuenta. Si alguien puede ayudarme a encontrarlo, voy a estar más que agradecido.
Acá dejo mi código.
Código
#include <bits/stdc++.h>
using namespace std;
#define INF 9999999
#define debug(x) cout << #x << " = " << x << endl
#define forsn(i,s,n) for(int i = s; i < n; i++)
#define vec(v) v.begin(), v.end()
struct vecino{
int calle, destino, costo;
};
struct info_nodo{
long long dist;
vector<int> abiertas;
};
void dijkstra(vector<info_nodo> &dist, int s, int B, vector<vector<vecino>> grafo){
vector<bool> marked(B+1, false);
priority_queue<pair<long long,int>> q;
q.push({0, s});
while(!q.empty()){
int actual = q.top().second;
q.pop();
if(marked[actual]) continue;
marked[actual] = true;
for(auto u : grafo[actual]){
int calle = u.calle, veci = u.destino, costo = u.costo;
if(dist[veci].dist > dist[actual].dist + costo){
dist[veci].dist = dist[actual].dist + costo;
dist[veci].abiertas = dist[actual].abiertas;
if(calle < 0){
dist[veci].abiertas.push_back(abs(calle));
}
q.push({-dist[veci].dist, veci});
}
}
}
}
int main(){
ifstream in("ciudad.in");
ofstream out("ciudad.out");
int B, G, O;
in >> B >> G >> O;
vector<vector<vecino>> grafo(B+1);
forsn(i,1,G+1){
int u, v, p;
in >> u >> v >> p;
grafo[u].push_back({i, v, p});
grafo[v].push_back({i, u, p});
}
forsn(i,1,O+1){
int u, v, p;
in >> u >> v >> p;
grafo[u].push_back({-i, v, p});
grafo[v].push_back({-i, u, p});
}
vector<info_nodo> dist(B+1, {INF, {}});
dist[1].dist = 0;
dijkstra(dist, 1, B, grafo);
out << dist[B].abiertas.size()+1 << " ";
forsn(i,0,dist[B].abiertas.size()){
out << dist[B].abiertas[i] << " ";
}
out << dist[B].dist << endl;
}
No limitás la abertura de obstáculos. Tendrías que abrir a lo sumo 2 (un par).
Según entiendo en tu solución,
dist[B].abiertas.size() podría llegar a ser igual a O.
Solo guardas una distancia por nodo. Esto es más sutil.
El problema es que podrías llegar a un nodo con una distancia (d_1) abriendo 2 obstáculos. Después llegás al mismo nodo Sin usar obstáculos y con otra distancia mayor (d_2).
Tu programa solo guardaría d_1 por ser la distancia menor. Pero d_2 podría ser útil para alcanzar B, permitiéndote abrir obstáculos posteriores. Te propongo que pienses un ejemplo donde esto sucede y pruebes como falla el programa.
Pensalo y si no se te ocurre como tener en cuenta el punto 2, volvé a escribir .
Saludos!
Hola, reuso el thread para preguntar por una situación diferente que estoy enfrentando con este problema pues, hasta donde tengo entendido, creo que los puntos mencionados ya los tengo cubiertos.
Mi idea es un poco diferente:
Paso Dijkstra al grafo creado a partir de las galerías, sin las obstruidas.
Agrego al grafo las galerias obstruidas. Para identificar entre obstruidas y aquellas que no, agrego un elemento a la estructura que uso para almacenar el grafo. Es decir, además de tener el nodo al cual apunta cada uno y el peso de la arista, también almaceno un entero, que de ser -1 , no está obstruida. De lo contrario es un número positivo, que lo identifica según orden de entrada en el input.
Paso nuevamente Dijkstra, pero con un par de adicionales:
La estructura del priority_queue que uso en mi Dijkstra tiene un elemento adicional con el cual cuento, hasta el nodo en cuestión, cuantas galerías obstruidas usé. Entonces, si me encuentro con una arista de una galeria que está obstruida, sólo continuaré si mi contador es menor a 2.
Para almacenar los padres producto del segundo Dijkstra, uso un vector de pares de enteros. De esta forma, en el primer elemento almaceno el padre correspondiente, pero también en el segundo si corresponde o no, una galeria obstruida a él.
Dado todo eso, de ser menor la distancia con abrir galerias obstruidas, recorro los padres del segundo Dijkstra y guardo los identificadores de las galerias obstruidas que puedan acompañar a alguno/s de ellos. Si solo guardo 1 será el segundo caso, y de ser 2, el tercer caso.
Así termino mostrando dicho caso que haya determinado y, según corresponda, los identificadores de las galerias obstruidas utilizadas y la distancia final (peso del vertice final).
Mi inconveniente es que creo que tengo un problema en la implementación, pues hay un único caso incorrecto (caso 4), llegando así, después de pelear un poco, a los 95 ptos. Hay algún caso que probablemente me estoy olvidando, o algún detalle que me estoy pasando de largo. Dejo mi código por si alguien puede revisarlo, si no es molestia.
Código
#include <bits/stdc++.h>
#define forn(i,n) for(ll i = 0; i < ll(n); i++)
#define forsn(i,s,n) for(ll i = ll(s); i < ll(n); i++)
#define dforn(i,n) for (ll i = ll(n)-1; i >= 0; i--)
#define dforsn(i,s,n) for(int i = ll(n)-1; i >= ll(s); i--)
#define all(c) (c).begin(),(c).end()
#define fst first
#define snd second
#define FAST_IO ios::sync_with_stdio(false);cin.tie(nullptr);
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int> ii;
const int MAXN = 1e4+2;
struct nodo {
int v,d;
int obstruido;
bool operator< (const nodo &o) const{
return o.d < d;
}
};
vector<nodo> G[MAXN];
vi distNO,padresNO,dist;
vector<ii> padres;
void dijkstra(int st, vi &D, vi &P) {
priority_queue<nodo> Q;
Q.push({st,0,-1});
D[st] = 0;
while (not Q.empty()) {
auto x = Q.top(); Q.pop();
if (D[x.v] < x.d) continue;
for (auto &w : G[x.v]){
if (D[w.v] == -1 or D[w.v] > w.d + x.d) {
D[w.v] = w.d + x.d;
P[w.v] = x.v;
Q.push({w.v, D[w.v], -1});
}
}
}
}
int B,g,O;
struct nodo_dijkstra {
int v,d;
int obstruido;
int cantObstruidos;
bool operator< (const nodo_dijkstra &o) const{
return o.d < d;
}
};
void dijkstraBuscar (int st, vi &D, vector<ii> &P) {
priority_queue<nodo_dijkstra> Q;
Q.push({st,0,-1,0});
D[st] = 0;
while (not Q.empty()) {
auto x = Q.top(); Q.pop();
if (D[x.v] < x.d) continue;
for (auto &w : G[x.v]){
if (D[w.v] == -1 or D[w.v] > w.d + x.d) {
int obstruidos = x.cantObstruidos;
if (w.obstruido != -1) {
if (x.cantObstruidos >= 2) continue;
obstruidos++;
}
D[w.v] = w.d + x.d;
P[w.v].fst = x.v;
P[w.v].snd = w.obstruido;
Q.push({w.v, D[w.v], w.obstruido, obstruidos});
}
}
}
}
int main() {
FAST_IO;
freopen("ciudad.in","r",stdin);
freopen("ciudad.out","w",stdout);
cin >> B >> g >> O;
forn (i,g) {
int a,b,p;
cin >> a >> b >> p;
G[a].push_back({b,p,-1});
G[b].push_back({a,p,-1});
}
distNO.resize(B+2,-1);
padresNO.resize(B+2,-1);
dist.resize(B+2,-1);
padres.resize(B+2,{-1,-1});
dijkstra(1,distNO,padresNO);
forn (i,O) {
int a,b,p;
cin >> a >> b >> p;
G[a].push_back({b,p,(int)i+1});
G[b].push_back({a,p,(int)i+1});
}
dijkstraBuscar(1,dist,padres);
if (distNO[B] <= dist[B])
cout << 1 << ' ' << distNO[B];
else {
vi obstruidos;
for (int i = B, obstr = padres[B].snd; i != -1; i = padres[i].fst, obstr = padres[i].snd) {
if (obstr != -1) {
obstruidos.push_back(obstr);
if (obstruidos.size() == 2) break;
}
}
reverse(all(obstruidos));
if (obstruidos.size() == 1) cout << 2 << ' ';
if (obstruidos.size() == 2) cout << 3 << ' ';
for (auto &i : obstruidos)
cout << i << ' ';
cout << dist[B];
}
return 0;
}
PD: Entiendo que el código se puede mejorar/acortar, como solo codear un único Dijkstra, por ejemplo. Pero eso creo requeriría que transforme vi padres en vector<ii> padres innecesariamente, y por cosas mías, prefiero ahorrar ese pequeño de memoria, entre otras decisiones menores.
Primero que nada, perdón por la demora. Bailando entre prioridades, responder este post me quedó un poco abajo. En fin, acá van mis comentarios/observaciones que veo.
Ahí hay que tener cuidado, porque al actualizar i y obstr, si bien primero se hace el chequeo de que i != -1, luego se actualiza i = padres[i].fst, lo cual puede hacer que se acceda con índice -1 en obstr = padres[i].snd.
Una posible entrada donde falla es la siguiente:
2 1 2
1 2 3
1 2 2
1 2 4
De todas formas, esa no es la razón por la que tu código no saca 100 puntos. Sospecho que lo que está pasando está relacionado con algo que mencionó Brian más arriba:
Te dejo un dibujito del ejemplo por si te ayuda. Tu código devuelve 3 1 2 8, o sea que usa las dos aristas de peso 1 de arriba a la izquierda, sin embargo debería arrojar 3 3 4 7, usando las otras dos galerías obstruídas.
Al llegar al nodo 4 con costo 2, usando dos galerías obstruídas, después tu código no ve la opción de llegar al nodo 4 con costo 3 usando una sola galería obstruída.
Mi sugerencia para resolver el problema (sobre todo por lo que ya tenés escrito) es agrandar el estado con toda esta información (lo cual explico en detalle más abajo).
Sin agrandar el estado, una opción para resolver el problema, que no sé si entra en tiempo (pero si no entra debe ser por poquito), es probar todas las formas posibles de agregar las galerías obstruídas. Es decir, si O es la cantidad de galerías obstruídas, propongo explorar las \underset{\text{perforar cada par}}{\underbrace{\binom O 2}}+\underset{\text{perforar solo una}}{\underbrace{\binom O 1}} + \underset{\text{no perforar}}{\underbrace{\binom O 0}} \leq 5051 (pues O \leq 100 por enunciado), y luego para cada una de ellas correr un Dijkstra normal.
Creo que te referís a correr dos Dijkstras y smplemente reciclar el código. De todas formas, este problema se puede resolver corriendo Dijkstra una sola vez, pero sobre un grafo que tenga la información necesaria para modelar el problema. Por lo visto, podemos modelar la situación pedida con un grafo cuyos nodos son de la forma \texttt{(bifurcación_actual, perforaciones_utilizadas)} \sim (b,p), y las transiciones serían utilizar alguna galería desde la bifurcación actual para moverse entre los nodos.
Por supuesto, estas transiciones dependerán de la galería en cuestión. Si una galería g conecta las bifurcaciones b_1 y b_2, y se utilizaron p < 2 perforaciones hasta ahora, entonces tendremos transiciones del estilo:
(b_1,p) \rightarrow \left\{\begin{matrix}
(b_2,p) \text{ si } g \text{ no está obstruída}\\
(b_2,p+1) \text{ si } g \text{ está obstruída}
\end{matrix}\right.
Llamemos b_F a la bifurcación final. Calculando caminos mínimos en este grafo desde la bifurcación inicial, bastará ver con qué distancia desde la bifurcación inicial logramos alcanzar a los nodos (b_F,0); (b_F,1); (b_F,2). Obviamente, buscamos el que tenga distancia mínima y en caso de empate en distancias al que tenga menor cantidad de perforaciones.
Te dejo un link a la Charla de grafos del Nacional 2018, que creo que te puede ser útil para modelar y resolver este tipo de problemas. En la charla analizamos en detalle varios problemas similares a este. También la podés encontrar en Youtube en el canal de la olimpíada, que creo que te puede ser más fácil d seguir que solamente con las diapositivas (en el video también están incluídas las diapositivas). Recomiendo mirar ambos links para este problema, y en general recomiendo fuertemente las charlas de años anteriores, junto con la wiki.
También aprovecho y te dejo mi implementación de lo que digo, por si te sirve de ayuda.
Muchas gracias por la respuesta! Muy completa y bien explicada!
Pasando por cada uno de los puntos que marcaste:
Hacer eso en el for sé que no es ideal por lo que antes probé cambiar las condiciones y ponerlas en un mejor orden dentro del mismo. A causa de que las pruebas que hice no cambiaron el resultado, además de que creo que se veía mejor ponerlo todo inline como lo hice, no le presté atención. Es más, probé la entrada que proporcionaste y su funcionamiento lo veo completamente normal.
Efectivamente es ese el problema. No se me había ocurrido el caso pero tenía previamente en consideración que podía suceder. El hecho de la poca diferencia al puntaje completo me desconcenrtó a pensar que mi código tenía un problema menor, jeje. Originalmente creo que había intentado una solución DP-like, utilizando una estructura símil DFS para recorrer los caminos posibles intentando guardar toda la información necesaria cuando pasaba por los nodos, parecido a la idea de construir el grafo que proponés, aunque se me estaba complicando implementar, sumado a que cuando pensé en la posiblidad de guardar varias distancias en los nodos, creía que la complejidad se iría bastante. En eso me di cuenta que modificar un Dijkstra sería mucho más fácil, y descarté todo lo que antes había hecho para empezar de 0 con tal idea. El inconveniente justamente con el Dijkstra es la forma que va por los vértices, tipo BFS, que al fin y al cabo no va en profundidad para realmente ver la totalidad de un camino. En eso tengo que guardar más información por nodo sobre las galerías que describen como decís.
Lamentablemente no tuve mucho tiempo de analizarlo, pero me hice una cuenta auxiliar en el juez mientras se reestablece la original, y lo pude resolver aunque con un tiempo de ejecución bastante cerca del límite. Hice precisamente lo que sugerís, guardando de ser necesario, la mínima distancia de caminos que llegan a un nodo tal que tienen 0,1 o 2 perforaciones. Así al llegar a cierto nodo, verifico si ya existe un camino que haya pasado por el dicho con la cantidad correspondiente de perforaciones hipotéticas del camino que se describe y de ser menor el peso total hasta ese punto con respecto al que pasó, o de no haber pasado otro antes, meto al priority_queue el tramo, así seguiendo con las posibilidades individualmente y me quedaré con la mejor.
Claramente como no lo pude ver detalladamente le faltarían optimizaciones. Vi también en una pasada rápida tanto el PowerPoint de la charla como tu código, y tengo una noción de cómo mejorar mi solución, y aplicar mejor la idea de modelar un grafo con más información, en vez de tener estructuras aparte como es mi caso.
De todas formas dejo lo que pude resolver, y cuando tenga tiempo lo mejoro y aviso por el foro.
Repito, muchas gracias por la respuesta y lo bien que está armada!
Código solución pendiente de mejorar
#include <bits/stdc++.h>
#define forn(i,n) for(ll i = 0; i < ll(n); i++)
#define forsn(i,s,n) for(ll i = ll(s); i < ll(n); i++)
#define dforn(i,n) for (ll i = ll(n)-1; i >= 0; i--)
#define dforsn(i,s,n) for(int i = ll(n)-1; i >= ll(s); i--)
#define all(c) (c).begin(),(c).end()
#define fst first
#define snd second
#define FAST_IO ios::sync_with_stdio(false);cin.tie(nullptr);
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int> ii;
const int MAXN = 1e4+2;
struct nodo {
int v,d;
int obstruido;
bool operator< (const nodo &o) const{
return o.d < d;
}
};
vector<nodo> G[MAXN];
vi dist;
int B,g,O;
struct nodo_dijkstra {
int v,d;
int obstruido;
int cantObstruidos;
vector<ii> camino;
bool operator< (const nodo_dijkstra &o) const{
return o.d < d;
}
};
pair< vector<ii>, int > best = {{},-1};
void dijkstraBuscar (int st, vi &D, int nd) {
priority_queue<nodo_dijkstra> Q;
map<int,vi> caminObst;
Q.push({st,0,-1,0,{{st,-1}}});
D[st] = 0;
while (not Q.empty()) {
auto x = Q.top(); Q.pop();
if (x.v == nd) {
if (best.snd == -1 or x.d < best.snd) {
best.fst = x.camino;
best.snd = x.d;
continue;
}
}
//if (D[x.v] < x.d) continue;
for (auto &w : G[x.v]){
int obstruidos = x.cantObstruidos;
if (w.obstruido != -1) {
if (x.cantObstruidos >= 2) continue;
obstruidos++;
}
if (D[w.v] == -1 or D[w.v] > w.d + x.d) {
D[w.v] = w.d + x.d;
YES:
x.camino.push_back({w.v,w.obstruido});
Q.push({w.v, w.d+x.d, w.obstruido, obstruidos, x.camino});
x.camino.pop_back();
}
else {
if (not caminObst.count(w.v)) {
caminObst[w.v].resize(3,-1);
caminObst[w.v][obstruidos] = w.d + x.d;
goto YES;
}
if (w.d + x.d < caminObst[w.v][obstruidos] or caminObst[w.v][obstruidos] == -1) {
caminObst[w.v][obstruidos] = w.d + x.d;
goto YES;
}
}
}
}
}
int main() {
FAST_IO;
freopen("ciudad.in","r",stdin);
freopen("ciudad.out","w",stdout);
cin >> B >> g >> O;
forn (i,g) {
int a,b,p;
cin >> a >> b >> p;
G[a].push_back({b,p,-1});
G[b].push_back({a,p,-1});
}
dist.resize(B+2,-1);
forn (i,O) {
int a,b,p;
cin >> a >> b >> p;
G[a].push_back({b,p,(int)i+1});
G[b].push_back({a,p,(int)i+1});
}
dijkstraBuscar(1,dist,B);
vi obstruidos;
for (auto &i : best.fst) {
if (i.snd != -1) obstruidos.push_back(i.snd);
if (obstruidos.size() == 2) break;
}
if (!obstruidos.size()) cout << 1 << ' ';
else if (obstruidos.size() == 1) cout << 2 << ' ';
else if (obstruidos.size() == 2) cout << 3 << ' ';
forn (i,obstruidos.size())
cout << obstruidos[i] << ' ';
cout << dist[B];
return 0;
}
PD: De paso aproveché e hice un único Dijkstra en vez de dos. Tanto como antes contaba cuando usaba 1 o 2 galerías obstruidas, también podía hacerlo para 0 y ahorrarme el primer Dijkstra que hacía.
Sobre lo del for, cuando lo leí me hacía mucho ruido, y corrí tu código (el original del post) en ese ejemplo. Podría jurar que me tiraba error de que accedía con rango -1 en esa parte. En fin, me puedo estar equivocando (sobre todo, dado que eran largas horas de la madrugada).
Cualquier otra consulta no dudes en hacer un post. No prometo responder rápido (al menos no con buen nivel de detalle).
PD1:
Por lo menos una solución incorrecta no sacaba 100 puntos como pasaba con yurumí. Por suerte en los últimos años se corrige con puntaje por subtarea y no por caso.
PD2:
Podría jurar que me tiraba error de que accedía con rango -1 en esa parte
No sé si estás usando algunos flags adicionales al compilar. -D_GLIBCXX_DEBUG es re útil para mí y -Wshadow también. Hacen que muchos errores salten al tiempo de compilar (¡y no al enviar en el juez!). Para más información está este post en la wiki.
Bueno, veo que el foro y la wiki están de nuevo online así que puedo responderte que me había llegado el correo y no leí completamente la respuesta.
Cuando tuve más tiempo mejoré el código y decidí guardar por cada nodo del grafo, el mejor camino hasta él con 0,1 o 2 obstrucciones hasta ese punto. Entonces así podía saber que dada una cantidad de obstrucciones, cuál es el mejor camino con menor peso con dicha característica, ya que de seguir por el mismo nodo tendrían la misma restricción que algún otro de mismas obstrucciones previas utilizadas. Así, además, cuando veía que con un camino llegaba al final con un menor peso a un mejor previamente guardado, nomás me guardaba los caminos obstruidos utilizados. Y en unas submissions con eso pude bajarlo a 0.048s.
Lo único si ya lo hice con una cuenta con el nombre original que tenía porque vi el cartel en el juez, así que quedó una cuenta mía ahí que podría borrarse
Curiosamente cuando el juez estuvo abajo, quería ver ese problema y estoy luchando con el caso ese que agregaron, jeje. Me acordaba que había un post con una pista, pero no podía accederlo
De hecho no. Cuando se me superoponen variables me doy cuenta generalmente (aunque no inmediatamente) pero -D_GLIBCXX_DEBUG vendría re útil. Tengo que cuidarme con lo que dice que afecta la complejidad de ciertas STL, pero es bueno saber que existe y ayudar en ciertos casos donde es medio difícil encontrar el problema.
Esto es cierto, pero solo cuando corre localmente en tu máquina. El caso más común donde uno lo nota es que las operaciones que normalmente tardarían \mathcal{O}(\log(N)) en una priority_queue pasan a tardar \mathcal{O}(
N) porque hace muchas verificaciones extra. Lo importante es que al enviar a cualquier juez no hay problema, porque los jueces no corren con -D_GLIBCXX_DEBUG en sus opciones de compilación.
En algunas competencias, uno recibe los inputs y tiene que generar los outputs. En ese tipo de casos donde uno corre el código localmente en su máquina para generar los outputs sí es importante.
Claro, lo comprendo. Lo que digo que si bien no es muy acertado, a veces en base a cuanto tarda mi máquina en correr cierto programa o no, puedo creer que una solución entra o no en tiempo. Pero si te acostumbras, está bien, a excepción por supuesto de aquellos problemas output only como decís (que incluso en OIA veo ha habido problemas así), está más que bien.
Así que muchas gracias por los consejos y por la ayuda!
Hola,
Mi idea para este problema es crear tres tipos de nodo para cada nodo de mi grafo original.
El primer tipo son los nodos que no abren ninguna galería (numerados de 0 a 9999 en mi solución).
El segundo tipo son los que abren una (numerados de 10000 a 10999).
Y los terceros los que abren dos (de 20000 a 29999).
Las aristas las direcciono de la siguiente forma:
Cuando leo las G primeras aristas, agrego una arista entre u y v, una entre 10000+u y 10000+v y una entre 20000+u y 20000+v (todo 0-index ya que le resté uno a u y v previamente).
Luego, al leer las siguientes O aristas, agrego una entre 10000+u y 20000+v (indica que ya abrí una, y estoy abriendo esta) y una entre u y 10000+v (indica que no abrí ninguna, y abro esta).
Creo que el problema está en el direccionado de las aristas, sobre todo por el hecho de que agrego una al comienzo entre 10000+u y 10000+v y una entre 20000+u y 20000+v. Sin embargo, no logré encontrar un contraejemplo que me rompiera esta idea de conectarlas al comienzo sin importarme las que realmente están obstruidas.
Luego, hago un Dijkstra, y sé por la construcción de mi grafo que si min(dist(n), dist(10000+n), dist(20000+n)) = dist(n), entonces me conviene ir de 1 a n sin abrir ninguna galería. Si min(dist(n), dist(10000+n), dist(20000+n)) = dist(10000+n), entonces me conviene ir de 1 a n abriendo una galería.
Y si min(dist(n), dist(10000+n), dist(20000+n)) = dist(20000+n), me conviene ir de 1 a n abriendo dos galerías.
Luego, reconstruyo el camino de 1 a n, 10000+n ó 20000+n, según el caso anteriormente mencionado.
Mi implementación de esta parte no es muy linda, pero tampoco logré encontrar un caso que produzca un output incorrecto.
Mi idea es que una vez que tengo el camino, veo dos nodos adyacentes de este.
Si son de la pinta (10000+x, 20000+y) sé que esta galería está obstruida.
Lo mismo si son de la forma (x, 10000+y).
Corrí los casos que mencinó Guty arriba, y también andan.
Alguien me pordría explicar si el error está en la implementación o en la lógica empleada?
Este es mi código, me da 65.
PD: creo que no se necesita usar long long, pero en mi código está en todos lados . Hice un intento para ver si algún WA era por overflow (no lo son).
Hay 60.000 aristas, y cada una tiene peso hasta 10.000 según el enunciado. Es decir, que si la solución es un camino muuuy largo, podría pesar hasta 6 \cdot 10^4 \cdot 10^4 = 6 \cdot 10^8
Ese infinito parece muy chiquitito. Probá agrandarlo. El modelo y la lógica del problema están bien
Ahora Mañana edito y se vienen un par de comentarios de estilo de código. Eso de andar poniendo/copypasteando 10000 o 20000 está muy mal. Imaginate que en un lugar de tu código hubieras puesto un cero de menos
Van los comentarios prometidos a @ignaciocanta a su código:
Comentarios:
Repetir 10000 o 20000 en todos los lugares del código no está bueno. Una opción es usar el propio n del enunciado, y hacer que tus 3 tipos de nodos estén en los rangos [0,n); [n,2n); [2n,3n). Otra opción para hacer exactamente lo mismo que hacés es definir una variable con el valor que querés. Notar que si en vez de 10000 necesitaras poner un 10005 por alguna razón, de esta forma tendrías que cambiar un número en solo un lugar del código. Esto sería de forma similar a INF:
const tint MAXN = 10000; // MAXN -> el nombre que te guste
Al leer la entrada hay código repetido. Si querés fijate en mi código de más arriba como leer las galerías normales y las obstruidas todo de una. Igual creo que con simplemente llevar a una función del estiloagregar_arista(x,y,w)que agregue las aristas x \overset{w}{\to} y e y \overset{w}{\to} x queda mucho más claro, y trae menos errores.
Al escribir la salida hay código repetido. Entiendo que en chemin te guardás todo el camino. Si te fijás en el camino cuántas veces cruzaste galerías obstruidas primero, antes de separar en casos, y te las guardás en un vector, después la respuesta a los 3 casos es básicamente la misma. El largo de ese vector, imprimir lo que haya en el vector y luego la distancia mínima obtenida. Incluso en tu código así como está, podés simplemente poner cout << mini << "\n"<, al final y sin separar en casos esa parte (va a seguir estando toda la otra lógica repetida).
¿Por qué hace falta poner lo que cito a continuación en este caso? No hace falta, se puede borrar. Si te fijás, ya que separás en casos, en este caso solo se usan nodos entre [0,10.000) y [10.000,20.000) porque usaste una sola galería obstruida. Para mí de hecho, esa porción de código quedó por copy/paste del otro caso .
map<pair<tint,pair<tint,tint>>, tint> id Quizá utilizar algún struct puede ayudarte a no llevar en la cabeza qué significan los .first y los .second que viene al usar pairs. Sobre todo son de ayuda cuando usás pairs para cosas distintas. Por ejemplo, usando un struct podrías tener con el mismo esfuerzo algo del estilo map<Arista,tint> id que para el que lee es mucho más claro (hay un detalle, para usarlo como clave en un map vas a necesitar definirle el operator < a lo que definiste en el struct).
Si te fijás, en mi código de arriba medio que muestro un ejemplo de cómo hacer las cosas que te marco acá. Los comentarios son con onda, para que después en competencias cometas menos bugs, y en caso de cometerlos que te sea más fácil debuguear .
Insisto, la lógica del problema estaba perfecta de una .
Hola,
Gracias por los comentarios! De hecho, antes de publicar mi duda en el foro, el caso de ejemplo del enunciado me daba mal (y era por tener un 200000 camuflado con un 20000).
Con respecto a lo de la salida, inicialmente tenía otra idea, y se ve que quedó así y no lo cambié.
También había intentado hacer el map con struct, pero no sabía que había que declarar el operador < para poder usar map de struct .
.
. Por suerte en los últimos años se corrige con puntaje por subtarea y no por caso.
así que puedo responderte que me había llegado el correo y no leí completamente la respuesta.
.