其它pta数据结构编程题请参见：
这道题考察最小生成树问题，用的是Prim算法。
和Dijkstra算法相比，没有了collect数组，因为dist[v] == 0就代表v被已收录。
1 #include2 using namespace std; 3 4 int N, M; 5 int** G; 6 void buildGraph(); 7 void deleteGraph(); 8 int prim(); 9 int findMinDist(int dist[]); 10 11 int main() 12 { 13 cin >> N >> M; 14 buildGraph(); 15 cout << prim(); 16 deleteGraph(); 17 return 0; 18 } 19 20 void buildGraph() 21 { 22 int i, j; 23 G = new int*[N]; 24 for (i = 0; i < N; i++) 25 { 26 G[i] = new int[N]; 27 for (j = 0; j < N; j++) 28 G[i][j] = INT_MAX; 29 } 30 31 int v, w, d; 32 for (i = 0; i < M; i++) 33 { 34 cin >> v >> w >> d; 35 v--; w--;//输入从1计数 36 G[v][w] = d; 37 G[w][v] = d; 38 } 39 } 40 41 void deleteGraph() 42 { 43 for (int i = 0; i < N; i++) 44 delete[] G[i]; 45 delete[] G; 46 } 47 48 int findMinDist(int dist[]) 49 { /*返回未收录进MST的顶点中dist最小的顶点*/ 50 int minV, v; 51 int minDist = INT_MAX; 52 for (v = 0; v < N; v++) 53 { 54 if (dist[v] != 0 && dist[v] < minDist) 55 { 56 minDist = dist[v]; 57 minV = v; 58 } 59 } 60 if (minDist < INT_MAX) 61 return minV; 62 return -1; 63 } 64 65 int prim() 66 { /*返回最小生成树的权重*/ 67 int v, w, vCount = 0; 68 int totalWeight = 0; 69 int* dist = new int[N]; 70 71 /*初始化，初始点下标为0*/ 72 for (v = 0; v < N; v++) 73 dist[v] = G[0][v]; 74 75 /*将0收进最小生成树MST*/ 76 dist[0] = 0; 77 vCount++; 78 79 while (true) 80 { 81 v = findMinDist(dist); 82 if (v == -1) 83 break; 84 85 totalWeight += dist[v]; 86 dist[v] = 0; //收录v 87 vCount++; 88 89 for (w = 0; w < N; w++) 90 { 91 /*如果w没有被收录*/ 92 if (dist[w] != 0 && G[v][w] < dist[w]) 93 { 94 dist[w] = G[v][w]; 95 } 96 } 97 } 98 99 delete[] dist;100 101 if (vCount < N)102 return -1;103 return totalWeight;104 }