C++のバス路線

バス路線のリストがあるとします。各ルート[i]には、i番目のバスが永遠に繰り返されるバスルートがあります。したがって、routes [0] =[1、5、7]の場合、これは、最初のバス（0番目のインデックス）が1、5、7、1、5、7、1、...の順序で永久に移動することを意味します。 。

ここで、最初はバスではなくバス停Sから出発し、バス停Tに行きたいとします。目的地に到着するために必要なバスの数を最小限に抑える必要がありますか？これが不可能な場合は、-1を返します。

したがって、入力が[[1,2,8]、[3,6,8]]のようで、S =1、T =6の場合、出力は2になります。したがって、最初のバスでバス停7に行きます。次に、2番目のバスに乗ってバス停6まで行きます。

これを解決するには、次の手順に従います-

• 1つのマップを定義するm
• iを初期化する場合：=0、i
• jを初期化する場合：=0、j
• m [r [i、j]]の最後にiを挿入します

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int numBusesToDestination(vector<vector<int>>& r, int S, int T) {
      unordered_map <int, vector <int> > m;
      for(int i = 0; i < r.size(); i++){
         for(int j = 0; j < r[i].size(); j++){
            m[r[i][j]].push_back(i);
         }
      }
      queue <int> q;
      q.push(S);
      if(S == T) return 0;
      unordered_set <int> visited;
      for(int lvl = 1; !q.empty(); lvl++){
         int sz = q.size();
         while(sz--){
            int node = q.front();
            q.pop();
            for(int i = 0; i < m[node].size(); i++){
               int route = m[node][i];
               if(visited.count(route)) continue;
               visited.insert(route);
               for(int j = 0; j < r[route].size(); j++){
                  int stop = r[route][j];
                  if(stop == T) return lvl;
                  q.push(stop);
               }
            }
         }
      }
      return -1;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{1,2,8}, {3,6,8}};
   cout << (ob.numBusesToDestination(v, 1, 6));
}

入力

{{1,2,8}, {3,6,8}}
1
6

出力

2