当前位置：首页 > 牛客 > 牛客16444题解析：公交线路最短路径算法优化（BFS+双向映射）

牛客16444题解析：公交线路最短路径算法优化（BFS+双向映射）

2个月前 (09-05)

一、题目解读

本题要求求解一个公交线路网络中的最短路径问题：给定n个站点和m条公交线路，每条线路包含多个站点，求从起点站1到终点站n的最小换乘次数。题目需高效处理站点与线路的双向关联，并优化路径搜索效率。

二、解题思路

采用双向映射+BFS的解题策略：

1. 构建双向映射：使用station_to_buses（站点→线路）和bus_to_stations（线路→站点）两个数据结构，快速获取某站点可乘坐的公交车及某公交车途经的站点。

2. BFS搜索：从起点1开始，逐层扩展可达站点，每次仅考虑未访问过的公交车，避免重复计算换乘次数。

3. 状态标记：用visited_bus数组记录已访问的公交车，确保每条线路仅被遍历一次，降低时间复杂度。

三、解题步骤

1. 输入与初始化：读取n、m及线路信息，建立双向映射。

2. BFS搜索：

○ 队列初始化：起点站{1, 0}入队，dist[1]=0。

○ 循环直至队列为空：

出队当前站点和花费cost。

若到达终点n，输出cost并结束。

遍历该站可乘坐的所有公交车：

若公交车未访问，标记visited_bus[bus]=true。

遍历该公交车途经的所有站点next_station：

○ 更新最小花费dist[next_station] = cost + 1，并入队{next_station, cost + 1}。

3. 输出结果：若未找到路径，输出-1。

四、代码与注释

#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});  // 起点入队

    // 记录各站点的最小花费（初始化为INF）
    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;
}