最优乘车

原题链接

题目描述

H 城是一个旅游胜地，每年都有成千上万的人前来观光。

为方便游客，巴士公司在各个旅游景点及宾馆，饭店等地都设置了巴士站并开通了一些单程巴士线路。

每条单程巴士线路从某个巴士站出发，依次途经若干个巴士站，最终到达终点巴士站。

一名旅客最近到 H 城旅游，他很想去 S 公园游玩，但如果从他所在的饭店没有一路巴士可以直接到达 S 公园，则他可能要先乘某一路巴士坐几站，再下来换乘同一站台的另一路巴士，这样换乘几次后到达 S 公园。

现在用整数 1,2,…,N 给 H 城的所有的巴士站编号，约定这名旅客所在饭店的巴士站编号为 1，S 公园巴士站的编号为 N。

写一个程序，帮助这名旅客寻找一个最优乘车方案，使他在从饭店乘车到 S 公园的过程中换乘的次数最少。

---

思路

关于建图

每行是一条公交线路，我们可以根据公交线路上各个点的先后顺序建图，即点 \(i\) 与 点 \(i+1,i+2,…,cnt\) 连边。

关于计算

换乘多少次 可以转换为 乘坐过多少次车➖1

1. 在同一条路线中，任意一个在此路线上的车站均能沿着该路线的方向到达后面的车站，权值都是1，表示只乘坐一次车。
2. 通过建图，由于权值均是1，使用bfs求出1号点到n号点最少乘过多少次车。

---

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 510;

int n, m;
int dist[N], stop[N];
bool g[N][N];

void bfs() {
    memset(dist, 0x3f, sizeof dist);
    queue<int> q;
    q.push(1);
    dist[1] = 0;

    while (!q.empty()) {
        int t = q.front();
        q.pop();

        for (int i = 1; i <= n; i++)
            if (g[t][i] && dist[i] > dist[t] + 1) {
                dist[i] = dist[t] + 1;
                q.push(i);
            }
    }
}

int main() {
    // ios::sync_with_stdio(0);
    // cin.tie(0); cout.tie(0);

    cin >> m >> n;
    getchar();

    string line;
    while (m--) {
        getline(cin, line);
        stringstream ss(line);

        int cnt = 0, p;
        while (ss >> p) stop[cnt++] = p;

        for (int i = 0; i < cnt; i++)
            for (int j = i + 1; j < cnt; j++)
                g[stop[i]][stop[j]] = true;
    }

    bfs();

    cout << (dist[n] == 0x3f3f3f3f ? "NO" : to_string(dist[n] - 1)) << endl;

    return 0;
}