BFS，队列记录{当前站点、当前换车次数、当前所在线路} 注意：1.需要注意输入的处理 2.需要注意记录已经访问的状态{站点和线路}防止无限循环

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
const int N = 550;
int keda[N][N];//表示从某个站点到其他站点的可达线路
int m,n;
queue<pair<pair<int,int>,int>> qu;
bool visited[N][N]; // 标记站点和线路的组合是否已访问

int bfs()
{
    int answer=INT_MAX; // 初始化为最大整数值
    memset(visited, false, sizeof(visited)); // 初始化访问标记数组

    while(!qu.empty())
    {
        pair<int,int> x = qu.front().first;
        int xian = qu.front().second; // 当前所在车辆线路
        qu.pop();

        int a = x.first, b = x.second; // a是当前站点, b是当前换车次数

        if(a == n)
        {
            if(b < answer)
                answer = b;
            continue;
        }

        // 如果已访问过该状态，跳过
        if(visited[a][xian]) continue;
        visited[a][xian] = true;

        for(int i=1; i<=n; i++)
        {
            if(keda[a][i])
            {
                if(keda[a][i] == xian)
                    qu.push({{i, b}, xian}); // 同一线路，不增加换乘次数
                else
                    qu.push({{i, b+1}, keda[a][i]}); // 换乘，增加换乘次数
            }
        }
    }
    return answer == INT_MAX ? -1 : answer;
}

int main()
{
    cin >> m >> n; // m条路线，共n个站
    cin.ignore(); // 忽略输入缓冲区的换行符

    memset(keda, 0, sizeof(keda)); // 初始化可达矩阵

    // 修正输入解析部分
    for(int i=1; i<=m; i++)
    {
        string line;
        getline(cin, line);
        stringstream ss(line);
        vector<int> stations;
        int station;

        // 解析一行中的所有站点
        while(ss >> station) {
            stations.push_back(station);
        }

        // 构建可达矩阵：同一线路的站点间可达
        for(int j=0; j<stations.size()-1; j++) {
            for(int k=j+1; k<stations.size(); k++) {
                keda[stations[j]][stations[k]] = i; // 从j到k的线路为i
            }
            //keda[stations[j]][stations[j+1]]=i;
        }
    }

    // 初始化BFS队列，从站点1出发
    for(int i=1; i<=n; i++)
    {
        if(keda[1][i])
            qu.push({{i, 0}, keda[1][i]}); // 注意：初始换乘次数为0，直接进入下一站
    }

    int answer = bfs();
    if(answer == -1)
        cout << "NO";
    else 
        cout << answer;

    return 0;
}