最小生成树Prim算法和单源最短路径Dijkstra算法问题：1
（最小生成树）给定一个带权的无向连通图，如何选取一棵生成树，使树上所有边上权的总和为最小，即求最小生成树
（单源最短路径）给定一个权值都为正数的无向连通图和一个源点，确定它到其它点的最短距离
之所以将这两个问题放在一起，是因为Prim算法与Dijkstra算法的思路和程序都非常相似，都是有贪心策略
解法（Prim算法）：思路：设连通网络N={V,E}，U表示已加入到生成树的顶点集合
在初始化阶段，任取一个顶点，用其关联边的权值作为初始的V-U顶点集合的数据
在每一步中，先在V-U顶点集合中选择距离U中任意点“最近”的顶点v，再把v加入到U中，最后看看在新的V-U顶点集合中，是否有哪个顶点距离v比距离U中其它点更近，若有则更新V-U顶点集合中的数据
U的元素个数为V-1，所以共要进行V-1步
总的时间复杂度为Time=O(V)*T_EXTRACT-MIN+O(E)*T_DECREASE-KEY若用数组作为顶点权值的数据结构，T_EXTRACT-MIN用时O(V)，T_DECREASE-KEY用时O(1)，总共用时O(V^2)若用最小堆作为顶点权值的数据结构，T_EXTRACT-MIN用时O(lgV)，T_DECREASE-KEY用时O(lgV)，总共用时O((V+E)*lgV)若用斐波那契堆作为顶点权值的数据结构，T_EXTRACT-MIN平均用时O(lgV)，T_DECREASE-KEY平均用时O(1)，总共用时O(E+V*lgV)下面的代码使用数组作为顶点权值的数据结构：[cpp]viewplaincopy1
#include2
#include3
usingnamespacestd;4
#defineMAXN10016
#defineINF10000007
intlowcost[MAXN]
