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

//Dijkstra
#include <iostream>
#include <queue>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 50050;

struct edge {
    int v;
};//边的另一个顶点（此题没有权重）
struct node {
    int dis;//每个顶点到源点（1号点）的距离
    int u;//顶点编号
    bool operator>(const node& a) const {
        return dis > a.dis;
    }//重载大于号，用于升序排列
};
vector<edge> e[maxn];//邻接表，边的位置代表其中一个顶点
int dis[maxn];//每个顶点到源点（1号点）的距离
int vis[maxn];//是否已确定最短距离，初值为0
priority_queue<node, vector<node>, greater<node> > q;
//按dis升序排列顶点的优先队列，存储未确定最短距离的顶点

int dijkstra(int n, int s) { //s:source源点
    memset(dis, 63, sizeof(dis));//63=0x3f 表示无穷大
    dis[s] = 0;
    q.push({dis[s], s});
    while (!q.empty()) {
        int u = q.top().u;//取出距离最小的顶点
        q.pop();
        if (vis[u]) continue;
        for (auto ed : e[u]) {//ed:edge，e[u]:与第u个顶点相连的顶点
            int v = ed.v;
            if (dis[v] > dis[u] + 1) {
                dis[v] = dis[u] + 1;
                q.push({dis[v], v});
            }
        }
        vis[u] = 1;
    }
    return dis[n];
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        e[u].push_back({v});
        e[v].push_back({u});
    }
    if (dijkstra(n, 1)<0x3f3f3f3f)cout<<dis[n];
    else cout<<-1;
    return 0;
}

审题发现是求解非负权无向稀疏图上单源最短路径，使用优先队列实现的Dijkstra如果同一个点的最短路被更新多次，因为先前更新时插入的元素不能被删除，也不能被修改，只能留在优先队列中，故优先队列内的元素个数是O(m)的，时间复杂度O(mlogm)。在OI Wiki提供的模板的基础上实现，感觉足够简洁优美。