1083:小明的家乡Ⅲ

Time/Memory Limit:5000 MS/32768 K
Submitted: 59 Accepted: 26

 Problem Description

小明家乡的旅游区改造已经进行了一段时间。省规划局的目标是使任何两个岛屿间都可以实现陆上交通(但不一定有直接的桥梁相连,只要能间接通过桥梁可达即可)。现得到桥梁统计表,表中列出了任意两岛屿间修建桥梁的费用,以及该桥梁是否已经修通的状态。现请你编写程序,计算出省规划局的规划目标还需要的最低成本。

 Input

测试输入包含若干测试用例。每个测试用例的第1行给出岛屿的数目N ( 1< N < 100 );随后的N(N-1)/2 行对应岛屿间桥梁修建的成本及修建状态,每行给4个正整数,分别是两个岛屿的编号(从1编号到N),此两岛屿间桥梁修建的成本,以及修建状态:1表示已建,0表示未建。当N为0时输入结束。

 Output

每个测试用例的输出占一行,输出省规划局的规划目标还需要的最低成本。

 Sample Input

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

 Sample Output

3
1
0

 Author

hjj

 Recommend

zh