Tuyến xe buýt (Bus Routes) trong C++

Cho danh sách tuyến xe buýt routes[i] (xe i lặp lại tuyến này mãi mãi). Từ trạm S (chưa lên xe), tìm số xe ít nhất để đến trạm T. Trả về -1 nếu không thể.

Ví dụ

routes = [[1,2,8],[3,6,8]], S=1, T=6 → kết quả 2. Lên xe 0 đến trạm 8, chuyển xe 1 đến trạm 6.

Thuật toán BFS

1. Xây dựng map stop → danh sách tuyến xe qua trạm đó.
2. BFS từ trạm S, mỗi level = số xe đã dùng.
3. Từ trạm hiện tại, duyệt các tuyến xe chưa dùng, đánh dấu đã dùng, đẩy tất cả trạm trên tuyến đó vào hàng đợi.
4. Gặp T trả về level hiện tại.

Chương trình C++

#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
Kết quả
2