现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。
输入格式:
输入数据包括城镇数目正整数N（≤1000）和候选道路数目M（≤3N）；随后的M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从1到N编号。
输出格式:
输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出−1，表示需要建设更多公路。
输入样例:
6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3
输出样例:
12
//prim算法求 7-5 公路村村通 (30 分)#include <stdio.h>#include <string.h>#include <stdbool.h>#define INF 0x3f3f3f3f//极大数int n;int ch[1001][1001]; //村与村之间的路(邻接矩阵)int L[1001]; //村与最小生成树之间的路int prim(int x){bool flag[1001];memset(flag, false, sizeof(flag));L[x] = 0;int cou = 0;for (int i = 0; i < n; i++){int u = -1, min = INF;for (int j = 1; j <= n; j++){if (L[j] < min && flag[j] == false){min = L[j];u = j;}}if (u == -1)return -1;cou += L[u];flag[u] = true;for (int j = 1; j <= n; j++){if (ch[u][j] != INF && flag[j] == false){if (ch[u][j] < L[j]){L[j] = ch[u][j];}}}}return cou;}int main(){memset(ch, INF, sizeof(ch));memset(L, INF, sizeof(L));int m;scanf("%d %d", &n, &m);while (m--){int a, b, c;scanf("%d %d %d", &a, &b, &c);ch[a][b] = c;ch[b][a] = c;}int k = prim(1);printf("%d", k);}
