> #include<iostream>
> #include<cstring>
> #include<cstdio>
> using namespace std;
> const int size = 50;
> int max( int a,int b)
> {
> 	return a>b?a:b;
> }
> int min( int a, int b)
> {
> 	return a<b?a:b;
> }
> struct node
> {
> 	int id;
> 	char name[size];
> }address[size];
> const int INF = 999999999;
> struct 
> {
> 	int a, b;
> 	int val;
> }value[size][size];
> typedef int G[size][size];
> G graph;
> char name1[size], name2[size];
> 
> int stack[size];
> int pre[size];
> int n;
> int m;
> int val;
> int total;
> int k;//最大度
> bool edge[size][size];
> bool flag[size];
> void init()
> {
> 	for (int i=0; i<size ;i++)
> 		for (int j=0; j<size; j++)
> 			graph[i][j] = INF;
> 	memset( edge, false, sizeof(edge));
> 	total = 0;
> }
> void deal( char s1[], char s2[], int value)
> {
> 	int id1=1, id2=1, i;
> 	if( strcmp( "Park", s1) == 0)
> 		id1 = 0;
> 	if( strcmp( "Park", s2) == 0)
> 		id2 = 0;
> 	if( id1 )
> 	{
> 		for (  i=1; i<=m; i++)
> 		{
> 			if( strcmp( s1, address[i].name) ==0)
> 			{
> 				id1 = i; break;
> 			}
> 		}
> 		if( i > m)
> 		{
> 			strcpy( address[++m].name, s1);
> 			address[m].id = m;
> 			id1 = m;
> 		}
> 	}
> 	if( id2 )
> 	{
> 		for ( i=1; i<=m; i++)
> 		{
> 			if( strcmp( s2, address[i].name)==0)
> 			{
> 				id2 = i; break;
> 			}
> 		}
> 		if( i > m )
> 		{
> 			strcpy( address[ ++m ].name, s2 );
> 			address[m].id = m;
> 			    id2 = m;
> 		}
> 	}
> 	graph[id1][id2] = graph[id2][id1] = value;
> }
> 
> void prim( )
> {
> 	int i, j;
> 	bool visited[100];
> 	memset( visited, false,sizeof(visited));
>     memset( value, 0, sizeof( value ));
> 	int top = 0;
> 	int cost[100];
>     for (i = 1; i <= m; i++)
> 	{
> 		cost[i] = graph[1][i];
> 		pre[i] = 1;
> 	}
>     visited[1] = true;
> 	stack[top++] = 1;
> 	for (i=1; i < m; i++)
> 	{
> 		int min = INF, k = -1;
> 		for (j=1; j <= m; j++)
> 		  if( !visited[j] && cost[j] < min)
> 			  min = cost[j], k=j;
> 		for (j=0; j<top; ++j)
> 		{
> 			if( min > value[ stack[j] ][ pre[k] ].val )
> 			{
> 			  value[ stack[j] ][ k ].val = min;
> 		      value[ stack[j] ][ k ].a = pre[k];
> 			  value[ stack[j] ][ k ].b = k;
> 			  value[ k ][ stack[j] ] = value[ stack[j] ][ k ];
> 			}
> 		}
> 		visited[ k ] = true;
> 		total += min;
> 		stack[ top++ ] = k;
>         edge[ pre[k] ][ k ] = edge[ k ][ pre[k] ] = true;
> 		for (j=1; j<=m; j++)
> 			if(!visited[j] && (graph[k][j] < cost[j] ) )
> 				cost[j] = graph[k][j], pre[j] = k;
> 	}
> }
> void dfs( int now )
> {
> 	flag[now] = true;
> 	for ( int i=1; i <= m; i++)
> 	{
> 		if(flag[i])
> 			continue;
> 		if ( edge[i][now] || edge[now][i])
> 		{
> 			//pre[ i ] = now;
> 		    if( value[ now][0].val < graph[i][now] )
> 			{
> 				value[i][0].val = graph[i][now];
> 				value[i][0].a = now;
> 				value[i][0].b = i;
> 			}
> 			else
> 			{
> 				value[i][0] = value[now][0];
> 			}
> 			dfs( i );
> 			
> 		}
> 	}
> }
> 
> int result( )
> {
> 	int i, j;
> 	int minval=INF;
> 	int index;
> 
> 	for (i=1; i<=m; i++)
> 	{
> 		if( graph[i][0] <INF && minval > graph[i][0] )
> 		{
> 			minval = graph[i][0];
> 			index = i;//先添加的第一条最小权值的边
> 		}
> 	}
> 	total += minval;
> 	edge[0][index] = edge[index][0] = 1;//表明这里的边已经添加到生成树里面
> 	/*for (i=1; i<=m; i++)
> 	{
> 		value[i][0] = value[0][i] = value[i][index];
> 	}
> 	pre[0] = i;*/
> 	int mininum ;
> 	int p1 = index;
> 
> 	for (i = 2; i <= k && i <= m; i++)
> 	{
> 		
> 		mininum = INF;
> 		memset(flag, false, sizeof(flag));
> 		dfs( p1 );
> 		for (j = 1; j <= m; j++)
> 		{
> 			if( graph[j][0] != INF && !edge[j][0])//stand for there is an edge between them并且这条边还没有被添加
> 			{
> 			   if( graph[j][0] - value[j][0].val < mininum)
> 			   {
> 			      mininum =  graph[j][0] - value[j][0].val;//最少添删
> 			      p1 = j;
> 			   }
> 			}
> 		}
> 		edge[ p1 ][ 0 ] = edge[0][p1] = true;
> 		value[ p1][ 0 ].val =  0;
> 		edge[ value[p1][0].a ][ value[p1][0].b ] = false;
> 		edge[ value[p1][0].b ][ value[p1][0].a ] = false;
> 		if( mininum >= 0 )
> 			return total;
> 		total += mininum;
> 		
> 		
> 	}
> 	return total;
> }
> 
> int main()
> {
> 	freopen("in.txt","r",stdin);
> 	while (scanf("%d", &n) ==1)
> 	{
>         m = 0;
> 		init();
> 		for (int i=0; i < n; i++)
> 		{
> 			scanf("%s%s%d", name1, name2, &val);
> 			deal( name1, name2, val);
> 		}
> 		scanf("%d",&k);
> 		prim();
> 		printf("Total miles driven: %d\n", result() );
> 
> 	}
> 	return 0;
> }
> 		
> 
> 
>