Các tuyến xe buýt trong C ++

Giả sử chúng ta có một danh sách các tuyến xe buýt. Trong mỗi tuyến [i] có một tuyến xe buýt mà xe buýt thứ i lặp lại mãi mãi. Vì vậy, nếu các tuyến đường [0] =[1, 5, 7], điều này có nghĩa là xe buýt đầu tiên (được lập chỉ mục thứ 0) đi theo trình tự 1, 5, 7, 1, 5, 7, 1, ... mãi mãi .

Bây giờ, giả sử chúng ta xuất phát ở bến xe buýt S, ban đầu không đi xe buýt, và chúng ta muốn đến bến xe buýt T. chúng ta phải tìm số xe buýt ít nhất mà chúng ta phải đi để đến đích? Nếu không được thì trả về -1.

Vì vậy, nếu đầu vào là [[1,2,8], [3,6,8]] và S =1, T =6, thì đầu ra sẽ là 2. Vì vậy, đi xe buýt đầu tiên đến bến xe buýt 7, sau đó bắt xe buýt thứ hai đến bến xe buýt số 6.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một bản đồ m
• để khởi tạo i:=0, khi i
• để khởi tạo j:=0, khi j
• chèn i vào cuối m [r [i, j]]

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int numBusesToDestination(vector<vector<int>>& r, int S, int T) {
      unordered_map <int, vector <int> > m;
      for(int i = 0; i < r.size(); i++){
         for(int j = 0; j < r[i].size(); j++){
            m[r[i][j]].push_back(i);
         }
      }
      queue <int> q;
      q.push(S);
      if(S == T) return 0;
      unordered_set <int> visited;
      for(int lvl = 1; !q.empty(); lvl++){
         int sz = q.size();
         while(sz--){
            int node = q.front();
            q.pop();
            for(int i = 0; i < m[node].size(); i++){
               int route = m[node][i];
               if(visited.count(route)) continue;
               visited.insert(route);
               for(int j = 0; j < r[route].size(); j++){
                  int stop = r[route][j];
                  if(stop == T) return lvl;
                  q.push(stop);
               }
            }
         }
      }
      return -1;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{1,2,8}, {3,6,8}};
   cout << (ob.numBusesToDestination(v, 1, 6));
}

Đầu vào

{{1,2,8}, {3,6,8}}
1
6

Đầu ra

2