题目链接：
题目描述：
请先参考关于prim算法求最小生成树的讲解博客：
代码实现：
1 #include2 #include 3 using namespace std; 4 #define MAX 100 5 #define MAXCOST 0x7fffffff 6 7 int graph[MAX][MAX]; 8 9 int prim(int graph[][MAX], int n)10 {11 int lowcost[MAX];//lowcost[i]:表示以i为终点的边的最小权值,注意i的起点并不确定12 int mst[MAX];//mst[i]:表示对应lowcost[i]的起点13 int i, j, min, minid, sum = 0;14 //我们设V1是起点，进行初始化15 for (i = 2; i <= n; i++)16 {17 lowcost[i] = graph[1][i];//如果该顶点未与V1相连，lowcost值为MAXCOST18 mst[i] = 1;//刚开始的时候，对于每一个Vi来说，它的起点都是V119 }20 mst[1] = 0;//当mst[i]=0表示起点i加入MST21 for (i = 2; i <= n; i++)//执行n-1次，保证V1到达每个顶点的最短边都能够找到22 {23 min = MAXCOST;24 minid = 0;//起点Vi到顶点minid的边最短25 for (j = 2; j <= n; j++)//找出最短的边，用minid记录下该顶点，用min存下最短边26 {27 if (lowcost[j] < min && lowcost[j] != 0)28 {29 min = lowcost[j];30 minid = j;31 }32 }33 sum += min;//每找出一条最短边就加到权值中去34 lowcost[minid] = 0;//当lowcost[i]=0说明以i为终点的边的最小权值=0,也就是表示i点加入了MST35 for (j = 2; j <= n; j++)36 {37 if (graph[minid][j] < lowcost[j])38 {39 lowcost[j] = graph[minid][j];40 mst[j] = minid;41 }42 }43 }44 return sum;45 }46 47 int main()48 {49 int i, j, k, m, n;50 int x, y, cost;51 while(scanf("%d%d",&m,&n)){52 if(m==0)53 break;54 //初始化图G55 for (i = 1; i <= m; i++)56 {57 for (j = 1; j <= m; j++)58 {59 graph[i][j] = MAXCOST;60 }61 }62 //构建图G63 for (k = 1; k <= n; k++)64 {65 cin >> i >> j >> cost;66 if(cost