poj 1251 Jungle Roads
#include <iostream> using namespace std; int lowcost[30]; bool f[30]; int w[30][30]; int t; int getValue(char a){ return a-64; } int prim(){ memset(f,0,sizeof(f)); memset(lowcost,0,sizeof(lowcost)); int i,j; f[1]=1; for(i=2;i<=t;i++) lowcost[i]=w[1][i]; int ans=0; for(i=1;i<t;i++){ int v; int min=100*100*127; for(j=1;j<=t;j++){ if(f[j]==0&&lowcost[j]<min){ min=lowcost[j]; v=j; } } ans+=min; f[v]=1; for(j=1;j<=t;j++){ if(f[j]==0&&w[v][j]<lowcost[j]){ lowcost[j]=w[v][j]; } } } return ans; } int main(){ while(cin>>t&&t!=0){ int i,j; for(i=1;i<=t;i++){ for(j=1;j<=t;j++){ if(i!=j)w[i][j]=100*100*127; else w[i][j]=0; } } for(i=1;i<t;i++){ char a; int m; cin>>a; cin>>m; if(m>0){ for(j=1;j<=m;j++){ char b; cin>>b; cin>>w[getValue(a)][getValue(b)]; w[getValue(b)][getValue(a)]=w[getValue(a)][getValue(b)]; } } } cout<<prim()<<endl; } return 0; }