dijikstra堆优化算法代码（含注释）

admin

[C++] 纯文本查看 复制代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 9;//常数
const int M = 1e4 + 9;
typedef pair<int, int> pii;//first是距离，second是队列中的点
struct edge {//边
    int v, w, next;
} e[M << 1];
int head[N], len;//链式前向星
void init() {//链式前向星存图
    memset(head, -1, sizeof(head));
    len = 0;
}
void add(int u, int v, int w) {//链式前向星存图
    e[len] = {v, w, head[u]};
    head[u] = len++;
}
int n, m;
int dis[N];//距离
bool vis[N];//是否被访问
void dijkstra(int u) {
    memset(vis, false, sizeof(vis));//初始化
    memset(dis, 0x3f, sizeof(dis));
    priority_queue<pii, vector<pii>, greater<pii>> q;//优先队列
    q.push({dis[u] = 0, u});//放入起点
    while (!q.empty()){
        int u = q.top().second;//队头上的点
        q.pop();
        if (vis[u]){//是否被访问
            continue;
        }
        vis[u] = true;//标记为访问
        for (int j = head[u]; ~j; j = e[j].next) {//链接
            int v = e[j].v;//下一个点
            int w = e[j].w;//权值
            if (!vis[v] && dis[v] > dis[u] + w) {//更新距离
                q.push({dis[v] = dis[u] + w, v});
            }
        }
    }
}
int main() {
    init();
    int u, v, w;
    cin >> n >> m;
    for(int i=1;i<=m;i++){//存边
        cin >> u >> v >> w;
        add(u, v, w);//无向图
        add(v, u, w);
    }
    dijkstra(1);//跑函数
    cout<<dis[n]<<endl;//结果
    return 0;
}