这题就是最小生成树的模板题，可是这题的数据给的有点坑。

首先我不清楚给出的村庄是否就是按照从A开始的字母顺序排列，所以我就用一个exist布尔数组来标记这个村庄是否存在；

在者就是两个村庄之间可能有多条路，所以存储的时候应该存储最小的，可是题目没有这样的例子，哎！

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         using namespace std; const int inf=1<<28; int road[27][27],mincost[27]; bool used[27],exist[27]; int n; int solve() { fill(mincost,mincost+27,inf); memset(used,false,sizeof(used)); for(int i=1;i<=26;i++) if(exist[i]) { mincost[1]=0; break; } int cost=0; while(true) { int _min=inf,u=-1; for(int i=1;i<=26;i++) if(exist[i]&&!used[i]&&_min>mincost[i]) _min=mincost[i],u=i; if(u==-1) break; used[u]=true; cost+=_min; for(int i=1;i<=n;i++) if(exist[i]) mincost[i]=min(mincost[i],road[u][i]); } return cost; } int main() { while(scanf("%d",&n),n!=0) { char s1[2],s2[2]; for(int i=0;i<27;i++) for(int j=0;j<27;j++) road[i][j]=inf; int m,k,a,b; memset(exist,false,sizeof(exist)); for(int i=1;i