错误答案 ACM A 节点太远

Question

我已经为问题“节点太远”问题 id uva 336 编写了代码。但是它给出了错误的答案，任何人都可以猜出我做错了什么。下面是我的代码。

问题的链接是 A Node too far

另外，如果有人可以告诉我什么是得到错误答案的常见原因，我们有什么方法可以知道我们的程序针对哪些输入产生了问题。

#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 决赛中，没有人会告诉你你失败的情况。