学步园

链接：点击打开链接

给n个房子,你需要在房子之间铺电缆,使所有的房子都连上,求最短的电缆,注意在poj上遇到double类型的，都用%f，不要用%lf，用%lf出现WA。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const float INF=0xffffff;
float edge[510][510],len;
int nn,vis[510];
void prime(int x){
 int i,j,k;
 float mark[510],mi_n;
 float sum_i;
 for(i=1;i<=nn;i++){
  mark[i]=edge[x][i];
  vis[i]=0;
 }
 vis[x]=1;
 sum_i=0.0;
 for(i=2;i<=nn;i++){
   mi_n=INF;
   for(j=1;j<=nn;j++){
    if(!vis[j]&&mark[j]<mi_n){
    mi_n=mark[j];
    k=j;
    }
   }
   vis[k]=1;
   sum_i+=mi_n;
   if(sum_i>=INF)
   break;
   for(j=1;j<=nn;j++){
    if(!vis[j]&&edge[k][j]<mark[j])
    mark[j]=edge[k][j];
   }
 }
 if(sum_i<=len)
 printf("Need %.1f miles of cable\n",sum_i);
 else printf("Not enough cable\n");
}
int main(){
 int i,j,a,m,x,y;
 float l;
 char str1[510][25],str2[25],str3[25];
 while(~scanf("%f",&len)){
    scanf("%d",&nn);
    for(i=1;i<=nn;i++)
    for(j=1;j<=nn;j++)
    edge[i][j]=INF;
    for(i=1;i<=nn;i++)
    scanf("%s",str1[i]);
    scanf("%d",&m);
    while(m--){
    scanf("%s %s %f",str2,str3,&l);
    for(j=1;j<=nn;j++){
     if(!strcmp(str1[j],str2))
     x=j;
     if(!strcmp(str1[j],str3))
     y=j;
    }
    edge[x][y]=l;
    edge[y][x]=l;
    }
    prime(1);
 }
 return 0;
}