用std::priority_queue实现prim算法最稳，需自定义比较逻辑按边权升序，邻接表存{to,weight}，入队前检查visited避免重复，dist数组加溢出防护，负权边不适用。
Prim算法在C++里怎么写才不崩
直接用 std::priority_queue 实现 Prim 是最稳的路径，但必须自定义比较逻辑，否则会按顶点编号排序而非边权——这是 90% 初学者第一次写就卡住的地方。
- 别用
std::priority_queue<:pair int>></:pair>默认构造，它按 first 升序，而我们需要按边权（即first）升序，但若把权值放second就更易错 - 推荐封装成结构体或用 lambda：
priority_queue<edge vector>, greater<edge>></edge></edge>，其中Edge重载operator 或 <code>operator> - 图必须用邻接表（
vector<vector int>>></vector>），存{to, weight}；邻接矩阵在稀疏图里纯属拖慢速度
为什么 visited 数组不能靠出队判断
Prim 的核心是“每次取最小边，且边另一端未访问”，但 std::priority_queue 不支持删除或更新已有元素。如果只靠出队时检查 visited[to]，会重复入队、重复处理——尤其在有重边或松弛后权值变小的图中，堆里可能塞几十个同一节点的不同边。
- 入队前就检查：插入前先看
to是否已加入 MST，是则跳过 - 或者入队后立刻标记
visited[to] = true，但仅限于该次成功扩展后——注意不是一进堆就标，而是从堆里取出、确认未访问、再标并累加边权 - 漏掉这步，
totalWeight会算重，甚至死循环（堆永远不空）
INT_MAX 初始化距离数组的隐患
用 vector<int> dist(n, INT_MAX)</int> 没问题，但加边时若不做溢出防护，dist[u] + w 可能整数溢出变成负数，导致错误松弛和堆顺序错乱。
- 每次计算前加判断：
if (dist[u] != INT_MAX && dist[u] + w - 或者改用
long long存距离，尤其题目边权范围大时——INT_MAX在 32 位环境只有约 21 亿，两段 15 亿的边相加就炸 - 别依赖编译器对
INT_MAX + 1的行为，C++ 标准里这是未定义行为
稠密图下 Prim 还不如 Kruskal？
是的。Prim 基于堆的版本复杂度是 O(E log V)，但当 E ≈ V²（比如完全图），Kruskal 的 O(E log E) 实际常数更低，且并查集实现简单、不易写错。
立即学习“C++免费学习笔记（深入）”；
- 真遇到点数
V ≤ 1000但边数E > 10^5，优先写 Kruskal - Prim 的优势在稀疏图 + 需要实时构建过程（比如网络动态加点），或题目明确要求“从某点开始生长”
- 手写堆或用
std::set替代priority_queue并不能根本改善稠密图性能，反而增加调试成本
边权类型、是否含负权、图是否连通——这三个条件没确认前，连 Prim 能不能用都得打问号。尤其是负权边，Prim 不处理，它假设所有边权非负，这点文档里常被忽略。
