思路

建图 每个车站到达后面的车站的距离都是1
那么1到达n的最短距离就是转车次数+1

比如例题中
1到2 3 5 都是距离1
2到 1 3 5 都是距离1
1先到3 3再到7 就是1到7的最短距离
所以可以将一条线路上的可到达的车站之间的权设置为1, 不同的之间就为正无穷

C++ 代码

#include<iostream>
#include<queue>
#include<string>
#include<cstring>
#include<cmath>
using namespace std;
const int N = 10010;
int a[120][520], t[520];
typedef pair<int, int> PII;
queue<int> q;
int idx;
int h[N], e[N], ne[N], w[N];
bool s[520];

void add(int x, int y, int z)
{
    e[idx] = y;
    ne[idx] = h[x];
    w[idx] = z;
    h[x] = idx++;
}

void spfa(int m, int n)
{
    memset(t, 0x3f, sizeof(t));
    t[1] = 0;
    q.push(1);

    while(q.size())
    {
        int ver = q.front();
        q.pop();
        s[ver] = false;
        for(int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(t[j] >= t[ver] + w[i])
            {
                t[j] = t[ver] + w[i];
                if(!s[j])
                {
                    q.push(j);
                    s[j] = true;
                }
            }

        }
    }
}

int main()
{
    int m, n;
    cin >> m >> n;
    string s[110];
    getchar();
    memset(h, -1, sizeof(h));
    for(int i = 0; i < m; i++)
    {
        getline(cin, s[i]);
        s[i].push_back(' ');
        int c = 0;
        string cs;
        //字符串转换为数组操作
        for(auto j = s[i].begin(); j < s[i].end(); j++)
        {
            if(*j >= '0' && *j <= '9')
            {
                cs.push_back(*j);
            }
            if(*j == ' ')
            {
                c++;
                for(int ii = 0; ii < cs.size(); ii++)
                {
                    a[i][c] += (cs[ii] - '0') * pow(10, cs.size() - 1 - ii);
                }
                cs.clear();

            }
        }

        //建图
        for(int k = 1; k <= c; k++)
        {
           for(int j = k + 1; j <= c; j++)
           {
               add(a[i][k], a[i][j], 1);
           }
        }
    }

    spfa(m, n);

    if(t[n] == 0x3f3f3f3f) cout << "NO" << endl;
    else cout << t[n] - 1 << endl;

    return 0;
}