dfs

先通过sstream把每行站点连边 （注意是单方向。。。）由左往右 在用一个数组存下每条边所在的路线

dfs搜索路线 如果走的路和上次不是同一条路线 就记录换乘一次 去最小值 最后判断是否能走通输出NO

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

using namespace std;

const int N = 1e5 + 10, M = N * 2;

#define x first
#define y second
typedef long long ll;
typedef pair<int,int> pii;

int t, n, m;
int h[N], e[N], ne[N], idx;
int w[1000][1000];

void add(int a,int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int dfs(int u,int fa,int path)
{
    if (u == n) {return path;}
    int res = N;
    for (int i = h[u]; i != -1; i = ne[i])
    {

        int j = e[i];
        if (j != fa)
        {
            if (st[j]) continue;
            st[j] = true;

            if (w[u][j] != w[fa][u])
            {
                res = min(res, dfs(j, u, path + 1));
            } 
            else
            {
                res = min(res, dfs(j, u, path));
            }

            st[j] = false;
        }

    }

    return res;
}

int main()
{
    cin >> m >> n;
    memset(h, -1, sizeof h);
    string str;
    getline(cin, str);
    int Id = 1;
    for (int i = 0; i < m; i ++ )
    {
        getline(cin, str);
        stringstream stream(str);
        int x, last = -1;
        while(stream >> x)
        {
            if (x == 1) w[1][1] = Id;

            if (last != -1)
            {
                w[last][x]  = Id;
                add(last, x);
            }
            last = x;
        }
        Id ++;
    }

    int res = N;
    res = min(res, dfs(1, 1, 0));

    if (res != N) cout << res << endl;
    else cout << "NO" << endl;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla