算法的原理挺很简单的，写起来超级复杂……
调了一天了……
不行，我要可耻地贴代码！！（代码略长，3380B，不过这是因为注释写得太多了！！）
#include <stdio.h>
#include <string.h>
#define MAXN 510
#define MAXL 20
#define INF (1<<28)
int n,limit,tot=0,dist[MAXN][MAXN];	//tot为小矮人的总数
int deg0,ncc,d[MAXN],pre[MAXN]={0};		//deg0为原图中V0的度,pre[i]为生成树上i的前点
int best[MAXN],bestnum[MAXN],rev[MAXN];
	//best[i]为i到根节点V0路径上最长边的值,bestnum[i]表示最长边的编号，即最长边是<bestnum[i], pre[bestnum[i]]>

int ans=0;			//ans为最终的答案
char name[MAXN][MAXL];
bool visit[MAXN],flag[MAXN];	//flag[i]表示i是否已被加入到最小生成森林中

void GetData(){
	int i,j,x,u,v;
	char str[MAXL];

	scanf("%d", &n);
	strcpy(name[0], "Park");

	for (i=0;i<MAXN;++i)
		for (j=0;j<MAXN;++j)
			dist[i][j]=INF;

	for (i=0;i<n;++i){
		scanf("%s", str);
		for (u=-1,j=0;j<=tot;++j)
			if ( strcmp(str, name[j])==0 )	{u=j;break;}
			if (u<0)	strcpy(name[u=++tot], str);
		
		scanf("%s", str);
		for (v=-1,j=0;j<=tot;++j)
			if ( strcmp(str, name[j])==0 )	{v=j;break;}
		if (v<0)	strcpy(name[v=++tot], str);

		scanf("%d", &x);
		if (dist[u][v]>x)	dist[u][v]=dist[v][u]=x;
	}
}


int Prim(){	//求最小生成树，将生成树中的节点编号保存在node[ncc][]中,并且返回生成树所连接的节点的个数
	int s,i,j,k,cnt,mind,res=0;	//res为本棵生成树的大小
	for (mind=INF,i=1;i<=tot;++i)	//找一个未添加到最小生成森林中,且距离源点V0最近的点s，作为本颗子树的根节点进行拓展
		if (!flag[i] && dist[0][i]<mind)	mind=dist[0][s=i];

	for (i=1;i<=tot;++i){
		if (flag[i])	continue;	//注意只对尚未加入生成森林中的节点进行操作(否则将不慎修改已处理过的点的pre[]指针)
		visit[i]=false;
		pre[i]=s;
		d[i]=dist[s][i];
	}
	pre[s]=d[s]=0;	//直接将s的根置为V0,后面的编程会很方便
	flag[s]=visit[s]=true;

	for (cnt=i=1;i<tot;++i){
		for (mind=INF,j=1;j<=tot;++j)
			if (!visit[j] && mind>d[j])		mind=d[k=j];
		if (mind==INF)		break;	//图形不连通，结束算法
		flag[k]=visit[k]=true;
		++cnt;						//已加入树中的节点数+1
		res+=d[k];

		for (j=1;j<=tot;++j)
			if (!visit[j] && d[j]>dist[k][j])	d[j]=dist[pre[j]=k][j];
	}

	ans += res + dist[0][s];
	return cnt;
}

void Reverse(int i){		//维护: 删除最长边后有些节点到根节点V0的距离就变了，要注意把相应的边反向，即i和pre[i]互换
	int top=0,end=bestnum[i];
	rev[0]=0;
	while (i!=end)		{rev[++top]=i;i=pre[i];}
	rev[++top]=i;
	for (i=top;i>0;--i)		pre[rev[i]]=rev[i-1];
}

int GetBest(int i){		//记忆化搜索
	if (best[i])		return best[i];		//已计算过则返回
	if (!pre[i])		return best[i]=-INF;
	int tmp=GetBest(pre[i]);	//tmp=best[pre[i]];
	if (tmp<dist[pre[i]][i]){
		best[i]=dist[pre[i]][i];	//best[i]为 边<pre[i],i> 和 pre[i]到V0路径上的最长边 中较长的一个
		bestnum[i]=i;
	}
	else{
		best[i]=tmp;
		bestnum[i]=bestnum[pre[i]];
	}
	return best[i];
}

void Solve(){
	scanf("%d", &limit);
	int i,k,ktree,choose,delta;
	for (deg0=i=1;i<n;++i)
		if (dist[0][i]!=INF)	++deg0;
	memset(flag,0,sizeof(flag));
	ans=ncc=k=0;
	while (k<tot)		{++ncc;k+=Prim();}	//先求除去点V0外的最小生成森林。k表示已选择的小矮人的个数,ncc为除去V0点后连通分量的总数
	ktree=ans;	//ktree为此时度限制生成树的大小

	while (ncc<limit){		//ncc为此时V0的度
		if (ncc==deg0)	break;	//此时已无法更新，因为V0连出的所有边都被选用了，可直接退出循环
		++ncc;
		memset(best,0,sizeof(best));
		memset(bestnum,0,sizeof(bestnum));
	
		best[0]=-INF;		//预处理任一点到V0路径上的最长边
		for (i=1;i<=tot;++i)	GetBest(i);
		for (delta=INF,i=1;i<=tot;++i){	//进行最小添删操作
			if (pre[i] && dist[0][i]!=INF && dist[0][i]-best[i]<delta) {
				delta=dist[0][i] - best[i];	//若这个顶点的前一个点不是V0,并且删除最大边后的添删值小于delta,选择这个顶点并记录
				choose=i;
			}
		}
		Reverse(choose);		//维护树的形状
		ktree+=delta;	//ktree为此时度限制生成树的大小
		if (ktree<ans)		ans=ktree;
	}

	printf("Total miles driven: %d\n", ans);
}

int main(){
	GetData();
	Solve();
	return 0;
}