1301.cpp

杭电 acm部分代码 有兴趣的可以下载 谢谢

#include<iostream>
#include<string>
using namespace std;
int road[30][30];
bool pass[30];
const int MAX=1000000;
void main()
{
    int n,num,len,t,i,j,min;
    char a,b;
    while(cin>>n){
        if(!n)  break;
        memset(road,0,sizeof(road));
        memset(pass,0,sizeof(pass));
        t=n;
        while(t---1){
            cin>>a>>num;
            while(num--){
                cin>>b>>len;
                road[a-65][b-65]=road[b-65][a-65]=len;
            }
        }
        min=MAX;
        int i_index,j_index,sum=0;
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
                if(road[i][j]!=0&&i!=j&&road[i][j]<min){
                    min=road[i][j];
                    i_index=i;
                    j_index=j;
                }
        pass[i_index]=true;
        pass[j_index]=true;
        sum+=min;
        for(int ca=1;ca<n;ca++){
            min=MAX;
            for(i=0;i<n;i++)
                for(j=0;j<n;j++)
                    if(pass[i]==true&&pass[j]==false&&road[i][j]!=0&&i!=j&&min>road[i][j]){
                        min=road[i][j];
                        j_index=j;
                    }
            if(min<MAX)
                sum+=min;
            pass[j_index]=true;
        }
        cout<<sum<<endl;
    }
}