AcWing 920. 最优乘车（单源最短路）

题目链接

920. 最优乘车 - AcWing题库高质量的算法题库https://www.acwing.com/problem/content/922/

来源

NOI1997

题解

在每一条巴士线路内部，将车站看成点，将每个车站与其它车站的线路看成边权为1的边，对整个图做一遍BFS就可以得到1号店到N号点的最短距离，减去1就是最少换乘次数。

代码

#include <cstring>
#include <iostream>
#include <algorithm>
#include <sstream>

using namespace std;

const int N = 510;

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

void bfs()
{
    int hh = 0, tt = 0;
    memset(dist, 0x3f, sizeof dist);
    q[0] = 1;
    dist[1] = 0;
    
    while (hh <= tt)
    {
        int t = q[hh++];
        
        for (int i = 1; i <= n; i++)
            if (g[t][i] && dist[i] > dist[t] + 1)
            {
                dist[i] = dist[t] + 1;
                q[++tt] = i;
            }
    }
}

int main()
{
    cin >> m >> n;
    
    string line;
    getline(cin, line);
    while (m--)
    {
        getline(cin, line);
        stringstream ssin(line);
        int cnt = 0, p;
        while (ssin >> p) stop[cnt++] = p;
        for (int j = 0; j < cnt; j++)
            for (int k = j + 1; k < cnt; k++)
                g[stop[j]][stop[k]] = true;
    }
    
    bfs();
    
    if (dist[n] == 0x3f3f3f3f) puts("NO");
    else cout << max(dist[n] - 1, 0) << endl;
    
    return 0;
}

参考资料

1. AcWing算法提高课