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

#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>

using namespace std;

int n, m;//n个结点，m条连线
map<int, vector<int>> mp;//map的键值不能重复
int dist[5001];//存储到达某个结点的最短距离，如果无法到达，则为-1

void Dijkstra(int start, int n) {
    bool ans =
        false;//判断能否到达n这个结点，即1和n之间是否有通路
    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，即最短距离的值了
                dist[pos] = dist[start] +
                            1;//从首个结点到一个结点的最短距离等于前面那个结点的最短距离+1,相当于是层次遍历
                if (pos == n) {
                    ans = true;
                    break;
                }
                qu.push(pos);
            }
        }
        if (ans)
            break;
    }
}

int main() {
    cin >> n >> m;
    int from, to;
    for (int i = 0; i < m; i++) {//键为int型，值为vector<int>型数组
        cin >> from >> to;
        mp[from].push_back(to);//将键值对存储到map中
        mp[to].push_back(from);//无向图相连的两个点互相到达
    }
    for (int i = 0; i <= 5000; i++) {
        dist[i] = -1;//初始值为-1
    }
    Dijkstra(1, n);
    cout << dist[n] << endl;//输出到达n的最短距离
    return 0;
}