BFS

参考代码

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

using namespace std;

const int N = 510;

bool g[N][N];
int n, m, dist[N], path[N];

/*
时间复杂度：主要在建图，m*n^2
*/

void bfs(){
    queue<int> q;
    q.push(1);
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    while(q.size()){
        int t = q.front();
        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;
    getchar();
    while(m --){
        string str;
        getline(cin, str);
        // 使用sstream处理一行数据
        stringstream sin(str);
        int cnt = 0, s;
        // 将一行数据按照空格读到s
        while(sin >> s) path[cnt ++] = s;
        // 一条线路前到后连一条边
        for(int i = 0; i < cnt; i ++)
            for(int j = i + 1; j < cnt; j ++)
                g[path[i]][path[j]] = true;
    }
    bfs();
    if(dist[n] == 0x3f3f3f3f) cout << "NO" << endl;
    // 自认为无需max(dist[n] - 1, 0)，dist[n]不会更新到比0小
    else cout << dist[n] - 1 << endl;
    return 0;
}

Dijkstra

参考代码

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

using namespace std;

const int N = 510;

int g[N][N], vis[N];
int n, m, dist[N], path[N];

/*
时间复杂度：主要在建图，m*n^2
*/

void dijkstra(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for(int i = 0; i < n; i ++){
        int t = -1;
        for(int j = 1; j <= n; j ++)
            if(!vis[j] && (t == -1 || dist[t] > dist[j])) t = j;

        vis[t] = true;

        for(int j = 1; j <= n; j ++) dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
}

int main(){
    cin >> m >> n;
    memset(g, 0x3f, sizeof g);
    getchar();
    while(m --){
        string str;
        getline(cin, str);
        stringstream sin(str);
        int cnt = 0, s;
        while(sin >> s) path[cnt ++] = s;
        for(int i = 0; i < cnt; i ++)
            for(int j = i + 1; j < cnt; j ++)
                g[path[i]][path[j]] = 1;
    }
    dijkstra();
    if(dist[n] == 0x3f3f3f3f) cout << "NO" << endl;
    else cout << dist[n] - 1 << endl;
    return 0;
}