1.补充一下 priority_queue 这种数据结构

C++中的priority_queue详解（结合Dijkstra算法代码）

priority_queue是C++标准库中的一个容器适配器，它提供了一种优先队列的数据结构实现。在Dijkstra算法的优化实现中，它被用来高效地获取当前距离起点最近的节点。下面我将结合题目代码详细讲解它的用法和特性。

基本概念

priority_queue（优先队列）是一种特殊的队列，其中的元素按照某种优先级顺序出队，而不是按照入队的先后顺序。在C++中，它默认实现的是最大堆（大根堆）。

在Dijkstra算法中的应用

在给定的代码中，priority_queue被这样定义和使用：

priority_queue<PII, vector<PII>, greater<PII>> heap;

1. 模板参数解析

priority_queue有三个模板参数：
1. 元素类型：PII（即pair<int, int>）
2. 底层容器：vector<PII>（默认就是vector<T>）
3. 比较函数：greater<PII>（这是一个函数对象，用于定义优先级）

2. 为什么使用greater<PII>

• 默认情况下，priority_queue是大根堆（使用less<T>），即最大的元素优先级最高
• 在Dijkstra算法中，我们需要距离最小的节点，所以需要使用小根堆
• greater<PII>会使队列按照升序排列，即最小的元素优先级最高

3. 元素类型为什么是pair<int, int>

• 第一个int：存储距离（用于优先级比较）
• 第二个int：存储节点编号
• 这样当从堆顶取出元素时，我们总是能得到当前距离起点最近的节点

主要操作

在代码中使用了以下操作：

1. 插入元素

heap.push({0, 1});          // 初始时插入起点(距离=0, 节点=1)
heap.push({dist[j], j});     // 松弛操作后插入更新后的距离

2. 访问堆顶元素

auto t = heap.top();  // 获取但不移除优先级最高的元素

3. 移除堆顶元素

heap.pop();  // 移除优先级最高的元素

为什么在Dijkstra中使用优先队列

1. 效率：每次获取最小距离节点的操作从O(n)降低到O(logn)
2. 适合稀疏图：当边数m远小于n²时，这种优化效果显著
3. 实现简洁：C++的priority_queue封装了堆操作，使用方便

与普通队列的区别

自定义比较函数

如果需要更复杂的优先级规则，可以自定义比较函数。例如：

struct Compare {
    bool operator()(const PII& a, const PII& b) {
        return a.first > b.first; // 等同于greater<PII>
    }
};

priority_queue<PII, vector<PII>, Compare> heap;

在Dijkstra中的注意事项

1. 重复插入：同一个节点可能被多次插入堆中（每次距离更新时），但只有距离最小的那个会被处理
2. 标记数组：st数组用于避免重复处理同一个节点
3. 内存使用：在最坏情况下，堆中可能包含O(m)个元素

性能考虑

• 使用greater<PII>比默认的less<PII>更适合Dijkstra算法
• 使用pair作为元素类型简单直接，但也可以定义更复杂的结构体
• 在某些情况下，使用emplace代替push可能更高效（避免临时对象创建）

通过使用priority_queue，Dijkstra算法的时间复杂度从O(n²)降低到了O(mlogn)，使其能够处理更大规模的图（如本题中的1.5×10⁵个节点和边）。

2.为什么不反过来用(节点, 距离)？

在Dijkstra算法的优先队列实现中，使用 (距离, 节点) 而不是 (节点, 距离) 的设计是经过深思熟虑的，主要原因如下：

1. 优先队列的默认排序行为

priority_queue 默认使用 std::less 比较函数，会对 pair 的 第一个元素 (first) 进行排序。
- 如果存入 (距离, 节点)，队列会按 距离从小到大排序（若用 greater<PII>），这正是Dijkstra算法需要的：每次取出 当前距离起点最近的节点。
- 如果存入 (节点, 距离)，队列会按 节点编号排序，完全违背了Dijkstra的需求。

2. pair 的比较规则

C++ 的 pair 在比较时，会先比较 first，若 first 相同，才会比较 second。
- 我们需要的是 按距离排序，因此距离必须放在 first。
- 节点编号 (second) 仅作为附带信息，不参与排序逻辑。

3. 如果强行用 (节点, 距离) 会怎样？

假设你写成：

priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({2, 3});  // 节点2，距离3
heap.push({1, 5});  // 节点1，距离5

• 由于 greater<PII> 是按 pair 的字典序比较，它会先比较节点编号（first），结果堆顶是 {1,5}（节点1），而 完全忽略距离5是否最小。
• 这样取出的节点 不是距离最近的，算法直接错误。

4. 能否通过自定义比较函数实现 (节点, 距离)？

可以，但没必要。例如：

struct Compare {
    bool operator()(const PII& a, const PII& b) {
        return a.second > b.second; // 强制按距离排序
    }
};
priority_queue<PII, vector<PII>, Compare> heap;

虽然这样能工作，但：
1. 需要额外写比较函数，代码更复杂。
2. 可读性变差（其他开发者可能误以为 first 是距离）。
3. 违背了 pair 的常规用法（通常 first 是主排序键）。

5. 总结：为什么是 (距离, 节点)？

因此，(距离, 节点) 是自然、高效且符合C++标准库设计哲学的选择。

3.最终代码

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;  // 存储距离和节点的对
const int N = 1e6 + 10;      // 最大节点数

int n, m;                    // n是节点数，m是边数
int h[N], w[N], e[N], ne[N], idx;  // 邻接表存储图
int dist[N];                 // 存储1号点到各点的最短距离
bool st[N];                  // 标记节点是否已经确定最短距离

void add(int a, int b, int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int dijkstra(){
    memset(dist, 0x3f, sizeof dist);  // 初始化距离为无穷大
    dist[1] = 0;                      // 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;        // 标记为已处理

        // 遍历ver的所有邻接节点
        for(int i = h[ver]; i != -1; i = ne[i]){
            int j = e[i];
            // 松弛操作：如果通过ver到j的距离更短，则更新
            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(){
    scanf("%d%d", &n, &m);  // 读取节点数和边数

    memset(h, -1, sizeof h);  // 初始化邻接表

    while(m--){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);  // 添加边
    }

    printf("%d\n", dijkstra());  // 计算并输出结果

    return 0;
}