Jungle Roads

/*
    最小生成树+Kruskal的问题
    这种问题就是初始化边，然后给边排序，利用Kruskal就可以解决
    这个问题描述真的是看的我头皮发麻。
    就是有n个村庄，然后要你计算最小的维护成本，其实就是求一个最小生成树
    9  // 这个是总的村庄数量
    A 2 B 12 I 25 // 开头A是起点，后面的2是指A有多少条道路去往别的村庄,B和12就是目的地和成本了
*/
#include <bits/stdc++.h>
using namespace std;
const int VMAXN = 26; // 村庄的最大数
const int RMAXN = 75; // 道路的最大数
struct Road{
	int from,to;
	int cost;
};
bool cmp(Road a,Road b){// 按照维护成本排序
	return a.cost<b.cost;
}
int father[VMAXN]; // 并查集
int height[VMAXN]; // 路径的高度
Road road[VMAXN*VMAXN];
int getRoot(int x){ // 获取其根节点
	if(x!=father[x]){
		father[x] = getRoot(father[x]);
	}
	return father[x];
}
void Union(int x,int y){ // 将两个不同集合的点合并为一个并且做路径压缩
	x = getRoot(x);
	y = getRoot(y);
	if(x!=y){
		if(height[x]<height[y]){
			father[x] = y;
		}else if(height[x]>height[y]){
			father[y] = x;
		}else{
			father[y] = x;
			height[x]++;
		}
	}
}
void init(){ // 初始化函数
	for(int i=0;i<VMAXN;i++){
		father[i] = i;
		height[i] = 0;
	}
}
int Kruskal(int vNum,int rNum){ // Kruskal 算法
	int sum = 0;
	sort(road,road+rNum,cmp); // 给边排序
	for(int i=0;i<rNum&&vNum>1;i++){
		Road cur = road[i];
		if(getRoot(cur.from)!=getRoot(cur.to)){
			Union(cur.from,cur.to);
			sum+=cur.cost;
			vNum--;
		}
	}
	return sum;
}
int main(){
	int n;
	while(scanf("%d",&n)!=EOF&&n){
		init(); // 初始化
		char v; // 记录每次输入的村庄数
		int num,cost,rNum=0;// num 用来记录每次输入的道路条路，cost记录成本，rNum记录总的道路数
		getchar(); // 吃掉空格，如果用cin不知道这一步可不可以省去，可以自己试一下
		for(int i=0;i<n-1;i++){ // 村庄的个数
			scanf("%c%d",&v,&num); // A 2
			getchar(); // 吃掉空格
			int from = v-'A'; // 当前村庄的下标
			for(int j=0;j<num;j++){
				scanf("%c%d",&v,&cost);
				int to = v-'A'; // 目的地村庄
				road[rNum].from = from;
				road[rNum].to = to;
				road[rNum++].cost = cost;
				getchar(); // 吃掉空格和回车
			}
		}
		int answer = Kruskal(n,rNum);
		printf("%d\n",answer);
	}
	return 0;
}

代码又臭又长，而且样例有坑

#define N 26
#define INF 10000
using namespace std;

int n, G[N][N];
int d[N];
bool vis[N];

void init(){
    int road, cost;
    char start, end;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(i == j)
                G[i][j] = 0;
            else{
                G[i][j] = INF;
                G[j][i] = INF;
            }
        }
    }
    for(int i = 0; i < n - 1; i++){
        cin >> start >> road;
        for(int j = 0; j < road; j++){
            cin >> end >> cost;
            if(cost < G[start - 'A'][end - 'A']){
                G[start - 'A'][end - 'A'] = cost;
                G[end - 'A'][start - 'A'] = cost;
            }
        }
    }
    fill(d, d + N, INF);
    d[0] = 0;
    fill(vis, vis + N, false);

    /*cout << '\t';
    for(int i = 0; i < n; i++){
        cout << (char)('A' + i) << '\t';
    }
    cout << endl;
    for(int i = 0; i < n; i++){
        cout << (char)('A' + i) << '\t';
        for(int j = 0; j < n; j++){
            cout << G[i][j] << '\t';
        }
        cout << endl;
    }*/
}

int prim(){
    int ans = 0;
    for(int i = 0; i < n; i++){
        int u = -1;
        int MIN = INF;
        for(int j = 0; j < n; j++){
            if(vis[j] == false && d[j] < MIN){
                u = j;
                MIN = d[j];
            }
        }
        if(u == -1)
            return ans;
        vis[u] = true;
        ans += d[u];
        for(int v = 0; v < n; v++){
            if(vis[v] == false && G[u][v] != INF && G[u][v] < d[v]){
                d[v] = G[u][v];
            }
        }
    }
    return ans;
}

int main(){
    while(cin >> n){
        init();
        cout << prim() << endl;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
struct Edge
{
    int from;
    int to;
    int cost;
    bool operator<(const Edge&e)const{
        return cost<e.cost;
    }
};
const int MAXN=26;
Edge edge[MAXN*MAXN];
int father[MAXN];
int height[MAXN];
void Initial(int n)
{
    for(int i=0;i<n;i++)
    {
        father[i]=i;
        height[i]=0;
    }
}
int Find(int x)
{
    if(x!=father[x])
        father[x]=Find(father[x]);
    return father[x];
}
void Union(int x,int y)
{
    x=Find(x);
    y=Find(y);
    if(x!=y)
    {
        if(height[x]>height[y])
            father[y]=x;
        else if(height[y]>height[x])
            father[x]=y;
        else 
        {
            father[y]=x;
            height[x]++;
        }
    }
    return ;
}
int KrusKal(int n,int edgeNumber)
{
    Initial(n);
    sort(edge, edge+edgeNumber);
    int answer=0;
    for(int i=0;i<edgeNumber;i++)
    {
        if(Find(edge[i].from)!=Find(edge[i].to))
        {
            Union(edge[i].from, edge[i].to);
            answer+=edge[i].cost;
        }
    }
    return answer;
}
int main()
{
    int n;
    while(cin>>n&&n!=0)
    {
        int edgeNumber=0;
        int count=0;
        for(int i=0;i<n-1;i++)
        {
            char from;
            cin>>from;
            int k;
            cin>>k;
            edgeNumber+=k;
            while(k--)
            {
                char to;
                int cost;
                cin>>to>>cost;
                edge[count].from=from-'A';
                edge[count].to=to-'A';
                edge[count++].cost=cost;
            }
        }
        cout<<KrusKal(n, edgeNumber)<<endl;
    }
    return 0;
}

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
struct edge
{
	char start, end;
	int distance;
	edge(char s, char e, int d) :start(s), end(e), distance(d) {}
};
bool comp(edge e1, edge e2)
{
	return e1.distance < e2.distance;
}
char find_root(map<char, char>& V, char x)//检查x所在集合的根
{
	if (V.find(x) != V.end() && V[x] != x)
		V[x] = find_root(V, V[x]);
	else
		return x;
	return V[x];
}
int kruskal(vector<edge>& E, int n)//最小生成树 克鲁斯卡尔算法O(ElogE)
{
	int sum = 0, count = 0;//边权值和，边的条数

	map<char, char> V;//顶点集/并查集

	vector<edge>::iterator it = E.begin();
	while (count != n - 1)//n个顶点的树n-1条边
	{
		while (it != E.end())//边已经排序了
		{
			int a = find_root(V, it->start);
			int b = find_root(V, it->end);
			if (a != b)//不在集合中，即没有构成回路
			{
				V[b] = a;//并入集合
				sum += it->distance;
				it++;
				break;
			}
			else
				it++;
		}
		count++;
	}
	return sum;
}
int main()
{
	int n;
	vector<edge> E;
	while (cin>>n && n != 0)
	{
		for (int i = 0; i < n - 1; i++)
		{
			char start;
			int m;
			cin >> start >> m;
			for (int i = 0; i < m; i++)
			{
				char end;
				int dis;
				cin >> end >> dis;
				E.push_back(edge(start, end, dis));
			}
		}
		sort(E.begin(), E.end(), comp);
		cout << kruskal(E, n) << endl;
		E.clear();
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
map<char, int> mp;
const int INF = 0x3f3f3f3f;
const int maxv = 30;
int g[maxv][maxv];
int dis[maxv];
bool vis[maxv];
int prim(int n)
{
    fill(dis, dis + 1 + n, INF);
    memset(vis, 0, sizeof(vis));
    dis[1] = 0;
    int ans = 0;
    for(int i = 0; i < n; ++i)
    {
        int u = -1, minn = INF;
        for(int j = 1; j <= n; ++j)
        {
            if(!vis[j] && dis[j] < minn)
            {
                u = j;
                minn = dis[j];
            }
        }
        if(u == -1)
            break;
        vis[u] = 1;
        ans += dis[u];
        for(int v = 1; v <= n; ++v)
        {
            if(!vis[v] && g[u][v] != INF && g[u][v] < dis[v])
                dis[v] = g[u][v];
        }
    }
    return ans;
}
int main()
{
    int n, m, w;
    char u, v;
    while(~scanf("%d", &n) && n)
    {
        int k = 0;
        mp.clear();
        fill(g[0], g[0] + maxv * maxv, INF);
        for(int i = 0; i < n - 1; ++i)
        {
            scanf("%*c%c %d", &u, &m);
            if(!mp[u])
                mp[u] = ++k;
            while(m--)
            {
                scanf("%*c%c %d", &v, &w);
                if(!mp[v])
                    mp[v] = ++k;
                g[mp[v]][mp[u]] = g[mp[u]][mp[v]] = min(g[mp[u]][mp[v]], w);
            }
        }
        printf("%d\n", prim(n));
    }
    return 0;
}

#define _CRT_SECURE_NO_WARNINGS
(842)#include <iostream>
#include <cstdio>
(802)#include <cstdlib>
#include <algorithm>
using namespace std;
const int maxn = 27;
int father[maxn];
int height[maxn];
struct edge {
	int from;
	int to;
	int length;
}e[maxn*maxn];

bool cmp(edge e1, edge e2) {
	return e1.length < e2.length;
}

void initial(int i) {
	father[i] = i;
	height[i] = 0;
}

int find(int i) {
	if (i != father[i]) {
		father[i] = find(father[i]);
	}
	return father[i];
}

void Union(int i, int j) {
	int x = find(i);
	int y = find(j);
	if (x != y) {
		if (height[x] < height[y]) {
			father[x] = y;
		}
		else if (height[y] < height[x]) {
			father[y] = x;
		}
		else {
			father[y] = x;
			height[x]++;
		}
	}
}

int kruskal(int n, int k) {
	int sum = 0;
	for (int i = 0; i < k; i++) {
		if (find(e[i].from) != find(e[i].to)) {
			Union(e[i].from, e[i].to);
			sum += e[i].length;
		}
	}
	return sum;
}

int main() {
	int n;
	while (scanf("%d", &n) != EOF) {
		if (n == 0) break;
		for (int i = 0; i < n; i++) {
			initial(i);
		}
		int now = 0, v = n;
		while (--v) {
			char x, y;
			int po1, len, po2;
			getchar();
			scanf("%c", &x);
			po1 = x - 'A';
			int m;
			scanf("%d", &m);
			for (int i = 0; i < m; i++) {
				getchar();
				scanf("%c %d", &y, &len);
				po2 = y - 'A';
				e[now].from = po1;
				e[now].to = po2;
				e[now].length = len;
				now++;
			}
		}
		sort(e, e + now, cmp);
		int answer = kruskal(n, now);
		printf("%d\n", answer);
	}
	system("pause");
	return 0;
}

/**
*最小生成树，求最小的养路费用
*萌新什么也不会，只会查并集，有什么办法
*节点字母转化成数字，然后就和Freckles那题差不多了
*@time 2019-06-27
*/
#include "stdio.h"
#include "stdlib.h"
#define canAdd(x) ((find(x.p)==find(x.q)) ? 0 : 1)
#define add(x) father[find((x).q)]=father[find((x).p)]
struct E{
    int p,q,cost;
}edge[75];
int cmp(const void * p1, const void * p2){
    return (((struct E *)p2)->cost - ((struct E *)p1)->cost);
}
int father[26];
int find(int p){
    while(p != father[p])
        p = father[p];
   return p;
}
int main(){
    int n, total;
    char p, q;
    while(scanf("%d%*c", &n) != EOF && n!= 0){
        int i = n;
        while(i--) father[i] = i;
        int num = 0;
        i = n - 1;
        while(i--){
            int k;
            scanf("%c%d%*c", &p, &k);
            while(k--){//根据输入初始化边的结构体
                edge[num].p = p - 'A';
                scanf("%c%d%*c", &q, &edge[num].cost);
                edge[num].q = q - 'A';
                //father[edge[num].q] = edge[num].p;我***把这句话放在这里，调试了半天
                num++;
            }
        }
        qsort(edge, num, sizeof(edge[0]), cmp);//qsort函数的size究竟是num还num-1没想清楚
        total = 0;
        while(num--){
            if(canAdd(edge[num])) {
                add(edge[num]);
                total += edge[num].cost;
            }
        }
        printf("%d\n", total);
    }
    return 0;
}

#include <iostream>
#include <algorithm>

using namespace std;

#define Idx(c)    (c-'A')
#define    MAXV    (27)
int tree[MAXV];

int findRoot(int x)
{
    if (tree[x] == -1)
        return x;
    tree[x] = findRoot(tree[x]);

    return tree[x];
}

struct Edge {
    char s, e;
    int cost;

    bool operator < (const Edge &A) const {
        return cost < A.cost;
    }
};

#define MAXE    (75)
Edge edge[MAXE];


int main()
{
    int n;

    while (cin >> n && n != 0) {
        int edgeNum = 0;
        for (int i = 0; i < n-1; ++i) {
            char s, e;
            int k, cost;
            cin >> s >> k;
            for (int i = 0; i < k; ++i) {
                cin >> e >> cost;
                edge[edgeNum].s = s;
                edge[edgeNum].e = e;
                edge[edgeNum].cost = cost;
                edgeNum++;
            }
        }
        sort(edge, edge+edgeNum);

        for (int i = 0; i < n; ++i)
            tree[i] = -1;

        int total = 0;
        for (int i = 0; i < edgeNum; ++i) {
            int a = findRoot(Idx(edge[i].s));
            int b = findRoot(Idx(edge[i].e));
            if (a != b) {
                tree[a] = b;
                total += edge[i].cost;
            }
        }
        cout << total << endl;
    }

    return 0;
}

#include <iostream>
#include <limits.h>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 105
void prim(int n, double c[N][N]){
    double sum = 0;
    double *lowcost = new double[n];
    int *closest = new int[n];
    bool *s = new bool[n];
    s[0] = true;
    for (int i = 1; i < n; i++){
        lowcost[i] = c[0][i];
        closest[i] = 0;
        s[i] = false;
    }
    for (int i = 1; i<n; i++){
        double min = INT_MAX;
        int j = 0;
        for (int k = 1; k <n; k++){
            if (lowcost[k]<min && (!s[k])){
                min = lowcost[k];
                j = k;
            }
        }
        //可能所有节点构成多颗树，去除不需要的边
        if (c[j][closest[j]] < 10000){
            sum += c[j][closest[j]];
        }
        s[j] = true;
        for (int k = 1; k < n; k++){
            if ((c[j][k]<lowcost[k]) && (!s[k])){
                lowcost[k] = c[j][k];
                closest[k] = j;
            }
        }
    }
    cout << sum << endl;
}

int main(){
    int n;
    while (cin >> n){
        double c[N][N], coord[N][2];
        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                c[i][j] = 10000;
            }
        }
        char c1, c2;
        int n1, n2, k;
        double dist;
        for (int i = 1; i<n; i++){
            cin >> c1;
            n1 = c1 - 'A';
            cin >> k;
            while (k--){
                cin >> c2 >> dist;
                n2 = c2 - 'A';
                c[n1][n2] = c[n2][n1] = min(dist, c[n1][n2]);
            }
        }
        prim(n, c);
    }
}

#include<stdio.h>
#include<algorithm>
#include<string.h>
#define N 27
using namespace std;
int Tree[N];
typedef struct Edge{
    char a,b;
    int cost;
}Edge;
int FindRoot(int x){
    if(Tree[x]==-1) return x;
    else{
        Tree[x]=FindRoot(Tree[x]);
        return Tree[x];
    }
}
int cmp(Edge a,Edge b){
    return a.cost<b.cost;
}
int main(){
    int n;
    while(scanf("%d",&n)!=EOF&&n!=0){
        getchar();
        int k,i,size=0;
        Edge e[N*(N-1)/2];
        char tmp;
        for(i=0;i<n;i++)
            Tree[i]=-1;
        for(i=0;i<n-1;i++){
            scanf("%c%d",&tmp,&k);
            getchar();
            while(k--){
                e[size].a=tmp;
                scanf("%c%d",&e[size].b,&e[size].cost);
                size++;
                getchar();
            }
        }
        sort(e,e+size,cmp);
        int cost=0;
        for(i=0;i<size;i++){
            int a,b;
            a=FindRoot(e[i].a-'A');
            b=FindRoot(e[i].b-'A');
            if(a!=b){
                Tree[b]=a;
                cost+=e[i].cost;
            }
        }
        printf("%d\n",cost);
    }
    return 0;
}

	

大家帮我看看怎么回事啊，数组越界
发生在flag[start] = true 那

mport java.util.Scanner;

/** 
*
* @author special
* @date 2017年12月28日 上午11:11:18
*/
public class Main {
    static int[][] cost;
    static boolean[] flag;
    static final int MAX = Integer.MAX_VALUE;

    public static int getMinCost(){
        int result = 0;
        int start, min, n = flag.length;
        flag[0] = true;
        while(--n > 0){
            start = -1;
            min = MAX;
            for (int i = 0; i < flag.length; i++) {
                if (flag[i]) {
                    for (int j = 0; j < flag.length; j++) {
                        if (!flag[j] && cost[i][j] < min) {
                            start = j;
                            min = cost[i][j];
                        }
                    }
                }
            }
            flag[start] = true;
            result += min;
        }
        return result;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner input = new Scanner(System.in);
        while(input.hasNext()){
            int lines = input.nextInt();
            if(lines == 0) break;
            cost = new int[lines][lines];
            flag = new boolean[lines];
            for(int i = 0; i < lines; i++){
                for(int j = 0; j < lines; j++){
                    cost[i][j] = MAX;
                }
            }
            for(int i = 0; i < lines - 1; i++){
                int start = input.next().charAt(0) - 'A';
                int k = input.nextInt();
                while(k-- > 0){
                    int end = input.next().charAt(0) - 'A';                    
                    int price = input.nextInt();
                    if(price < cost[start][end]){
                        cost[start][end] = price;
                        cost[end][start] = price;
                    }
                }
            }
            System.out.println(getMinCost());
        }
    }

}

A 2 B 12 I 25

#include <iostream>
#include <algorithm>
#define N 27
using namespace std;
int Tree[N];
int findRoot(int x){
    if(Tree[x]==-1) return x;
    int temp=findRoot(Tree[x]);
    Tree[x]=temp;
    return temp;
}
struct Edge{
    int x,y;
    int cost;
};
int cmp(Edge a,Edge b){
    return a.cost<b.cost;
}
int main(){
    int n;
    while(cin>>n){
        if(n==0) break;
        Edge e[300];
        int cnt,len=0;
        char x;
        int cc;char xb;
        for(int i=0;i<n;i++) Tree[i]=-1;
        for(int i=0;i<n-1;i++){
            cin>>x>>cnt;
            int aa=x-'A';
            for(int j=0;j<cnt;j++){
                cin>>xb>>cc;
                int bb=xb-'A';
                e[len].x=aa;e[len].y=bb;e[len].cost=cc;
                len++;
            }
        }
        sort(e,e+len,cmp);
        int ans=0;
        for(int i=0;i<len;i++){
            int a=findRoot(e[i].x);
            int b=findRoot(e[i].y);
            if(a!=b){Tree[a]=b;ans+=e[i].cost;}
        }
        cout<<ans<<endl;
    }
    return 0;
}

#include <stdio.h>
#include<stdlib.h>

struct Edge {
    int from;
    int to;
    int lenght;
};

const int max = 27;
struct Edge edge[max*max];
int father[max];
int height[max];

int cmp(const void* A, const void* B) {
    const struct Edge *a = (const struct Edge*) A;
    const struct Edge *b = (const struct Edge*) B;
    if (a->lenght > b->lenght)
        return 1;
    else if (a->lenght < b->lenght)
        return -1;
    else
        return 0;
}

void initial(int n) {
    for (int i = 0; i <= n; i++) {
        father[i] = i;
        height[i] = 0;
    }
}

void InitialF(struct Edge edge[], int m){
    for (int i = 0; i < m; i++){
        edge[i].lenght = 101;
    }
}

int Find(int x) {
    if (x != father[x]) {
        father[x] = Find(father[x]);
    }
    return father[x];
}

void Union(int a, int b) {
    a = Find(a);
    b = Find(b);
    if (a != b) {
        if (height[a] < height[b]) {
            father[a] = b;
        } else if (height[a] > height[b]) {
                father[b] = a;
            } else {
                father[a] = b;
                height[a]++;
            }
    }
}

int KrusKal(struct Edge edge[], int m){
    
    //InitialF(edge, m);
    qsort(edge, m, sizeof(edge[0]), cmp);
    int cost = 0;
    for (int i = 0; i < m; i++){
        if(Find(edge[i].from) != Find(edge[i].to)){
            Union(edge[i].from, edge[i].to);
            cost+=edge[i].lenght;
        }
    }
    return cost;
}

int main() {
    char a, a1;
    int b, b1;
    int n;
    //getchar();
    while (scanf("%d", &n) != EOF) { // 注意 while 处理多个 case
        // 64 位输出请用 printf("%lld") to
        
        if (n == 0) break;
        int m = n*(n-1)/2;
       
        int count = 0;
        for (int j = 0; j < n - 1; j++) {
            getchar();
           
            scanf("%c %d", &a, &b);
             if (b == 0) continue;
            //scanf("%d", &b);
            //scanf("%c %d", &a, &b);
            //printf("%d ", a);
            for (int i = 0; i < b; i++) {
                getchar();
                scanf("%c %d", &a1, &b1);
               //
                edge[count].from = a-'A';
                edge[count].to = a1-'A';
                edge[count++].lenght = b1;
                //printf("(%d %d)\n", edge[i].from, edge[i].to);
            }
        }
        // for(int i = 0 ; i < count; i++){
        //     printf("(%d %d %d)", edge[i].from, edge[i].to, edge[i].lenght);
        // }
        initial(n);
        printf("%d\n", KrusKal(edge,count));
    }
    return 0;
}

/*
描述
热带岛屿拉日山的长老有个问题。几年前，大量的外国援助资金被用于修建村庄之间的额外道路。
但丛林无情地超过了道路，因此大型公路网的维护成本太高。长老会必须选择停止维护一些道路。
左上方的地图显示了目前正在使用的所有道路以及每月维护这些道路的成本（以aacms为单位）。
当然，即使路线不像以前那么短，也需要有一些办法通过维护好的道路到达所有村庄之间。
首席长老想告诉长老委员会，他们每月能花多少钱来维护连接所有村庄的道路。
在上面的地图中，这些村庄被标记为A到I。
右边的地图显示了可以最便宜地维护的道路，每月216 aacms。
你的任务是编写一个程序来解决这些问题。
（ps：如果不是连通图的话，最后的结果输出不用包含不在连通图里的那些点）
输入描述：
输入由一到100个数据集组成，后面跟着只包含0的最后一行。
每个数据集以一行开始，该行仅包含数字n，即村庄的数量，1<n<27，
村庄用字母表的前n个字母标记，大写。
每个数据集由n-1行组成，这些行以村庄标签按字母顺序开始。
最后一个村庄没有排队。
一个村庄的每一行都以村庄标签开始，后面是从这个村庄到后面有标签的村庄的道路编号k。
如果k大于0，则该行继续使用k条道路中每条道路的数据。
每条道路的数据是道路另一端的村庄标签，然后是道路的每月维护成本（以aacms为单位）。
维护成本将是小于100的正整数。行中的所有数据字段都用单个空格分隔。
公路网将始终允许所有村庄之间的交通。
该网络的道路数量永远不会超过75条。
任何村庄通往其他村庄的道路都不会超过15条（在字母表中的前面或后面）。
在下面的示例输入中，第一个数据集与上面的映射一致。
输出描述：
每个数据集的输出是每行一个整数：
维护连接所有村庄的道路系统的最低成本，以每月aacms为单位。
注意：检查每一条可能的道路的暴力解决方案不会在一分钟内完成。
*/
#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;

struct Edge {
    char from;  //边的起点
    char to;    //边的终点
    int length; //边的长度
    Edge(char f, char t, int l): from(f), to(t), length(l) {}
    bool operator<(const Edge& e)const {
        return length < e.length;
    }
};

vector<Edge>edge;       //边集
map<char, char>father;  //父亲结点
map<char, int>height;   //结点高度

void Initial(int n) {                           //初始化
    for (int i = 0; i < n; i++) {
        father[i + 'A'] = i + 'A';
        height[i + 'A'] = 0;
    }
}

char Find(char ch) {                            //查找根结点
    if (ch != father[ch]) {                     //路径压缩
        father[ch] = Find(father[ch]);
    }
    return father[ch];
}

void Union(char x, char y) {                    //合并集合
    x = Find(x);
    y = Find(y);
    if (x != y) {
        if (height[x] < height[y]) {
            father[x] = y;
        } else if (height[y] < height[x]) {
            father[y] = x;
        } else {
            father[y] = x;
            height[x]++;
        }
    }
}

int Kruskal(int n) {    //克鲁斯卡尔算法求n个结点的最小生成树
    Initial(n);
    sort(edge.begin(), edge.end());
    int sum = 0;
    for (const auto& e : edge) {
        if (Find(e.from) != Find(e.to)) {
            Union(e.from, e.to);
            sum += e.length;
        }
    }
    return sum; //返回最小总长度
}

int main() {
    int n;
    while (cin >> n) {
        for (int i = 1; i < n; i++) {   //数据集有n-1个
            string str;
            cin >> str;
            char from = str[0];
            int k;
            cin >> k;
            while (k--) {
                cin >> str;
                char to = str[0];
                int length;
                cin >> length;
                edge.emplace_back(from, to, length);
            }
        }
        cout << Kruskal(n) << endl;
    }
    return 0;
}

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

const int MAXN = 27;
int vexset[MAXN];
int ans = 0;

typedef struct Graph {
	char vexs[MAXN];
	int edge[MAXN][MAXN];
	int vexnum, arcnum;
}Graph;
int locateVex(Graph g, char vex) {
	for (int i = 0; i < g.vexnum; ++i)
		if(vex == g.vexs[i])
			return i;

	return -1;
}
//help function
typedef struct Arcs {
	char from, to;
	int weight;
}Arcs;
Arcs arcs[MAXN];


bool cmp(Arcs a1, Arcs a2) {
	return a1.weight < a2.weight;
}

void kruskal(Graph g) {
	int i, j, vs1, vs2, v1, v2;
	//排序
/*	cout<<"开始排序"<<endl;
*/	sort(arcs, arcs+g.arcnum, cmp);
	//处理连通分量
	for(i = 0; i < g.vexnum; ++i)
		vexset[i] = i;
	//得出最小生成树（合并连通分量）
/*	cout<<"开始得出最小生成树"<<endl;
*/	for(i=0; i<g.arcnum;++i) {
		v1 = locateVex(g, arcs[i].from);
		v2 = locateVex(g, arcs[i].to);

		vs1 = vexset[v1];
		vs2 = vexset[v2];
		if(vs1 != vs2) {
			ans += arcs[i].weight;
			for(j = 0;j < g.vexnum; ++j) {
				if(vexset[j] == vs2)
					vexset[j] = vs1;
			}
		}
	}
}

int main(int argc, char* argv[])
{
	int n, arcn, i, j, k;
	Graph g;
/*	cout<<"开始输入"<<endl;
*/	while(cin>>n && n != 0) {
		ans = 0;
		k = 0;
		g.vexnum = n;
		g.arcnum = 0;
		for (i=0; i<n-1;++i) {
			cin>>g.vexs[i]>>arcn;
			for (j=0;j < arcn; ++j) {
				arcs[k].from=g.vexs[i];
				cin>>arcs[k].to;
				cin>>arcs[k].weight;
				g.arcnum++;
				++k;
			}
		}
		g.vexs[i] = g.vexs[i-1]+1;
/*		cout<<"输入完毕"<<endl;
*/
/*		cout<<"克鲁斯卡尔算法开始执行"<<endl;
*/		kruskal(g);
/*		cout<<"克鲁斯卡尔算法执行完毕"<<endl;
*/
		cout<<ans<<endl;

	}
	return 0;
}