通報

Question

cin>>t; 

while (t--) 
{ 

    cin>>n; 
    cin>>m; 

    if (n==m) 
     cout<<"0\n"; 
    else 
    { 
     //Breadth First Search Tree: 
     queue <gnode*> gqueue; 

     bft_data bft=bft_data(); 


     list<gnode>* gp; 
     list<gnode>::iterator it; 

     gp=_gfind(graph,n);// finds list containing gnode with n value 
     gnode* st=gfind(gp,n),*tmp,*_st;//finds gnode with n value 
     _st=st; 

     bft.w[st->v]=0; 
     bft.pn[st->v]=NULL; 
     bft.c[st->v]=1; 

     gqueue.push(st); 

     while (!gqueue.empty()) 
     { 
      st=gqueue.front(); 
      gqueue.pop(); 

      gp=_gfind(graph,st->v); 

      it=(*gp).begin(); 
      for (++it;it!=(*gp).end();it++)//initialized with ++it to skip fist element of list 
      { 
       tmp=&(*it); 
       // cout<<tmp->v<<"\n"; 
       // getchar(); 
       if (bft.c[tmp->v]==0) 
       { 
        bft.pn[tmp->v]=st; 
        bft.c[tmp->v]=1; 
        bft.w[tmp->v]=bft.w[st->v]+1; 

        gqueue.push(tmp); 
       } 
      } 

     } 


     if(bft.w[m]!=SIZE) 
     cout<<bft.w[m]<<"\n"; 
     else 
     cout<<"Impossible\n"; 
bft.~bft_data(); 
    } 
} 

さらに、ループはそのvlaueを保持しながら、何とかBFTツリーは、外側の最初の反復で構成さtree.But BFSを構築することによって値とB/Wノードの距離を計算nおよびmにこのコードスニペット

class bft_data 
{ 
public: 
int w[SIZE],c[SIZE]; 
gnode* pn[SIZE]; 

bft_data() 
{ 
    memset(w,SIZE,SIZE); 
    memset(c,0,SIZE); 
    memset(pn,NULL,SIZE); 
} 

}; 

Answer 1

I：ループはここ

グラフはvector<list<gnode>>

BFSタイプのものであり、BFTに影響を与えないながらの反復は、クラスbft_dataの対象でありますmemsetの3番目の引数はバイト数なので、配列要素のサイズを掛けなければなりません。

memset(w,SIZE,SIZE * sizeof(int)); 
memset(c,0,SIZE * sizeof(int)); 
memset(pn,NULL,SIZE * sizeof (gnode*));