LeetCode815.公交路线

公交路线"/>

LeetCode815.公交路线

题目链接:点这里
图类问题: 已知某些点之间是连通的, 求从一个点到另一个点的最短跳转距离(这里通过公交车进行跳转), 如果两个点不连通, 那么返回-1
解题步骤:

1. 有已知的出发站, 求得可以乘坐哪些车(这里需要个数据结构存放每个站由哪些车过, unordered_map<int, set>)
2. 根据这些车得知哪些站可以到达, 到达这些站, 并记录距离, 如果这个站已经到达过, 这不在记录(这里需要一个数据结构记录到这些站的距离unordered_map<int, int>)
3. 根据这些站得出可以乘坐的车, 如果有的车乘坐过, 那么直接排除, 不在乘坐(这里需要一个数据结构记录哪些车乘坐过, vector)
4. 重复步骤二

class Solution {
public:unordered_map<int, set<int>> m1;unordered_map<int, int> m2;queue<int> q;int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {vector<int> flag(routes.size(), 0);if (source == target) return 0;for (int i = 0; i < routes.size(); i++) {for (int j = 0; j < routes[i].size(); j++) {m1[routes[i][j]].insert(i);}}// cout << "2" << endl;for (auto i = m1[source].begin(); i != m1[source].end(); i++) {q.push(*i);flag[*i] = 1;}// cout << "3" << endl;int dis = 1;while (!q.empty()) {for (int i = q.size(); i > 0; i--) {int mid = q.front(); q.pop();for (int j = 0; j < routes[mid].size(); j++) {if (routes[mid][j] == target) return dis;if (m2.count(routes[mid][j])) continue;m2[routes[mid][j]] = dis;for (auto k = m1[routes[mid][j]].begin(); k != m1[routes[mid][j]].end(); k++) {if (flag[*k]) continue;q.push(*k);flag[*k] = 1;}}}dis++;}return -1;}
};