dijkstra堆优化模板

下面是一个使用堆优化的Dijkstra算法的模板：

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

typedef pair<int, int> pii; // 存储节点和距离的pair

const int INF = numeric_limits<int>::max(); // 无穷大

vector<vector<pii>> graph; // 图的邻接表表示

vector<int> dijkstra(int start, int n)
{
    vector<int> dist(n, INF); // 存储起始点到每个点的最短距离
    dist[start] = 0;

    priority_queue<pii, vector<pii>, greater<pii>> pq; // 小顶堆，存储节点和距离的pair

    pq.push(make_pair(0, start)); // 将起始点入队

    while (!pq.empty())
    {
        int u = pq.top().second; // 当前节点
        int d = pq.top().first; // 当前距离
        pq.pop();

        // 如果当前距离大于已经计算出的最短距离，则忽略
        if (d > dist[u])
            continue;

        // 遍历当前节点的邻接节点
        for (auto edge : graph[u])
        {
            int v = edge.first; // 邻接节点
            int w = edge.second; // 边的权重

            // 如果通过u到v的距离更短，则更新最短距离，并将v加入队列
            if (dist[u] + w < dist[v])
            {
                dist[v] = dist[u] + w;
                pq.push(make_pair(dist[v], v));
            }
        }
    }

    return dist;
}

int main()
{
    int n, m;
    cin >> n >> m; // 输入节点数和边数

    graph.resize(n);

    for (int i = 0; i < m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w; // 输入边的起点、终点和权重
        graph[u].push_back(make_pair(v, w));
        graph[v].push_back(make_pair(u, w)); // 无向图需要双向连接
    }

    int start;
    cin >> start; // 输入起始点

    vector<int> dist = dijkstra(start, n); // 调用Dijkstra算法

    // 输出最短距离
    for (int i = 0; i < n; i++)
        cout << "Node " << i << ": " << dist[i] << endl;

    return 0;
}

这个模板使用了堆优化的方法来实现Dijkstra算法，通过优先队列（小顶堆）来选择当前距离最短的节点进行扩展。算法的时间复杂度为O((V+E)logV)，其中V为节点数，E为边数。