leetcode 困难题 815. Bus Routes 公交路线
Problem: 815. Bus Routes 公交路线
解题过程
抽象，不考虑站点的邻接表，更上一层的，考虑bus之间的邻接表
用每个站点做邻接表，然后用Dijkstra或者深度优先搜索dfs都超时了，或者超内存了。考虑到每辆bus在这个路径内都是联通的，所以每个bus做一个节点node，routes长度<500，每个bus写出邻接表，相比每个站点做邻接表，占用的内存大大减小，只需要考虑bus之间是否联通即可，不单独考虑站点之间。只要source所在的bus和target所在的bus是联通的即可，拿到最短路径就行了
bus之间是否相连的话，首先用哈希表存储每个站点的bus索引i的ump[routes[i][j]].insert(i);，这样每个站点的bus索引就拿到了，顺便存储source和target的索引，然后构造邻接表即可trr[p1].push_back(p2);， trr[p2].push_back(p1);。
因source可能存在于多个bus的索引内，所以从每个source可能的索引开始，都使用深度优先搜索，或者Dijkstra，这样target可能的索引的最短距离就是答案
Code
class Solution { public: vector<vector<pair<int, int>>> tr; vector<vector<int>> trr; vector<vector<bool>> status; unordered_map<int, int> ump; pair<int, int> point; int mi = INT_MAX; void dfs(vector<vector<int>>& routes, int source, int target, int ii, int jj) { int i, j, next; if(source == target) { mi = min(mi, (int)ump.size()); } status[ii][jj] = true; ump[ii]++; for(int k = 0; k < tr[source].size(); k++) { point = tr[source][k]; i = point.first; j = point.second; if(status[i][j] == false) { next = routes[i][j]; dfs(routes, next, target, i, j); } } status[ii][jj] = false; ump[ii]--; if(ump[ii]==0) { ump.erase(ii); } } unordered_set<int> tC, tmptmp; vector<int> ttCC; vector<bool> statusSTATUS; int minmin = INT_MAX; void dfsdfs(int start) { tmptmp.insert(start); if(tC.find(start) != tC.end()) { minmin = min(minmin, (int)tmptmp.size()); } statusSTATUS[start] = true; int next; for(int i = 0; i < trr[start].size(); i++) { next = trr[start][i]; if(statusSTATUS[next] == false) { dfsdfs(next); } } tmptmp.erase(start); statusSTATUS[start] = false; } int numBusesToDestination(vector<vector<int>>& routes, int source, int target) { if(source == target) return 0; trr.resize(routes.size()); statusSTATUS.assign(routes.size(), false); vector<int> sC; unordered_map<int, unordered_set<int>> ump; for( int i = 0; i < routes.size(); i++ ) { bool s = false, t = false; for( int j = 0; j < routes[i].size(); j++ ) { if(routes[i][j] == source) { sC.push_back(i); s = true; } if(routes[i][j] == target) { tC.insert(i); ttCC.push_back(i); t = true; } ump[routes[i][j]].insert(i); } // if(s == true && t==true) return 1; } unordered_set<int>::iterator it; unordered_map<int, vector<int>> umpump; for(auto [key, value] : ump) { for(it = value.begin(); it != value.end(); it++) { umpump[key].push_back(*it); } } int p1, p2; for(auto [key, value] : umpump) { for(int i = 0; i < value.size(); i++) { p1 = value[i]; p2 = value[(i+1)%(int)value.size()]; trr[p1].push_back(p2); trr[p2].push_back(p1); } } // for(int i = 0; i < sC.size(); i++) { // dfsdfs(sC[i]); // } // if(minmin==INT_MAX) return -1; // return minmin; // int ret = 0, mx = INT_MIN; // vector<pair<int, int>> sourceCOL; // for( int i = 0; i < routes.size(); i++ ) { // int n = routes[i].size(); // bool s = false, t = false; // for(int j = 0; j < n; j++) { // mx = max(mx, routes[i][j]); // if(routes[i][j]==source) s = true; // if(routes[i][j] == target) t = true; // if(s == true && t==true) return 1; // } // } // tr.resize(mx + 1); // for( int i = 0; i < routes.size(); i++ ) { // int n = routes[i].size(); // vector<bool> tmp(n, false); // status.push_back(tmp); // int p1, p2; // for(int j = 0; j < n; j++) { // p1 = routes[i][j]; // tr[p1].push_back(std::make_pair(i, (j+1)%n)); // // for(int k = j+1; k < n; k++) { // // p2 = routes[i][k]; // // tr[p1].push_back(std::make_pair(i, k)); // // tr[p2].push_back(std::make_pair(i, j )); // // } // if(routes[i][j] == source) { // sourceCOL.push_back({i, j}); // } // } // } // for(int i = 0; i < sourceCOL.size(); i++) { // dfs(routes, source, target, sourceCOL[0].first, sourceCOL[0].second); // } for(int ij = 0; ij < sC.size(); ij++) { vector<int> dis(routes.size()+1, INT_MAX); vector<bool> status(routes.size()+1, false); dis[sC[ij]] = 0; queue<vector<int>> qe; qe.push({0, sC[ij]}); int distance, next, start, i, j, d, mem; vector<int> tp; while(!qe.empty()) { tp = qe.front(); distance = tp[0]; start = tp[1]; qe.pop(); if(status[start] == true) continue; status[start] = true; for(int k = 0; k < trr[start].size(); k++) { next = trr[start][k]; if(status[next] == false && dis[next] > distance + 1) { qe.push({distance + 1, next}); dis[next] = distance + 1; } } } int jmi = INT_MAX; for(int j = 0; j < ttCC.size(); j++) { if(dis[ttCC[j]] != INT_MAX) { jmi = min(jmi, dis[ttCC[j]]); } } minmin = min(jmi, minmin); } if(minmin == INT_MAX) return -1; return minmin + 1; } };