Неправильный ответ ACM Узел слишком далеко

Question

Я написал код для задачи «Узел слишком далеко». Id id uva 336. Но он дает неправильный ответ, может кто-нибудь догадаться, что я делаю неправильно. Ниже мой код.

Ссылка на проблему: Узел слишком далеко

Кроме того, если кто-то может сказать мне, каковы общие причины получения неправильного ответа и есть ли какой-то способ, которым мы знаем, на чьей основе наша программа создает проблемы.

#include <iostream>
#include <vector>
#include <list>
#include <map>

unsigned int caseID = 0;
struct Edge;

struct Node{
   Node():id(0),cost(0),color(false),added(false){}
   int id;
   int cost;
   bool color;
   bool added;
   std::list<Edge *>edges;
};
struct Edge{
 Edge():destination(0){}

 Node *destination;
};


void make_graph(unsigned int sourceid,unsigned int destinationid,
    std::map<int, Node*> &mymap, int &totalNodes){
    Node *source = 0;
    Node *destination = 0;

    std::map<int, Node*>::iterator it = mymap.find(sourceid);
    if(it == mymap.end()){
     source = new Node;
     ++ totalNodes;
     source->id = sourceid;
     mymap.insert(std::pair<int,Node*> (sourceid,source));
   }
   else{
     source = it->second;
   }
   if(sourceid == destinationid){
     return;
   }

   it = mymap.find(destinationid);
   if(it == mymap.end()){
      ++totalNodes;
      destination = new Node;
      destination->id= destinationid;
      mymap.insert(std::pair<int,Node*> (destinationid,destination));

   }
   else{
      destination = it->second;
   }

   Edge *e = new Edge;
   e->destination = destination;
   source->edges.push_back(e);

   e = new Edge;
   e->destination = source;
   destination->edges.push_back(e);

 }



  void delete_graph(std::map<int, Node*> &mymap){
     std::map<int,Node*>::iterator it = mymap.begin();
     for(;it != mymap.end(); ){

       Node *n = it->second;
       if(!n){
         continue;
       }
       std::list<Edge *>::iterator myEdge = it->second->edges.begin();

          while(myEdge != n->edges.end()){
          Edge *e = *myEdge;
          if(e){
          e->destination = 0;
          delete e;
          e = 0;
          }
          ++myEdge;
       }
       delete n;
       n = 0;
       ++it;
       std::cout << std::endl;
      }
    }


      void calc_nodes(int value, Node *n, unsigned int &nodesCount, int prevCost){

        if(!n->added){
          n->cost = ++prevCost;
          if(n->cost == value){
           ++nodesCount;
           n->added = true;
           return;
         }
          ++nodesCount;
          n->added = true;

         }else{
           n->cost =  ++prevCost;
          }

        std::list<Edge *>::iterator it = n->edges.begin();
        while(it != n->edges.end()){
            Edge *e = *(it);
             if(e->destination->color){
                ++it;
                continue;
             }

           n->color = true;
           e->destination->color = true;
           calc_nodes(value,e->destination,nodesCount,n->cost);
           ++it;
        }

     }

     void clearGraph(std::map<int, Node *>& mymap ){
            std::map<int, Node *>::iterator it = mymap.begin();
            while(it != mymap.end()){
               it->second->added = false;
               it->second->color = false;
               ++it;
            }
    }

     void calc_nodes_aux(int totalNodes,std::map<int,Node *> &mymap){
         unsigned int TTL = 0;
         Node *source = 0;
         unsigned int sourceId = 0;
          unsigned int nodesCount = 0;
         while(true){
           std::cin >> sourceId >>TTL;
              if(sourceId == 0 && TTL == 0){
                   break;
              }    
          std::map<int,Node *>::iterator it = mymap.find(sourceId);
          source = it->second;

          if(source && TTL > 0){
             nodesCount = 0;
             clearGraph(mymap);
             calc_nodes(TTL,source,nodesCount, -1);
             if(caseID > 0){
                    std::cout <<std::endl;
             }
            std::cout << "Case "<< ++caseID<<": " <<totalNodes - nodesCount <<
       " nodes not reachable from node " <<sourceId << " with TTL = " << TTL<<".";
            }
           }
          }
       int main(){

            unsigned int edges = 0;
            unsigned int sourceId = 0;
             unsigned int destinationId = 0;
             while(true){
               std::cin >>edges;
                if(edges == 0){
                  break;
                } 
               std::map<int,Node*>mymap;
                int totalNodes = 0;
               for(unsigned int i = 0; i < edges; ++i ){
                    std::cin >> sourceId >> destinationId;
                    make_graph(sourceId,destinationId,mymap,totalNodes);
               }
              calc_nodes_aux(totalNodes,mymap);
              delete_graph(mymap);
          }
          return 0;
      } 

Answer 1

Ваш код чрезвычайно сложен для поставленной задачи, и вы даже не пройдете тестовый пример! Обратите внимание, что в (почти всех) онлайн-судьях вы должны производить вывод, который будет таким же побайтным, как и ожидаемый. Вы выводите около 10 дополнительных символов новой строки после первого контрольного примера, и даже если ваш код верен, это приведет к неправильному ответу.

Вот два подхода к решению этой конкретной проблемы с меньшими усилиями:

Все, что вам нужно сделать, это построить график узлов, а затем запустить поиск в ширину из узла в запросе. После этого подсчитайте все узлы, у которых их кратчайшее расстояние до исходного узла больше заданного порогового значения (TTL).

Поскольку число узлов действительно мало (до 30), альтернативным решением было бы запустить алгоритм Floyd Warshall . Это решение будет еще короче, но не будет работать для гораздо больших ограничений.

Оба подхода могут легко уместиться менее чем в 50 строк.

Один из подходов к определению, какой у вас тест WA, состоит в том, чтобы попытаться сгенерировать случайные графики и смоделировать перемещение пакетов между любыми двумя узлами и сравнить результат с результатом, найденным вашей программой. Всегда генерируйте маленькие примеры! В этом случае я считаю, что до 5 узлов более чем достаточно.

Второй подход, который я обычно предпочитаю, - это создавать графики вручную и снова вычислять ожидаемый ответ вручную. Постарайтесь охватить как можно больше граничных случаев (один узел в сети, все узлы достижимы, TTL равен 0 и т. Д.). В онлайн-судье лишь немногие предлагают возможность увидеть, в каком случае ваш код не выполняется, а UVA не является одним из них. Это сделано для определенной цели - это заставляет вас пытаться отлаживать вашу программу самостоятельно. Кроме того, в финале ACM никто не собирается рассказывать вам о том, что вы проиграли.