题解 | Jungle Roads

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int fa[30];


typedef struct Link{
    char a,b;
    int len;
}L;



bool cmp(L l1,L l2)
{
    return l1.len<l2.len;
}


int find(int x)
{
    if(fa[x]==x)return x;
    return fa[x] = find(fa[x]);
}

void init(int n)
{
    for(int i=0;i<n;i++)
    {
        fa[i]=i;
    }
    
}


int main() {
    int n;
    while(cin>>n)
    {
        if(n==0)break;
        init(n);
        L li[100];
        int len=0 ;
        for(int i = 0;i<n-1;i++)
        {

            int num;
            char c;
            cin>>c>>num;
            if(num>0)
            {
                int num1;
                char c1;
                for(int j=0;j<num;j++)
                {
                    cin>>c1>>num1;
                    li[len].a = c;
                    li[len].b = c1;
                    li[len].len =num1;
                    len++;
                }
            }

        }
        sort(li,li+len,cmp);
        int cnt=0,ans=0;
        for(int i=0;i<len;i++)
        {
            int f1 = find(li[i].a-'A');
            int f2 = find(li[i].b-'A');
            if(f1!=f2)
            {
                fa[f2] = f1;
                cnt++;
                ans+=li[i].len;
            }
            if(cnt==n-1)break;

        }
        cout<<ans<<endl;
    }
}
// 64 位输出请用 printf("%lld")