Acortando el camino

Buenas, anduve intentando resolver el problema “Acortando el camino” de Selectivo del año 2012. Link al problema: http://juez.oia.unsam.edu.ar/#/task/ciudad/statement

Mi idea es la siguiente:

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;
    }
1 me gusta

Yo veo dos problemas en tu solución:

  1. 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.
  2. 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 :smile:.
Saludos!

3 Me gusta

Gracias por la ayuda! Ahora veo el código y corrijo los errores.

1 me gusta