1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| #include<iostream>
#include<cstdio>
#include<string.h>
#define MAX 999999;
using namespace std;
int map[105][105],dist[105];
bool vis[105];
int prim(int n)
{
int i,j,pos;
int min,sum;
sum=0;
memset(vis,false,sizeof(vis));
for(i=1; i<=n; i++)
{
dist[i]=map[1][i];
}
vis[1]=true;
dist[1]=MAX;
for(i=1; i<n; i++)
{
min=MAX;
for(j=1; j<=n; j++)
{
if(!vis[j] && dist[j]<min)
{
min=dist[j];
pos=j;
}
}
sum+=min;
vis[pos]=true;
for(j=1; j<=n; j++)
{
if(!vis[j] && dist[j]>map[pos][j])
{
dist[j]=map[pos][j];
}
}
}
return sum;
}
int main()
{
int n,a,b;
int c,d;
while(~scanf("%d",&n))
{
if(n==0)
break;
for(int i=0; i<(n*(n-1)/2); i++)
{
cin >> a>> b>>c>>d;
if(d==1)
map[a][b]=map[b][a]=0;
else
map[a][b]=map[b][a]=c;
}
int ans=prim(n);
printf("%d\n",ans);
}
return 0;
}
|