11. 最短路、最小生成树与连通性

习题

#31101

⚡5⏳5

在非负权有向图上实现 Dijkstra 单源最短路。图用边数组表示：

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef struct {
    size_t from;
    size_t to;
    uint64_t weight;
} WeightedEdge;

bool dijkstra_distances(
    size_t vertex_count,
    const WeightedEdge *edges,
    size_t edge_count,
    size_t source,
    uint64_t *out_distances
);

要求：

1. 顶点编号有效，边权不得为负；不可达顶点的距离写为 UINT64_MAX。
2. vertex_count == 0 不接受有效源点；参数无效、存储分配失败或松弛加法溢出时返回 false，不得修改输出数组。
3. 使用邻接表和最小堆，时间复杂度为 $O((V+E)\log V)$；允许在堆中保留过期条目，但必须安全跳过。
4. 说明非负边权是 Dijkstra 正确性的必要条件。

#31102

⚡5⏳5

给定无向带权图，求其最小生成树总权重：

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef struct {
    size_t left;
    size_t right;
    uint64_t weight;
} UndirectedEdge;

bool minimum_spanning_tree_weight(
    size_t vertex_count,
    const UndirectedEdge *edges,
    size_t edge_count,
    uint64_t *out_weight
);

要求：

1. 图不连通时返回 false；vertex_count == 0 时总权重为 0。
2. 边端点必须有效；总权重或内部加法溢出时返回 false，输出对象保持不变。
3. 使用 Kruskal 或 Prim，并说明并查集如何避免加入环；时间复杂度应达到 $O(E\log E)$ 或 $O((V+E)\log V)$。
4. 相同权重的边可以任意选择，但必须得到一棵合法的生成树。