题解 | #【模板】单源最短路1#

# include<iostream>
# include<vector>
# include<queue> 
using namespace std;

const int N = 5001;
int n, m;
int dist[N];
bool vis[N];
vector<int> g[N];
queue<int> q;

void spfa(int s){
    for(int i=1; i<=5000; i++){
        dist[i] = (1ll  << 31) - 1;
    }
    dist[s] = 0;
    vis[s] = true;
    q.push(s);
    while(!q.empty()){
        int x = q.front();
        vis[x] = false;
        q.pop();
        for(int i=0; i<g[x].size(); i++){
            int y = g[x][i];
            if(dist[x] + 1 < dist[y]){
                dist[y] = dist[x] + 1;
                if(!vis[y]){
                    vis[y] = true;
                    q.push(y);
                }
            }
        }
    }
}

int main(){
    cin >> n >> m;
    int u, v;
    for(int i=1; i<=m; i++){
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    spfa(1);
    if(dist[n] == ((1ll << 31) - 1)){
        cout << -1 << endl;
    }else{
        cout << dist[n] << endl;
    }
    return 0;
}