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