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，然后乘第二辆公共汽车到6号公共汽车站。

为了解决这个问题，我们将遵循以下步骤-

• 定义一张映射

• 对于初始化i：= 0，当i <r的大小时，更新（将i增加1），执行-

• 在m [r [i，j]]的末尾插入i

• 对于初始化j：= 0，当j <r [i]的大小时，更新（将j增加1），执行-

• 定义一个队列q，将S插入q

• 如果S与T相同，则-

• 返回0

• 定义一组称为访问的

• 对于初始化lvl：= 1，如果非q为空，则更新（将lvl增加1），执行-

• node：= q的第一个元素，从q删除元素

• 对于初始化i：= 0，当i <m [node]的大小时，更新（将i增加1），执行-

• 将sz减1

• 停止：= r [路线，j]

• 如果stop与T相同，则-

• 返回lvl

• 忽略以下部分，跳至下一个迭代

• 路线：= m [节点，我]

• 如果访问过路线，则-

• 将路线插入已访问

• 对于初始化j：= 0，当j <r [route]的大小时，更新（将j增加1），执行-

• 在q中插入止损

• sz：= q的大小

• 当sz不为零时，执行-

• 返回-1

让我们看下面的实现以更好地理解-

示例

#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