- 题目描述：
- 省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。现得到城镇道路统计表，表中列出了任意两城镇间修建道路的费用，以及该道路是否已经修通的状态。现请你编写程序，计算出全省畅通需要的最低成本。
- 输入：
- 测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 1< N < 100 )；随后的 N(N-1)/2 行对应村庄间道路的成本及修建状态，每行给4个正整数，分别是两个村庄的编号（从1编号到N），此两村庄间道路的成本，以及修建状态：1表示已建，0表示未建。
当N为0时输入结束。
- 输出：
- 每个测试用例的输出占一行，输出全省畅通需要的最低成本。
- 样例输入：
3
1 2 1 0
1 3 2 0
2 3 4 0
3
1 2 1 0
1 3 2 0
2 3 4 1
3
1 2 1 0
1 3 2 1
2 3 4 1
0
- 样例输出：
3
1
0 该题在1024题的基础上略微修改即可，已修的路价格为0，未修的路价格为原价
代码如下：#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#define MAX 102
#define inf 0x3f3f3f3f
int flag[MAX];
int cost[MAX][MAX];
int lowCost[MAX]; int main(int argc, char const *argv[])
{
int n,m;
scanf("%d",&n);
while(n != ) {
int count = ;
m = n * (n-)/;
for(int i = ; i <= n; i++) {
flag[i] = ;
for(int j = ; j <= n; j++) {
cost[i][j] = inf;
}
}
for(int i = ; i < m; i++) {
int a,b,c,d;
scanf("%d %d %d %d",&a,&b,&c,&d);
if(d == ) {
cost[a][b]= cost[b][a] = c;
}
else {
cost[a][b]= cost[b][a] = ;
}
} int sumCost = ;
for(int i = ; i <= n; i++) {
lowCost[i] = cost[][i];
}
flag[] = ; for(int i = ; i <= n; i++) {
int min = inf;
int v = -;
for(int i = ; i <= n; i++) {
if(flag[i] == && lowCost[i] < min) {
min = lowCost[i];
v = i;
}
}
flag[v] = ;
sumCost = sumCost + lowCost[v]; for(int i = ; i <= n; i++) {
if(cost[v][i] < lowCost[i]) {
lowCost[i] = cost[v][i];
}
}
} printf("%d\n",sumCost); scanf("%d",&n);
} return ;
}