牛客16444题解：BFS解决公交换乘问题

一、问题描述

牛客16444题要求计算从公交站点1到站点n的最少换乘次数。每次乘坐公交车可以到达该线路上的所有站点，换乘次数加1。

二、算法核心思想

采用广度优先搜索(BFS)方法：

1. 建立站点与公交车的双向映射关系

2. 使用队列进行BFS遍历

3. 记录每个站点的最小换乘次数

4. 通过公交车访问标记优化搜索过程

三、完整代码实现（带注释）

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
using namespace std;

const int INF = 1e9;  // 定义无穷大值

int main() {
    ios::sync_with_stdio(false);  // 加速输入输出
    cin.tie(nullptr);
    
    int n, m;  // n:站点总数 m:公交线路数
    cin >> n >> m;
    
    // 建立站点到公交车的映射
    unordered_map<int, vector<int>> station_to_buses;
    // 建立公交车到站点的映射
    vector<vector<int>> bus_to_stations(m);
    
    // 输入处理：构建双向映射
    for (int i = 0; i < m; ++i) {
        int t;  // 当前公交线路的站点数
        cin >> t;
        bus_to_stations[i].resize(t);
        for (int j = 0; j < t; ++j) {
            cin >> bus_to_stations[i][j];
            station_to_buses[bus_to_stations[i][j]].push_back(i);
        }
    }
    
    // BFS队列，存储{当前站点，花费}
    queue<pair<int, int>> q;
    q.push({1, 0});  // 从站点1出发，初始换乘次数为0
    
    // 记录站点最小花费
    vector<int> dist(n + 1, INF);
    dist[1] = 0;  // 起点距离为0
    
    // 记录已经访问过的公交车
    vector<bool> visited_bus(m, false);
    
    while (!q.empty()) {
        auto [station, cost] = q.front();
        q.pop();
        
        if (station == n) {  // 到达终点
            cout << cost << endl;
            return 0;
        }
        
        // 遍历当前站点能乘坐的所有公交车
        for (int bus : station_to_buses[station]) {
            if (visited_bus[bus]) continue;  // 跳过已访问的公交线路
            visited_bus[bus] = true;  // 标记已访问
            
            // 遍历该公交车能到达的所有站点
            for (int next_station : bus_to_stations[bus]) {
                if (dist[next_station] > cost + 1) {  // 发现更优路径
                    dist[next_station] = cost + 1;
                    q.push({next_station, cost + 1});
                }
            }
        }
    }
    
    cout << -1 << endl;  // 无法到达终点
    return 0;
}

四、关键点解析

1. 双向映射建立：

• station_to_buses：快速查询站点可乘哪些公交

• bus_to_stations：快速查询公交可达哪些站点

2. BFS优化：

• 公交车访问标记避免重复处理

• 距离数组剪枝减少无效搜索

3. 时间复杂度：

• 最坏情况O(n*m)，但实际运行效率很高

五、实际应用场景

1. 城市公交线路规划

2. 地铁换乘方案

3. 物流配送路径优化

4. 社交网络关系分析