TOPIC

5% de wrong answer

Tarlison Sander Lima Brito asked 1 year ago

Estou o dia todo procurando o porquê, mas eu não consigo descobrir os 5% de erro, alguém poderia me dar uma luz ?

#include<iostream>
#include<list>
#include<queue>
using namespace std;

int O, DESTINO, K;
int *proibidos;

class Grafo{

    int N_vertices;

    list<int> *adj;

    bool proibido(int v);

public:

    Grafo(int N_vertices);

    void addEdge(int v, int w);

    void BFS(int v);

    void BFSUtil(int v, bool *visitado, int *d);

};

Grafo::Grafo(int N_vertices) {
    this->N_vertices = N_vertices;
    adj = new list<int>[N_vertices];
}

bool Grafo::proibido(int v){
    for(int i = 0; i < K; i++){
        if(v == proibidos[i]){
            return true;
        }
    }
    return false;
}

void Grafo::addEdge(int v, int w){
    if(w < 1 || w > 100000)
        return;

    adj[v].push_back(w);
}

void Grafo::BFS(int v){
    bool *visitado = new bool[N_vertices];
    int *d = new int [N_vertices];

    for (int i = 0; i < N_vertices; i++){
        visitado[i] = false;
        d[i] = -1;
    }

    BFSUtil(v,visitado, d);

}

void Grafo::BFSUtil(int v, bool *visitado, int *d){
    queue<int> Q;
    int u;

    visitado[v] = true;
    d[v] = 0;
    Q.push(v);

    while(!Q.empty()){
        if(d[DESTINO] != -1){
            break;
        }
        u = Q.front();
        Q.pop();
        list<int>::iterator it;
        for(it = adj[u].begin(); it != adj[u].end(); ++it){
            if(!visitado[*it] && !proibido(*it) && d[*it] == -1){
                visitado[*it] = true;
                d[*it] = d[u] + 1;
                Q.push(*it);
            }
        }

    }

    cout << d[DESTINO] << endl;
}

int main(){
    Grafo controle(100001);

    for (int canais = 1; canais <= 100000; canais++){
        controle.addEdge(canais, canais * 3);
        controle.addEdge(canais, canais * 2);
        controle.addEdge(canais, canais + 1);
        if (canais % 2 == 0){
            controle.addEdge(canais, canais/2);
        }
        controle.addEdge(canais, canais - 1);

    }

    while (scanf("%d %d %d", &O, &DESTINO, &K)){
        if (O == 0 && DESTINO == 0 && K == 0)
            return 0;

        else{
            proibidos = new int[K];
            for(int i = 0; i < K; i++){
                scanf("%d", &proibidos[i]);
            }
            controle.BFS(O);
        }
    }

    return 0;
}

This topic has not been answered yet. Be the first!

Remember not post solutions. Your post may be reviewed by our moderators.