python/TangDou/AcWing_TiGao/T3/MiniPath/920.md

AcWing 920. 最优乘车

一、题目描述

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.第一个肯定有
scanf("%d", &stop[++cnt]);

// 2、下一个输入
// (1)换行键　ASCII 10
// (2)空格键　ASCII 32
// (3)最后一个输入结束 -1(EOF)
char ch = getchar();

// 3、如果读入的字符是空格，说明后面还有数字要读
while (ch == ' ') {
    // while (ch != EOF && ch != 10) { //这样写，与 ch==' '是等价的
    scanf("%d", &stop[++cnt]); //还有就继续读
    ch = getchar();            //为下一次做准备
}

三、算法分析

① 乘坐多少次车，与实际距离并没有关系，只要是同一次车，距离视为1 一趟车从S出发经过a,b,c可以到达T,可以理解为d[S][a]=1,d[S][b]=1,d[S][c]=1,d[S][T]=1

② 经过上面的转换 建图，可以 计算出S到T的最短路径，现实含义:乘车多少次。 乘坐过多少次车减1 就是 换乘多少次。

四、实现代码

#include <bits/stdc++.h>

using namespace std;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> PII;

const int N = 1e5 + 10, M = N << 1;

int n; // 总共有N个车站
int m; // 开通了M条单程巴士线路
int h[N], e[M], w[M], ne[M], idx;
int dis[N]; // 最小距离数组
bool st[N]; // 是否在队列中

int stop[N]; // 站点数组

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
void dijkstra() {
    memset(dis, 0x3f, sizeof dis);                    // 求最小设最大
    dis[1] = 0;                                       // 1到自己，乘车数0
    priority_queue<PII, vector<PII>, greater<PII>> q; // 小顶堆
    q.push({0, 1});                                   // 1号入队列

    while (q.size()) {
        auto t = q.top();
        q.pop();
        int u = t.second;
        if (st[u]) continue;
        st[u] = true;
        for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i];
            if (dis[v] > dis[u] + w[i]) {
                dis[v] = dis[u] + w[i];
                q.push({dis[v], v});
            }
        }
    }
}

int main() {
    memset(h, -1, sizeof h); // 初始化邻接表
    cin >> m >> n;           // 总共有N个车站,开通了M条单程巴士线路
    while (m--) {            // m条边
        // ① 先读入第一个数字
        int cnt = 0; // cnt一定要清零
        cin >> stop[++cnt];
        char ch = getchar();
        while (ch == ' ') {
            // ② 读入其它数字
            cin >> stop[++cnt]; // 还有就继续读
            ch = getchar();     // 为下一次做准备
        }
        // 这个建图建的妙啊！
        // 通过多条边，成功映射了问题，将一趟车问题转化为多个点之间边是1问题
        for (int i = 1; i <= cnt; i++)
            for (int j = i + 1; j <= cnt; j++)
                add(stop[i], stop[j], 1);
    }

    dijkstra();
    if (dis[n] == INF)
        puts("NO");
    else
        printf("%d\n", dis[n] - 1);
    return 0;
}