这段代码实现了一个Dijkstra算法，用于求解单源最短路径问题。与之前的实现不同，这段代码使用了**优先队列（最小堆）**来优化算法，从而提高效率。以下是代码的详细思路解析：

---

1. 问题背景

给定一个包含 n 个节点和 m 条边的图，每条边有一个非负权重。目标是找到从节点 1 到节点 n 的最短路径长度。如果不存在这样的路径，则返回 -1。

2. Dijkstra算法的概念

Dijkstra算法是一种经典的最短路径算法，适用于带权重的有向图或无向图，且所有边的权重均为非负数。算法通过维护一个距离数组 dist 和一个访问标记数组 st，逐步找到从源点到所有其他节点的最短路径。使用优先队列可以优化选择当前距离最小的未访问节点的过程。

3. 代码逻辑解析

(1) 初始化图和距离数组

cin >> n >> m;  // 输入节点数和边数
memset(h, -1, sizeof h);  // 初始化邻接表头数组
while (m--)
{
    int a, b, c;
    cin >> a >> b >> c;  // 输入一条边的起点、终点和权重
    add(a, b, c);  // 添加边到邻接表
}

• 使用邻接表存储图，h[a] 表示节点 a 的第一条边的索引，e[i] 和 w[i] 分别表示边的终点和权重，ne[i] 表示下一条边的索引。

• 输入图的边，调用 add 函数将边添加到邻接表中。

(2) 添加边的函数

void add(int a, int b, int c)
{
    e[idx] = b;  // 边的终点
    w[idx] = c;  // 边的权重
    ne[idx] = h[a];  // 下一条边的索引
    h[a] = idx++;  // 更新头数组，索引加1
}

• 将边 (a, b) 与权重 c 添加到邻接表中。

(3) Dijkstra算法实现

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);  // 初始化距离数组为无穷大
    dist[1] = 0;  // 源点到自身的距离为0
    priority_queue<PII, vector<PII>, greater<PII>> heap;  // 使用最小堆
    heap.push({0, 1});  // 将源点加入堆

    while (heap.size())
    {
        auto t = heap.top();  // 获取堆顶元素
        heap.pop();  // 弹出堆顶元素

        int ver = t.second, distance = t.first;  // 当前节点和距离

        if (st[ver]) continue;  // 如果当前节点已访问，跳过
        st[ver] = true;  // 标记当前节点为已访问

        for (int i = h[ver]; i != -1; i = ne[i])  // 遍历当前节点的所有邻接边
        {
            int j = e[i];  // 邻接节点
            if (dist[j] > dist[ver] + w[i])  // 更新邻接节点的距离
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});  // 将更新后的节点加入堆
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;  // 如果目标节点的距离仍为无穷大，说明无路径
    return dist[n];  // 返回源点到目标节点的最短路径长度
}

• 初始化：

  • 将距离数组 dist 初始化为无穷大。

  • 将源点到自身的距离设为0。

  • 使用优先队列（最小堆）存储节点及其当前距离。

• 迭代：

  • 每次从堆中取出当前距离最小的节点 ver。

  • 如果该节点已访问过，跳过。

  • 遍历该节点的所有邻接边，更新邻接节点的距离。

  • 如果更新后的距离更短，将邻接节点加入堆中。

• 检查结果：

  • 如果目标节点 n 的距离仍为无穷大，说明从源点到目标节点无路径，返回 -1。

  • 否则，返回源点到目标节点的最短路径长度。

(4) 主函数

ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cout << dijkstra();  // 输出从节点1到节点n的最短路径长度

• 输入优化：

  • 使用 ios::sync_with_stdio(0) 和 cin.tie(0) 提高输入输出效率。

• 调用 Dijkstra算法：

  • 调用 dijkstra 函数计算从节点 1 到节点 n 的最短路径长度，并输出结果。

---

4. 示例运行

输入：

5 6
1 2 2
1 5 10
2 3 3
3 5 7
3 4 2
4 5 3

输出：

10

---

5. 总结

这段代码的核心思路是通过Dijkstra算法求解单源最短路径问题，并使用**优先队列（最小堆）**优化算法，从而提高效率。这种方法的时间复杂度为 O((n + m) log n)，适用于大规模图。

完整代码

#include<bits/stdc++.h>
using namespace std;

// 定义一个二元组类型 PII，用于存储距离和节点编号
typedef pair<int, int> PII;
// 定义最大节点数
const int N = 1e6 + 10;
// n 表示节点数，m 表示边数
int n, m;
// h 数组是邻接表的头数组，存储每个节点的第一条边的编号
// w 数组存储每条边的权重
// e 数组存储每条边的终点
// ne 数组存储每条边的下一条边的编号
// idx 用于记录当前边的编号
int h[N], w[N], e[N], ne[N], idx;
// dist 数组用于存储从起点到各个节点的最短距离
int dist[N];
// st 数组用于标记节点是否已经确定最短路径
bool st[N];

// 向邻接表中添加一条从 a 到 b 权重为 c 的边
void add(int a, int b, int c)
{
    // 当前边的终点为 b
    e[idx] = b;
    // 当前边的权重为 c
    w[idx] = c;
    // 当前边的下一条边为节点 a 的第一条边
    ne[idx] = h[a];
    // 节点 a 的第一条边更新为当前边
    h[a] = idx ++;
}

// 堆优化版的 Dijkstra 算法实现
int dijkstra()
{
    // 初始化 dist 数组，将所有距离初始化为一个很大的值（0x3f3f3f3f）
    memset(dist, 0x3f, sizeof dist);
    // 起点到自身的距离为 0
    dist[1] = 0;
    // 定义一个小顶堆，存储距离和节点编号
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    // 将起点的距离和编号加入堆中
    heap.push({0, 1});

    // 当堆不为空时，继续循环
    while(heap.size())
    {
        // 取出堆顶元素
        auto t = heap.top();
        heap.pop();

        // 取出节点编号和距离
        int ver = t.second, distance = t.first;

        // 如果该节点已经确定最短路径，跳过
        if(st[ver]) continue;
        // 标记该节点已经确定最短路径
        st[ver] = true;

        // 遍历该节点的所有出边
        for(int i = h[ver]; i != -1; i = ne[i])
        {
            // 取出当前边的终点
            int j = e[i];
            // 如果通过当前节点到达终点的距离更短，则更新距离
            if(dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                // 将更新后的距离和节点编号加入堆中
                heap.push({dist[j], j});
            }
        }
    }

    // 如果终点的距离仍然是初始的很大值，说明无法到达终点
    if(dist[n] == 0x3f3f3f3f) return -1;
    // 返回起点到终点的最短距离
    return dist[n];
}

int main()
{
    // 关闭输入输出流的同步，提高输入输出效率
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // 输入节点数和边数
    cin >> n >> m;
    // 初始化邻接表的头数组，将所有节点的第一条边编号初始化为 -1
    memset(h, -1, sizeof h);
    // 循环读入每条边的信息
    while(m --)
    {
        // a 表示起点，b 表示终点，c 表示边的权重
        int a, b, c;
        cin >> a >> b >> c;
        // 向邻接表中添加边
        add(a, b, c);
    }
    // 调用堆优化版的 Dijkstra 算法并输出结果
    cout << dijkstra();
    return 0;
}