#include

<

iostream

>

using

namespace

std;

#define

N 27

#define

M 27

#define

INF 111

int

dist[N];

int

P[M][M];

//

初始值为INF;

int

n;

//

n个村庄;

int

used[N];

int

total;

void

prim();

int

main()

{

char

v;

char

tmp;

int

money;

int

num;

cin

>>

n;

while

(n)

{

total

=

0

;

for

(

int

m

=

0

;m

<

N;m

++

)

{

dist[m]

=

INF;

used[m]

=

0

;

}

for

(

int

j

=

0

;j

<

M;j

++

)

for

(

int

k

=

0

;k

<

M;k

++

)

P[j][k]

=

INF;

int

i

=

0

;

for

(i

=

0

;i

<

n

-

1

;i

++

)

{ cin

>>

v;

cin

>>

num;

while

(num

--

){

cin

>>

tmp;

cin

>>

money;

P[v

-

'

A

'

][tmp

-

'

A

'

]

=

P[tmp

-

'

A

'

][v

-

'

A

'

]

=

money;

}

}

prim();

cout

<<

total

<<

endl;

cin

>>

n;

}

}

void

prim()

//

从第o点开始;

{

for

(

int

i

=

0

;i

<

n;i

++

)

dist[i]

=

P[

0

][i];

used[

0

]

=

1

;

int

x;

for

(x

=

0

;x

<

n;x

++

){

int

min

=

INF;

int

f

=-

1

;

for

(

int

i

=

0

;i

<

n;i

++

)

if

(

!

used[i]

&&

dist[i]

<

min)

{

min

=

dist[i];

f

=

i;

}

if

(f

==-

1

)

break

;

else

{

used[f]

=

1

;

total

+=

dist[f];

}

for

(

int

z

=

0

;z

<

n;z

++

){

if

(

!

used[z]

&&

P[f][z]

<

dist[z])

{

dist[z]

=

P[f][z];

}

}

}

}

 

很简单  很基础的最小生成树   既然ac了   就把代码贴出来了 :