TOPIC

Ajuda com wrong answer

Rodrigo P S Sacchi asked 3 months ago

Olá a todos. Se for possível me ajudar, agradeço. Minha solução está com 5% de erros. Executei meu código com o uDebug usando o maior caso de teste dele, trazendo umas 14 linhas diferentes da minha. Acontece que o caso de teste do uDebug é gigante e eu não consegui entender qual tipo de grafo faz com que meu código dê os 5% de erros.

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

  • Aléxis Toigo replied 3 months ago

    Sem o código é dificil de saber o erro, porém pode ser utilizado o algoritmo de floyd warshall, cuidando com as condições do problema.

  • Rodrigo P S Sacchi replied 3 months ago

    
    // iPair ==>  Integer Pair 
    typedef pair<int, int> iPair; 
    
    int Dijkstra(int src, int dest, int numVertices)
    {
        priority_queue< iPair, vector <iPair> , greater<iPair> > pq; 
    
        // Create a vector for distances and initialize all 
        // distances as infinite (INT_MAX) 
        vector<int> dist(numVertices, INT_MAX); 
    
        // Todas as distâncias são infinitas, mas no vértice origem, 
        // a distância é zero.
        vertices[src].distancia = 0;    
    
        pq.push(make_pair(0, src)); 
        dist[src] = 0; 
    
        while(!pq.empty())
        {
            int u = pq.top().second;
            pq.pop();
    
            for(int line = 0; line < numVertices; line++)
            {
                // testando a segunda opc aqui no if.
                if(grafoG[u][line].eAdj == 1)
                {
                    int w = grafoG[u][line].peso;
                    //  If there is shorted path to v through u. 
                    if (dist[line] > dist[u] + w) 
                    { 
                        // Updating distance of v 
                        (grafoG[line][u].eAdj == 1) ? dist[line] = dist[u] + 0 : dist[line] = dist[u] + w;
                        vertices[line].distancia = dist[line];
                        vertices[line].predecessor = u;
                        pq.push(make_pair(dist[line], line)); 
                    } 
                }
            }
        }
        return dist[dest];
    }
    
  • Rodrigo P S Sacchi replied 3 months ago

    O URI não deixa eu postar o código.