TOPIC

[Runtime Error] Todas as saídas testadas corretas

Felipe César L. Machado ( ☕ 🌠 ) asked 1 year ago

#include "bits/stdc++.h"
#define fr(inicio, fim) for(int i = inicio; i < fim; i++)

using namespace std;

vector<int> dt, rot; // Distancias e caminhos -> Dijkstra
vector<bool> visitado; // Para Dijkstra
vector< pair<int, int> > mark; // Arcos que se encontrarm nos menores caminhos
vector< list<int> > grafo; // Lista de adjacencias

struct classcomp {
  bool operator() (const int& lhs, const int& rhs) const
  { return dt[lhs] < dt[rhs]; } // Prioridade relativa ao menor caminho para Dijkstra
};

multiset<int, classcomp> menor; // Prioridade de vertice para Dijkstra
int edge[501][501], inicio, destino, v, e; // Matriz de adjacencia apenas para consulta (nao inicializada com valores nulos)

/* ===== bool dijkstra(int vertice) AQUI ===== */

void marca(int vertice){ // Marca os arcos do menor caminho
    if(vertice == inicio)
        return;
    mark.push_back(pair<int, int>(rot[vertice], vertice));
    return marca(rot[vertice]);
}

/*inicializa() dt e rot AQUI*/

int main ()
{

    while(cin >> v >> e && (v || e)){
        /*clear() e resize(v + 1) AQUI, para os containers criados*/

        cin >> inicio >> destino;
        fr(0, e){
            int x, y, d;
            cin >> x >> y >> d;
            grafo[x].push_back(y);
            edge[x][y] = d;
        }

        inicializa();
        bool res = dijkstra(inicio);
        int goal = dt[destino]; // Menor caminho
        marca(destino); // Marca todas as arestas do menor caminho
        grafo[rot[destino]].remove(destino); // Remove o ultimo arco

        if(res){
            do{
                inicializa();
                res = dijkstra(inicio);

                if(dt[destino] <= goal){ // Enquanto ha caminho de distancia igual ao menor
                    marca(destino); // Marca todos
                    grafo[rot[destino]].remove(destino); // Remove apenas o ultimo arco
                }
                else if(res) // Caso nao haja caminhos de comprimento igual ao menor
                {
                    for(auto elem : mark)
                        grafo[elem.first].remove(elem.second); // Remove todos os arcos marcados (pertencentes aos menores caminhos)
                    inicializa();
                    res = dijkstra(inicio);
                    break;
                }
            }while(res);
        }

        if(res)
            cout << dt[destino] << "\n";
        else
            cout << "-1\n";
    }

  return 0;
}

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

  • Vitor Vilela replied 1 year ago

    Pior que eu tentei fazer essa solução em C#, usando a minha própria lógica e consegui Answer Accepted de primeira sem muita dificuldade. Seus casos de teste do uDebug também funcionaram sem problema.

    Não tenho praticamente nenhuma experiência em C++, mas pelo que vejo talvez o problema possa estar na lista de adjacência, onde sem querer por algum probleminha no código pode acabar tentando remover um mesmo elemento duas vezes e assim lançando uma exceção. É uma hipótese claro, mas você pode tentar remover partes do seu código (mesmo que o seu algoritmo fique errado) e enviar no judge até que o Runtime Error suma e apareça um Wrong Answer. Alternativamente, jogar ifs em todos os lugares que podem lançar exceções e abortar o programa caso algo de errado seja detectado e assim ir testando até ver em que parte do código pode estar com problema. Fora isso, teremos que aguardar alguém com mais experiência em C++ pra lhe ajudar.

  • Felipe César L. Machado ( ☕ 🌠 ) replied 1 year ago

    Meu código bate com muitas saídas testadas mas dá Runtime Error não sei o porquê. Peguei os casos de teste no site da competição (coloquei no uDebug) e deu o mesmo. Porém testei com um input grande (500 vértices e quase 10.000 arestas) e não apresentou problema, além de ter dado a saída correta.

    Alguém consegue ver o porquê de Runtime Error?

    -> A ideia foi achar o menor caminho marcando todos os arcos, retirar o último arco e repetir o processo do menor caminho até que ele seja maior que o primeiro. Quando se encontra um caminho maior, retiro todos os arcos marcados e tento encontrar novamente o menor caminho.

    Agradeço!

    (Tive que comentar algumas partes do código porque ultrapassou o limite de caracteres da descrição).