C++ 代码

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

using namespace std;
int m, n;
const int M = 30000, N = 510;//因为加了很多额外的边，M要开得大一些
const int INF = 0x3f3f3f3f;
int e[M], ne[M], h[N], idx;
int dist[N];
bool st[N];
int stop[N];

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

void spfa(){
    memset(dist, INF, sizeof dist);
    dist[1] = 0;
    queue<int> q;
    q.push(1);
    st[1] = true;
    while(!q.empty()){
        int t = q.front();
        q.pop();
        st[1] = false;
        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if(dist[j] > dist[t] + 1){
                dist[j] = dist[t] + 1;
                if(!st[j]){
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

}
int main(){
    cin >> m >> n;

    string s;
    memset(h, -1, sizeof h);
    getchar();

    int cnt = 0, x;
    for(int i = 0; i < m; i++){
        getline(cin, s);
        stringstream ssin(s);
        cnt = 0;
        while(ssin >> x) stop[cnt++] = x;
        for(int i = 0; i < cnt; i++)
            for(int j = i + 1; j < cnt; j++){
                add(stop[i], stop[j]);
                //printf("a = %d, b = %d\n", stop[i], stop[j]);
            }
    }


    spfa();
    if(dist[n] == INF)puts("NO");
    else printf("%d", dist[n] - 1);

    return 0;

}