题解 | #公交车#

公交车

https://www.nowcoder.com/practice/630816b6884f4ad49590b6c07bab40fc

解题思路

这是一道使用BFS求解最短路径的问题，主要思路如下：

问题分析：
- $n$ 个公交站点， $m$ 条公交线路
- 每条线路经过若干站点
- 每次乘坐花费1元
- 求从1号站到 $n$ 号站的最少花费
解决方案：
- 构建双向图：站点和公交线路都作为节点
- 站点与经过它的公交线路之间建立边
- 使用BFS寻找最短路径
- 最终结果需要除以2（来回算两次）
关键点：
- 图的节点包括站点和公交线路
- 一次完整乘车需要两步：上车和下车
- 需要处理无法到达的情况

代码

cpp
java
python

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

int main() {
    int n, m;
    cin >> n >> m;
    
    // 建图：n个站点 + m条线路
    vector<vector<int>> graph(n + m + 1);
    
    // 读入每条线路经过的站点
    for (int i = 1; i <= m; i++) {
        int t;
        cin >> t;
        for (int j = 0; j < t; j++) {
            int station;
            cin >> station;
            // 站点和线路之间建立双向边
            graph[station].push_back(n + i);
            graph[n + i].push_back(station);
        }
    }
    
    // BFS求最短路径
    vector<int> dist(n + m + 1, -1);
    queue<int> q;
    q.push(1);
    dist[1] = 0;
    
    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        
        // 遍历相邻节点
        for (int next : graph[curr]) {
            if (dist[next] == -1) {
                dist[next] = dist[curr] + 1;
                q.push(next);
            }
        }
    }
    
    // 输出结果
    if (dist[n] == -1) {
        cout << -1 << endl;
    } else {
        cout << dist[n] / 2 << endl;
    }
    
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        // 建图：n个站点 + m条线路
        ArrayList<Integer>[] graph = new ArrayList[n + m + 1];
        for (int i = 0; i <= n + m; i++) {
            graph[i] = new ArrayList<>();
        }
        
        // 读入每条线路经过的站点
        for (int i = 1; i <= m; i++) {
            int t = sc.nextInt();
            for (int j = 0; j < t; j++) {
                int station = sc.nextInt();
                // 站点和线路之间建立双向边
                graph[station].add(n + i);
                graph[n + i].add(station);
            }
        }
        
        // BFS求最短路径
        int[] dist = new int[n + m + 1];
        Arrays.fill(dist, -1);
        Queue<Integer> q = new LinkedList<>();
        q.offer(1);
        dist[1] = 0;
        
        while (!q.isEmpty()) {
            int curr = q.poll();
            
            // 遍历相邻节点
            for (int next : graph[curr]) {
                if (dist[next] == -1) {
                    dist[next] = dist[curr] + 1;
                    q.offer(next);
                }
            }
        }
        
        // 输出结果
        if (dist[n] == -1) {
            System.out.println(-1);
        } else {
            System.out.println(dist[n] / 2);
        }
    }
}

from collections import defaultdict, deque

def solve():
    # 读入站点数和线路数
    n, m = map(int, input().split())
    
    # 建图：使用邻接表存储
    graph = defaultdict(list)
    
    # 读入每条线路经过的站点
    for i in range(1, m + 1):
        line = list(map(int, input().split()))
        t = line[0]  # 站点数
        stations = line[1:]  # 站点列表
        
        # 站点和线路之间建立双向边
        for station in stations:
            graph[station].append(n + i)
            graph[n + i].append(station)
    
    # BFS求最短路径
    dist = [-1] * (n + m + 1)
    q = deque([1])
    dist[1] = 0
    
    while q:
        curr = q.popleft()
        
        # 遍历相邻节点
        for next_node in graph[curr]:
            if dist[next_node] == -1:
                dist[next_node] = dist[curr] + 1
                q.append(next_node)
    
    # 输出结果
    print(-1 if dist[n] == -1 else dist[n] // 2)

# 主程序
if __name__ == "__main__":
    solve()