C++：ツリー内の各ノードのペア間の距離を計算するためのBFS

Question

私は、Nの隣接リストの形で格納された重み付きツリーを持っています。私はM個のノードのリストを持っています。プログラムがコンパイルされないと、次のようにエラーがある

using namespace std; 
#define MAX_N (1<<17) 
#define MAX_V (1<<17) 

typedef pair<int,int> pii;  
vector<pii> adj[MAX_V]; 

bool vis[MAX_N]; //mark the node if visited 
ll bfs(pii s,pii d) 
{ 
    queue <pii> q; 
    q.push(s); 
    ll dist=0; 

    vis[ s.first ] = true; 
    while(!q.empty()) 
    { 
     pii p = q.front(); 
     q.pop(); 
     for(auto i = 0 ; i < adj[ p ].size() ; i++) 
     { 
      if(vis[ adj[ p ][ i ].first ] == false) 
      { 
       q.push(adj[ p ][ i ].first); 
       vis[ adj[ p ][ i ] ] = true; 
       dist += adj[p][i].second; 
      } 


     } 
    } 

    return dist; 
} 

int main() 
{ 

     for(int i=0;i<N;i++) 
     { 
      int v1,v2,l; 
      cin>>v1>>v2>>l; 
      adj[v1].push_back(make_pair(v2,l)); 
      // adj[v2].push_back(make_pair(v1,l)); 
     } 
     int a[M]; 
     for(int i=0;i<M;i++) 
     cin >> a[i]; 

     int ans=0; 


     for(int i=0;i<M-1;i++) 
     { 
      for(int j=i+1;j<M;j++) 
      { 
       num += bfs(adj[a[i]],adj[a[j]]); 
      } 
     } 

    } 

：

could not convert 'adj[a[i]]' from 'std::vector<std::pair<long long int, long long int> >' to 'pii {aka std::pair<long long int, long long int>}' 
       num += bfs(adj[a[i]],adj[a[j]]); 

私がこれを書いたこのツリーのMノードのリストからノードのすべてのペア間の距離を計算するために、今すぐ

また、デスティネーション頂点に到達しても停止していないので、このプログラムは間違っていることがわかります。

これらのエラーを修正するのに助けてくれる人がいますか？

Answer 1

私はいくつかの問題があると思う：

• for(auto i = 0 ; i < adj[ p ].size() ; i++)あなたはADJのための指標としてのpを使用しているが、pがタイプpiiです。対が意味を持つと仮定して、おそらくp.firstが必要です。
• if(vis[ adj[ p ][ i ].first ] == false)：隣人がまだ訪れていないかどうかを確認したいと思います。それでは、これ以上のものが必要です：vis[adj[p.first][i].second] == false。訪れた人のインデックスはadj[p.first][i].secondです。
• q.push(adj[ p ][ i ].first);：整数をプッシュしていますが、キューにはpiiの型が格納されています。あなたがどのようにそれを変更したいかをあなたに伝えましょう。
• dist += adj[p][i].second;：ペアを使用して配列のインデックスを作成しています。あなたは
はしかし問題のみコンパイルされているこれらの

Bucksterが既にコメントで説明したように、あなたがbfs関数にvector<pii>代わりのpiiを渡しているnum += bfs(adj[a[i]],adj[a[j]]);最後にインデックス

を使用する必要があります。あなたのアルゴリズムがあなたが期待していることを実際に行っているかどうかはわかりません。 bfsを使って任意の数のノード間の距離を計算することができますが、重み付けされていれば、bfs自体が最小のパスを与えるわけではありません。最小パスに興味がある場合は、ダイクストラを使用することができます（重みが正である場合）。 Here私はあなたが望むなら、あなたがここで何をしようとしているのか少しだけ複雑な、あなたが確認できるbfs実装を持っています。