http://acm.hdu.edu.cn/showproblem.php?pid=1102
#include <iostream>
#include <cmath>
using namespace std;
const int M=27;
const int MAX=10000000;
int map[M][M];
int dis[M]; //存储i节点到当前节点的最短距离
bool visit[M];
int n;
int res; //结果
int min(int a,int b)
{
return a<b?a:b;
}
void prim(int v)
{
int i,j,t;
int min;
for(i=1;i<=n;i++)
{
dis[i]=map[v][i];
visit[i]=false;
}
visit[v]=true;
res=0;
for(t=1;t<n;t++) //找点
{
min=MAX;
for(i=1;i<=n;i++)
if(dis[i]<min && !visit[i]) //找到未访问过的到当前节点最短的点
{
min=dis[i];
j=i;
}
if(min==MAX)
break;
res+=min;
visit[j]=true;
for(i=1;i<=n;i++) //更新dis数组
if(map[j][i]<dis[i])
dis[i]=map[j][i];
}
}
int main()
{
int i,j,k,d,t;
char ch,c;
while(scanf("%d",&n)!=EOF,n)
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i==j)
map[i][j]=0;
else
map[i][j]=MAX;
for(t=1;t<n;t++)
{
scanf("%c%c",&c,&ch);
//cin>>ch;
i=ch-'A'+1;
scanf("%d",&k);
while(k--)
{
scanf("%c%c",&c,&ch);
//cin>>ch;
j=ch-'A'+1;
scanf("%d",&d);
map[i][j]=map[j][i]=d;
}
}
prim(1);
printf("%d\n",res);
}
return 0;
}
posted on 2011-09-16 15:43
大大木马 阅读(121)
评论(0) 编辑 收藏 引用