We have a list of bus routes. Each routes[i] is a bus route that the i-th bus repeats forever. For example if routes[0] = [1, 5, 7], this means that the first bus (0-th indexed) travels in the sequence 1->5->7->1->5->7->1->... forever.
We start at bus stop S (initially not on a bus), and we want to go to bus stop T. Travelling by buses only, what is the least number of buses we must take to reach our destination? Return -1 if it is not possible.
Example: Input: routes = [[1, 2, 7], [3, 6, 7]] S = 1 T = 6 Output: 2 Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.Note:
1 <= routes.length <= 500.1 <= routes[i].length <= 500.0 <= routes[i][j] < 10 ^ 6.分析
对于这种从某处出发到某处的最短路径的问题，一般都需要采用BFS来做，BFS一般使用队列来实现。BFS在实现时需要考虑如何使用一个数据结构获取下一次搜寻的值。以本题为例，当达到某一站时，如何判断该站是否为换乘站，以及如何获取换乘的线路的各个站。
这里使用map<int, set<int>>用来保存stop 到route的映射。这样每次搜索到一站时，可以直接查询map获取可选择的route，然后通过set<int> visit判断该route是否已经被访问过，如果没有的话，就遍历该route的各个站，将其加入到队列中。
Code
class Solution { public: int numBusesToDestination(vector<vector<int>>& routes, int S, int T) { map<int, set<int>> m; for (int i = 0; i < routes.size(); i ++) { for (int j = 0; j < routes[i].size(); j ++) { if (m.find(routes[i][j]) == m.end()) { m.insert(make_pair(routes[i][j], set<int>())); } m[routes[i][j]].insert(i); } } set<int> visit; queue<pair<int, int>> q; q.push(make_pair(S, 0)); while (!q.empty()) { pair<int, int> tmp = q.front(); int pos = tmp.first; int num = tmp.second; q.pop(); if (pos == T) return num; set<int>::iterator iter; for (iter = m[pos].begin(); iter != m[pos].end(); iter ++) { int bus = *iter; if (visit.find(bus) != visit.end()) continue; visit.insert(bus); for (int j = 0; j < routes[bus].size(); j ++) { if (routes[bus][j] == pos) continue; q.push(make_pair(routes[bus][j], num+1)); } } } return -1; } };运行效率
Runtime: 260 ms, faster than 34.08% of C++ online submissions for Bus Routes.
Memory Usage: 45.9 MB, less than 46.24% of C++ online submissions for Bus Routes.
