1. 题目

我们有一系列公交路线。每一条路线 routes[i] 上都有一辆公交车在上面循环行驶。
例如，有一条路线 routes[0] = [1, 5, 7]，表示第一辆 (下标为0) 公交车会一直按照 1->5->7->1->5->7->1->… 的车站路线行驶。

假设我们从 S 车站开始（初始时不在公交车上），要去往 T 站。
期间仅可乘坐公交车，求出最少乘坐的公交车数量。
返回 -1 表示不可能到达终点车站。

示例:
输入: 
routes = [[1, 2, 7], [3, 6, 7]]
S = 1
T = 6
输出: 2
解释: 
最优策略是先乘坐第一辆公交车到达车站 7, 
然后换乘第二辆公交车到车站 6。

说明:
1 <= routes.length <= 500.
1 <= routes[i].length <= 500.
0 <= routes[i][j] < 10 ^ 6.

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/bus-routes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

class Solution {
public:
    int numBusesToDestination(vector<vector<int>>& routes, int S, int T) {
        if(S == T)//哈哈，又被坑了
            return 0;
        unordered_map<int,unordered_set<int>> station_line;//站点，线路
        unordered_map<int,unordered_set<int>> line_station;//线路，站点
        queue<int> q;//线路队列
        int n = routes.size(), line, station, step = 1, size;
        unordered_set<int> visitedStation;
        unordered_set<int> visitedLine;
        for(int i = 0, j; i < n; ++i)
        {
        	for(j = 0; j < routes[i].size(); ++j)
        	{
        		station_line[routes[i][j]].insert(i);
        		line_station[i].insert(routes[i][j]);
        		if(routes[i][j] == S)
        		{
        			q.push(i);//起点站的线路，都放进队列
        			visitedStation.insert(S);
        			visitedLine.insert(i);
        		}
        	}
        }
        while(!q.empty())
        {
        	size = q.size();
        	while(size--)
        	{
        		line = q.front();
        		q.pop();
        		if(line_station[line].count(T))
        			return step;//线路包含终点，返回
        		for(auto st = line_station[line].begin(); st != line_station[line].end(); ++st)
        		{	//查找这条线路经过的所有站
        			if(!visitedStation.count(*st))
        			{	//没访问过的站
        				visitedStation.insert(*st);
        				for(auto l = station_line[*st].begin(); l != station_line[*st].end(); ++l)
        				{	//这个站的所有未访问线路
        					if(!visitedLine.count(*l))
        					{
        						q.push(*l);
        						visitedLine.insert(*l);
        					}
        				}
        			}
        		}
        	}
        	step++;
        }
        return -1;
    }	
};

444 ms 59.5 MB