do
{
State=FindMin();
if (State!=0)
{
SetNum=SetNum+1;
is_arrived[State]=true;
Length=Length+Dist[State];
for(p=1;p<=Vertex;p++)
if ((Map[State][p]<Dist[p])&&(!is_arrived[p]))
Dist[p]=Map[State][p];
}
else
break;
}
while (SetNum!=Vertex);
if (SetNum!=Vertex)
fout << "The graph is not connected!";
else
fout << Length;
fin.close();
fout.close();
return 0;
}
Sample Input
7
00 20 50 30 00 00 00
20 00 25 00 00 70 00
50 25 00 40 25 50 00
30 00 40 00 55 00 00
00 00 25 55 00 10 70
00 70 50 00 10 00 50
00 00 00 00 70 50 00
Sample Output
160
//用于搜索最短连接路径的快速方法
void prime()
{
int i,j,k=0;
int v0=1;
int min;
for( i=1; i<=cases; i++ )
{
lowcost=cost[v0];
closest=v0;
}
lowcost[v0]=-1;
for( i=1; i<cases; i++ )
{
min=max;
for( j=1; j<=cases; j++ )
{
if( lowcost[j]<min && lowcost[j]!=-1)
{
min=lowcost[j];
k=j;
}
}
sum+=lowcost[k];
//printf("sum=%d\n",sum);
//printf("k=%d\n",k);
lowcost[k]=-1;
for( j=1; j<=cases; j++ )
{
if( cost[k][j]<lowcost[j] && lowcost[j]!=-1 )
{
lowcost[j]=cost[k][j];
closest[j]=k;
}
}
}
}
上一页 [1] [2]
责任编辑：小草
