解题思路

问题分析： 这是一个典型的最小生成树（$MST$）问题，目标是找到连接所有房屋所需的最短电缆长度。可以使用$Prim$算法或$Kruskal$算法来解决。

输入处理： 首先读取电缆长度，然后读取房屋数量及其名称，接着读取路径信息并将其转换为图的邻接矩阵表示。

Prim算法： 从任意一个节点开始，逐步选择与当前生成树距离最短的节点加入生成树，并更新其他节点到生成树的距离，直到所有节点都被包含。

输出结果： 比较生成树的总权重与给定的电缆长度，输出相应结果。

解题方法

图的表示： 使用邻接矩阵存储房屋之间的距离，初始时不相连的房屋距离设为无穷大。

Prim算法实现：

初始化：选择一个起始节点（如第一个房屋），标记为已访问，初始化其他节点到生成树的距离。

迭代：每次选择距离当前生成树最近的未访问节点加入生成树，并更新其他未访问节点的距离。

累加： 每次加入新节点时，累加其对应的边权重。

C++代码实现：

#include<stdio.h>
#include<string.h>
#define INF 0xfffffff
#define N 1010
char s[10000][30];
double map[N][N],cost[N],m,outcome;
int country,road,v[N];
void prim()
{
	int i,j,next;
	double mincost;
	memset(v,0,sizeof(v));
	for(i=0;i<country;i++)
	{
	 cost[i]=map[0][i];
   
	 }
	 v[0]=1;
	 for(i=1;i<country;i++)//寻找最短的距离 
	  {
	  	mincost=INF;
	  	for(j=0;j<country;j++)
	  	 {
	  	 	if(!v[j]&&mincost>cost[j])
	  	 	{
	  	 		mincost=cost[j];
	  	 		next=j;
			}
		   }
		   outcome+=mincost;
		   v[next]=1;
		   for(j=0;j<country;j++)//更新路径 
		    {
		    	if(!v[j]&&cost[j]>map[next][j])
		    	{
		    		cost[j]=map[next][j];
				}
			}
	  }
}
int main()
{
	int i,j;
	double l;
	char a[30],b[30];
	while(scanf("%lf",&m)!=EOF)
	{
	scanf("%d",&country);
	for(i=0;i< country;i++)
	 scanf("%s",s[i]);
	 scanf("%d",&road);
	 for(i=0;i<country;i++)
	  {
	  	for(j=0;j<country;j++)
	  	 {
	  	 	if(i==j)
	  	 	map[i][j]=0;
	  	 	else
	  	 	map[i][j]=INF;
		   }
	  }
	 for(i=0;i<road;i++)//字符转化为点 
	  {
	  	scanf("%s%s%lf",a,b,&l);
	  	int k,t;
	  	for(j=0;j<country;j++)
	  	{
	  		if(strcmp(s[j],a)==0)
	  		 k=j; 
		}
		  for(j=0;j<country;j++)
		   {
		   	
		   		if(strcmp(s[j],b)==0)
	  		      t=j;
		   }
		    map[t][k]=map[k][t]=l;
	  }
	  prim();
	  if(outcome<=m)
	  printf("Need %.1f miles of cable\n",outcome);
	  else
	  printf("Not enough cable\n");
	return 0;
}
}

结果判断：比较生成树的总权重与电缆长度，输出相应结果。