1

Fiz um código em C++ para resolver o problema URI 1270 Fibra Ótica. Fiz várias simulações e o código resolve o problema mas no ambiente do URI, a resposta é "Runtime Error". Alguém pode me ajudar a descobrir onde está o erro no código?

    /**
 * Created by Alexandre Miguel de Carvalho on 25/06/17.
 * orcid.org/0000-0002-8801-4321
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License.
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 */

#include <iostream>
#include <list>
#include <vector>
#include <limits>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <memory>
#include <algorithm>
#include <iomanip>
#include <exception>

using namespace std;

class AdjListGraph {

public:

    AdjListGraph() {
    }

    struct distancias{
        int cidade1;
        int cidade2;
        float_t distancia;

        bool operator() (distancias i, distancias j) { return  (i.distancia < j.distancia);}
    } D;

    vector<vector<distancias>> Md; //linha 0 distancia entre cidade0 e cidade1
    distancias dTemp;
    vector<distancias> linhaDaMatriz;


    float_t methodAMC(unsigned int numeroDistancias){

        float_t resultado = 0;
        vector<float_t > soma; //resultado das somas


        struct menorQueDist{
            bool operator()(float_t v1, float_t v2 ) const {
                return v1 > v2;
            }
        };

        vector<distancias> rootTree;


        for( vector<vector<distancias>>::size_type j = 0; j < Md[0].size(); j++){
            rootTree.push_back(Md[0][j]);
        }

        try {


            for (vector<vector<distancias>>::size_type i = 0; i < rootTree.size(); i++) {

                unsigned int di = 0;
                unsigned int k = 0;
                float_t s = 0;

                dTemp = rootTree.at(i);

                for (vector<vector<distancias>>::size_type di = 1; di < Md.size(); ++di) {
                    unsigned int tamanho = Md[di].size();

                    for (vector<vector<distancias>>::size_type j = 0; j < Md[di].size(); j++) {
                        if ((dTemp.cidade1 == Md[di][j].cidade1) ||
                            (dTemp.cidade1 == Md[di][j].cidade2) ||
                            (dTemp.cidade2 == Md[di][j].cidade1) ||
                            (dTemp.cidade2 == Md[di][j].cidade2)) {
                            s += dTemp.distancia + Md[di][j].distancia;
                            dTemp = Md[di][j];
                            break;
                        }
                    }
                }
                soma.push_back(s);
            }

        std::make_heap(soma.begin(), soma.end(),menorQueDist() );
        resultado = soma.front();
        soma.clear();
        rootTree.clear();

        }catch(exception &e) {
            cout << 0 << endl;
        }

        return resultado;

    }

};

int main() {

    unsigned int ID = 0;

    struct coordenadas{
        int X;
        int Y;
        string nomeDaCidade;
        unsigned int idVertice;
    };

    vector<coordenadas> latlong;

    std::map<string, vector<coordenadas>> listaCidades; //chave = nomeDaCidade
    std::map<string, vector<coordenadas>>::iterator itOrigem = begin(listaCidades);
    std::map<string, vector<coordenadas>>::iterator itDestino = begin(listaCidades);

    int N = 0;          //numero de cidades (vertices)
    int Ci = 0;
    string nomeCidade;
    string origem;
    string destino;
    int o; //origem
    int d; //destino
    float_t distancia = 0.0;
    int x1, y1, x2, y2;

    int x = 0;
    int y = 0;
    coordenadas temp;

    for (;;) {

        latlong.clear();
        listaCidades.clear();

        cin >> N;
        if (N == 0) return 0;
        unique_ptr<AdjListGraph> grafo (new AdjListGraph());

        for (int i = 1; i <= N; i++) {

            cin >> nomeCidade >> Ci;

            latlong.clear();

            for (int j = 1; j <= Ci; j++) {
                cin >> x >> y;
                temp.X = x;
                temp.Y = y;
                temp.idVertice = ID;
                temp.nomeDaCidade = nomeCidade+":"+std::to_string(x)+":"+std::to_string(y);
                ++ID;
                latlong.push_back(temp);
            }
            listaCidades.insert(make_pair(nomeCidade, latlong));
        }

        for(int k = 0; k < (N-1); k++) {

            grafo->linhaDaMatriz.clear();
            cin >> origem >> destino;

            itOrigem = listaCidades.find(origem);
            itDestino = listaCidades.find(destino);

            for(int indiceOrigem = 0; indiceOrigem < (*itOrigem).second.size(); indiceOrigem++){
                for(int indiceDestino = 0; indiceDestino < (*itDestino).second.size(); indiceDestino++){

                    x1 = (*itOrigem).second[indiceOrigem].X;
                    y1 = (*itOrigem).second[indiceOrigem].Y;
                    x2 = (*itDestino).second[indiceDestino].X;
                    y2 = (*itDestino).second[indiceDestino].Y;
                    distancia = sqrtf(pow(x1 - x2, 2) + pow(y1 - y2, 2));
                    o = (*itOrigem).second[indiceOrigem].idVertice;
                    d = (*itDestino).second[indiceDestino].idVertice;

                    grafo->dTemp.cidade1 = o;
                    grafo->dTemp.cidade2 = d;
                    grafo->dTemp.distancia = distancia;
                    grafo->linhaDaMatriz.emplace_back(grafo->dTemp);
                }
            }
            std::sort(grafo->linhaDaMatriz.begin(), grafo->linhaDaMatriz.end(), grafo->D );
            grafo->Md.emplace_back(grafo->linhaDaMatriz);
        }
        grafo->linhaDaMatriz.clear();

        try {

            cout << std::fixed << std::setprecision(1) << grafo->methodAMC(N-1) << endl;

        }catch (exception& e){
            cout << 0 << endl;
        }


        grafo->Md.clear();
        latlong.clear();

    }
    return 0;
}

Uma observação, já rodei o Valgrind e não foi detectado nenhum memory leak.

==17369== LEAK SUMMARY: ==17369== definitely lost: 0 bytes in 0 blocks ==17369== indirectly lost: 0 bytes in 0 blocks ==17369== possibly lost: 0 bytes in 0 blocks ==17369== still reachable: 72,704 bytes in 1 blocks ==17369== suppressed: 0 bytes in 0 blocks ==17369== ==17369== For counts of detected and suppressed errors, rerun with: -v ==17369== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

4
  • Uma observação, já rodei o Valgrind e não foi detectado nenhum memory leak. 13/07/2017 às 3:26
  • ==17369== LEAK SUMMARY: ==17369== definitely lost: 0 bytes in 0 blocks ==17369== indirectly lost: 0 bytes in 0 blocks ==17369== possibly lost: 0 bytes in 0 blocks ==17369== still reachable: 72,704 bytes in 1 blocks ==17369== suppressed: 0 bytes in 0 blocks ==17369== ==17369== For counts of detected and suppressed errors, rerun with: -v ==17369== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) 13/07/2017 às 3:28
  • primeiramente, obrigado pois eu ainda não conhecia o URIOnline, muito legal. Me inscrevi lá pra ver o que acontecia no seu código, mas enrolei e fui ver só hoje. Olhei o ranking da 1270 e é você mesmo em terceiro? Parabéns! Imagino que isso quer dizer que você já descobriu o problema? 21/07/2017 às 0:09
  • Nem tinha visto isto, rs. Precisava entregar a solução a um professor. 16/09/2017 às 23:53

0

Você deve fazer log-in para responder a esta pergunta.

Pesquise outras perguntas com a tag .