算法提高课汇总

模型抽象

• 顶点: 巴士🚌站

• 边: 以从本站上车能够直接到达的所有站作为建边依据. 例如🚌路线: $(4, 7, 3, 6)$, 则从$4$号
  巴士站分别向$7, 3, 6$建一条单向边, 表示从$4$号站台出发可以到达站台$7, 3, 6$, 边权为$1$. (即
  用$bool$值表示能否到达).同理, 从$7$号站台分别向$3, 6$站台建建权值为1的单向边. 依次类推.

按上述方式建图后, 从起点到终点的最短路径的含义是从起点出发乘车的最小次数, 与换乘次数相差$1$.

代码实现

由于边权为$1$, 可以用$bfs$解决.

注意: 需要考虑乘车次数为$0$的情况, 此时乘车次数和换乘次数相等.

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

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int m, n;
int dist[N], q[N];
int stop[N]; //保存巴士路线
bool g[N][N]; //g[u][v] = true: 从u上车可以直接到达v

void bfs()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    int tt = 0, hh = 0;
    q[tt ++] = 1;
    while( hh < tt )
    {
        int u = q[hh ++];
        for( int v = 1; v <= n; v ++ )
        {
            //由于dist[v]只会更新一次 不等式同时也判断v是否被访问过
            if( g[u][v] && dist[v] > dist[u] + 1 )
            {
                dist[v] = dist[u] + 1;
                q[tt ++] = v;
            }
        }
    }
}

int main()
{
    cin >> m >> n;
    string line;
    getline(cin, line); //读回车
    while ( m -- )
    {
        getline(cin, line);
        stringstream ssin(line); //将空格分割的string -> int
        int p, cnt = 0;
        while( ssin >> 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();
    if( dist[n] == INF )  puts("NO");
    else    cout << max(dist[n] - 1, 0) << endl;

    return 0;
}