間違った答えACM Aノードがあまりにも遠い

Question

私は問題 "Aノードが遠い"問題IDのコードを書いた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個の改行文字を追加して出力します。そうでない場合でもコードが間違っていても、これは間違った答えになります。

はここで少ない労力で、この特定の問題を解決する方法についての二つのアプローチです：

あなたがする必要があるすべてのノードのグラフを構築し、クエリ内のノードからbreadth first searchを実行することです。その後、最初のノードまでの最短距離が指定されたしきい値（TTL）を超えるすべてのノードをカウントします。

ノードの数が実際には少ない（最大30個）ため、代わりの解決方法はFloyd Warshallアルゴリズムを実行することです。このソリューションはさらに短くなりますが、ずっと大きな制約のためには機能しません。

両方のアプローチは、50行以下で簡単に適合します。

WAを持つテストを見つける方法の1つのアプローチは、任意のグラフを生成し、任意の2つのノード間のパッケージの動きをシミュレートし、その結果をプログラムで見つけたものと比較することです。常に小さな例を生成してください！この場合、最大5ノードまでは十分です。

私が一般的に好む第2のアプローチは、グラフを手作業で生成し、期待される答えを手で計算することです。できるだけ多くのエッジケースをカバーしてください（ネットワーク内の単一ノード、すべてのノードに到達可能、TTLは0など）。 オンライン審査員の中には、あなたのコードが失敗したケースと、UVAがそのケースではないケースを確認するオプションがあります。これは目的のために実行されます。プログラムを自分で試してデバッグする必要があります。また、ACM決勝では、誰もあなたが失敗しているケースを教えてくれることはありません。