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

#include<iostream> 
#include<queue> 
#include<map> 
#include<vector> 
#include<algorithm> 
using namespace std; 
map<int,vector<int> > mp; 
int dist[5001]; 
void Dijkstra(int start,int n){ 
    bool ans = false; 
    queue<int> qu; 
    qu.push(start); 
    dist[start] = 0; 
    while(!qu.empty()){ 
        start = qu.front(); 
        qu.pop(); 
        for(int i = 0;i < mp[start].size();++i){ 
            int pos = mp[start][i]; 
            if(dist[pos] == -1){ 
                dist[pos] = dist[start] + 1; 
                if(pos == n){ 
                    ans = true; 
                    break; 
                } 
                qu.push(pos); 
            } 
        } 
        if(ans) 
            break; 
    } 
} 
int main() { 
    int n,m,from,to; 
    cin >> n >> m; 
    for(int i = 1;i <= m;++i){ 
        cin >> from >> to; 
        mp[from].push_back(to); 
        mp[to].push_back(from); 
    } 
    for (int i = 0 ; i <= 5000 ; i ++)
        dist[i] = -1;  
    Dijkstra(1,n); 
    cout << dist[n]; 
}