c++堆优化dijkstra

C++堆优化Dijkstra算法是一种用于求解单源最短路问题的算法，它是Dijkstra算法的一种优化。在Dijkstra算法中，我们通过一个数组记录节点到起点的距离，并通过一个集合记录已经确定最短路的节点，然后每次从集合中选择距离起点最近的节点进行松弛操作，直到集合为空为止。但是这种方法的时间复杂度是O(n^2)的，无法处理大规模图的问题。

堆优化Dijkstra算法则是通过使用堆来优化选择距离起点最近的节点的过程，从而将时间复杂度降低到O(mlogn)，其中n为节点数，m为边数。具体实现过程如下：

1. 初始化：将起点加入堆中，距离为0，其他节点距离为无穷大。

2. 取出堆顶元素：每次从堆中取出距离起点最近的节点，将其标记为已经确定最短路。

3. 松弛操作：遍历与该节点相邻的所有节点，如果当前节点到起点的距离可以通过该节点更新，则更新该节点到起点的距离，并将该节点加入堆中。

4. 重复步骤2和3，直到堆为空或者堆顶元素为终点。

下面是C++代码实现：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
int n, m, s, t;
int head[N], cnt = 0;
int dis[N], vis[N];
struct Edge {
    int v, w, nxt;
} e[N << 1];
struct Node {
    int u, d;
    bool operator < (const Node &rhs) const {
        return d > rhs.d;
    }
};
void add_edge(int u, int v, int w) {
    e[++ cnt] = (Edge) {v, w, head[u]};
    head[u] = cnt;
}
void dijkstra() {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    priority_queue<Node> q;
    q.push((Node) {s, 0});
    dis[s] = 0;
    while (!q.empty()) {
        int u = q.top().u;
        q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].v, w = e[i].w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if (!vis[v]) q.push((Node) {v, dis[v]});
            }
        }
    }
}
int main() {
    cin >> n >> m >> s >> t;
    for (int i = 1; i <= m; i ++) {
        int u, v, w;
        cin >> u >> v >> w;
        add_edge(u, v, w);
        add_edge(v, u, w);
    }
    dijkstra();
    cout << dis[t] << endl;
    return 0;
}

其中，priority_queue<Node> q;表示使用小根堆来存储节点，Node结构体中的u表示节点编号，d表示该节点到起点的距离。