输入格式 n（城市数，1<≤n≤100）e（边数）以下e行，每行3个数i，j，wij（wij≤3000），表示在城市i，j之间修建高速公路的造价。 输出格式 一个整型数，表示得到的最小工程造价。输出样例 19

算法1

(Prim算法)

Prim算法是一种求解最小生成树的贪心算法，基本思想是从一个点开始，每次选择与当前生成树连接的权值最小的边所连的点加入到生成树中，直到所有点都被加入到生成树中为止。具体实现时，可以使用一个数组记录每个点到当前生成树的距离，每次选择距离最小的点加入到生成树中，并更新其他点到生成树的距离。

时间复杂度

Prim算法的时间复杂度为O(n^2)或O(mlogn)，其中n为点数，m为边数。

参考文献

- 《算法导论》（第三版）章节23.2

C++ 代码

算法2

(Kruskal算法)

Kruskal算法是一种求解最小生成树的贪心算法，基本思想是从边开始，每次选择权值最小且不会形成环的边加入到生成树中，直到生成树中包含所有点为止。具体实现时，可以使用并查集来判断是否形成环。

时间复杂度

Kruskal算法的时间复杂度为O(mlogm)，其中m为边数。

参考文献

- 《算法导论》（第三版）章节23.2

C++ 代码