920 最优乘车（抽象--＞单源最短路径）

野性酷女 2022-09-16 03:41 150阅读 0赞

**1. 问题描述：**

H 城是一个旅游胜地，每年都有成千上万的人前来观光。为方便游客，巴士公司在各个旅游景点及宾馆，饭店等地都设置了巴士站并开通了一些单程巴士线路。每条单程巴士线路从某个巴士站出发，依次途经若干个巴士站，最终到达终点巴士站。一名旅客最近到 H 城旅游，他很想去 S 公园游玩，但如果从他所在的饭店没有一路巴士可以直接到达 S 公园，则他可能要先乘某一路巴士坐几站，再下来换乘同一站台的另一路巴士，这样换乘几次后到达 S 公园。现在用整数 1，2，…N 给 H 城的所有的巴士站编号，约定这名旅客所在饭店的巴士站编号为 1，S 公园巴士站的编号为 N。写一个程序，帮助这名旅客寻找一个最优乘车方案，使他在从饭店乘车到 S 公园的过程中换乘的次数最少。

**输入格式**

第一行有两个数字 M 和 N，表示开通了 M 条单程巴士线路，总共有 N 个车站。从第二行到第 M+1 行依次给出了第 1 条到第 M 条巴士线路的信息，其中第 i+1 行给出的是第 i 条巴士线路的信息，从左至右按运行顺序依次给出了该线路上的所有站号，相邻两个站号之间用一个空格隔开。

**输出格式**

共一行，如果无法乘巴士从饭店到达 S 公园，则输出 NO，否则输出最少换乘次数，换乘次数为 0 表示不需换车即可到达。

**数据范围**

1 ≤ M ≤ 100，  
1 ≤ N ≤ 500

**输入样例：**

3 7  
6 7  
4 7 3 6  
2 1 3 5

**输出样例：**

2  
来源：[https://www.acwing.com/problem/content/description/922/][https_www.acwing.com_problem_content_description_922]

**2. 思路分析：**

分析题目可以知道这道题目求解的不是从起点到终点的最短路径，而是求解从起点到终点的最少换乘次数(这个比较恶心一点)，其实我们先画画图观察一下其中的规律，以题中的例子为例：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_13_color_FFFFFF_t_70_g_se_x_16][]

可以发现我们可以先求解出需要坐车的最少次数，坐车的最少次数减1就是换乘的最少次数，因为需要结合最短路径问题，所以我们可以往如何将题目的模型转换为最短路模型去想，可以发现每一个点可以往与后面有联系的点连一条边（这一点是关键），这样就可以将原问题转化为了最短路径问题，求起点到终点的最少坐车次数相当于是求解从起点到终点的最短路径，其中每一条边的权重都是1，所以可以直接使用bfs即可，先搜到终点的路径肯定是最短路径，所以题目的核心在于建图的过程。

**3. 代码如下：**

from typing import List
    
    
    class Solution:
        def bfs(self, s: int, n: int, g: List[List[int]]):
            INF = 10 ** 10
            # 一开始的距离都是正无穷, dis既可以求解最短距离又可以充当判重数组
            dis = [INF] * (n + 1)
            # 起点的距离为0
            dis[s] = 0
            q = [0] * (n + 1)
            # 队列中的编号为起点
            q[0] = s
            hh, tt = 0, 0
            while hh <= tt:
                # 相当于弹出队首元素
                p = q[hh]
                hh += 1
                # 枚举邻接表
                for next in g[p]:
                    if dis[next] > dis[p] + 1:
                        dis[next] = dis[p] + 1
                        tt += 1
                        # 入队
                        q[tt] = next
            return dis[n]
    
        def process(self):
            m, n = map(int, input().split())
            # 每一个g[i]相当于是一个邻接表而且只存编号即可
            g = [list() for i in range(n + 1)]
            for i in range(m):
                t = list(map(int, input().split()))
                for j in range(len(t)):
                    for k in range(j + 1, len(t)):
                        g[t[j]].append(t[k])
            res = self.bfs(1, n, g)
            INF = 10 ** 10
            if res == INF: return "NO"
            # 这里需要注意起点与终点可能是同一个点所以减去1可能是负数所以与0取一个max
            return max(0, res - 1)
    
    
    if __name__ == "__main__":
        print(Solution().process())

[https_www.acwing.com_problem_content_description_922]: https://www.acwing.com/problem/content/description/922/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_13_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/2995e1f8a68f4a6c82890714074f85ba.png