地址 https://leetcode-cn.com/problems/bus-routes/
我们有一系列公交路线。每一条路线 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 <= 10^5. 0 <= routes[i][j] < 10 ^ 6.
解法
算法1
使用路线作为图的点 而不是车站
然后求多终点多起点的最短路径
制图和求最短路径上各有手法 有哈希有双指针遍历核对路线有无相同车站
时间差距较大,我的哈希代码使用了unordered_set 才勉强通过,直接set就TLE了
class Solution { public: vector<int> g[510]; unordered_set<int> stationOnLine[500]; int numBusesToDestination(vector<vector<int>>& routes, int S, int T) { if (S == T) return 0; for (int i = 0; i < routes.size(); i++) { for (const auto& e : routes[i]) { stationOnLine[i].insert(e); } } for (int i = 0; i < routes.size(); i++) { for (const auto& e : stationOnLine[i]) { for (int j = i + 1; j < routes.size(); j++) { if (stationOnLine[j].count(e) != 0) { //两者连边 g[i].push_back(j); g[j].push_back(i); } } } } vector<int> dis(routes.size(), INT_MAX); queue<int> q; for (int i = 0; i < routes.size(); i++) { if (stationOnLine[i].count(S) != 0) { //该路线包含起点站 放入队列中 q.push(i); dis[i] = 1; } } while (q.size()) { int u = q.front(); q.pop(); if (stationOnLine[u].count(T) != 0) { return dis[u]; } for (auto v : g[u]) { if (dis[v] > dis[u] + 1) { dis[v] = dis[u] + 1; q.push(v); } } } return -1; } };