现在的位置: 首页 > 综合 > 正文

poj 1251 Jungle Roads

2017年10月18日 ⁄ 综合 ⁄ 共 782字 ⁄ 字号 评论关闭

 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;
}

抱歉!评论已关闭.