题目描述

blablabla

样例

blablabla

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<sstream>
#include<cstring>
#include<queue>
using namespace std;

const int N = 510;
bool g[N][N];
int dist[N];
int m, n;
int lines[N];

void bfs()
{
    memset(dist, 0x3f, sizeof dist);
    queue<int> q;
    q.push(1);
    dist[1] = 0;

    while(q.size())
    {
        auto t = q.front();
        if (t == n) break;
        q.pop();
        for (int i = 1; i <= n; i ++)
        {
            if (g[t][i] && dist[i] > dist[t] + 1)
            {
                dist[i] = dist[t] + 1;
                q.push(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) lines[cnt ++] = p;

        for (int i = 0; i < cnt; i ++)
            for (int j = i + 1; j < cnt; j ++)
                g[lines[i]][lines[j]] = true;
    }

    bfs();

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

}

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla