记录编号	37812	评测结果	AAAAAAAAA
题目名称	[USACO 2.4.4]回家	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.013 s
提交时间	2012-04-08 15:51:31	内存使用	0.27 MiB

/*
ID: anytjf1
PROG: comehome
LANG: C++
*/
#include <cstdio>
#include <cctype>
int ord(char c) {
    if(isupper(c))
        return c - 'A';
    else
        return c - 'a' + 26;
}
const int INF = 60000;
int f[52][52];
int main() {
    freopen("comehome.in","r",stdin);
    freopen("comehome.out","w",stdout);
    int n, m, d;
    char a, b;
    for(int i=0; i<52; i++)
        for(int j=0; j<52; j++)
            f[i][j] = INF;
    for(int i=0; i<26; i++)
        f[i][i] = 0;
    scanf("%d\n", &n);
    for(int i=0; i<n; i++) {
        scanf("%c %c %d\n", &a, &b, &d);
        a = ord(a);
        b = ord(b);
        if(f[a][b] > d)
            f[a][b] = f[b][a] = d;
    }
    for(int k=0; k<52; k++)
        for(int i=0; i<52; i++)
            for(int j=0; j<52; j++)
                if(f[i][k] + f[k][j] < f[i][j])
                    f[i][j] = f[i][k] + f[k][j];
    m = INF;
    a = '#';
    for(char i='A'; i<='Y'; i++) {
        d = f[ord(i)][ord('Z')];
        if(d < m)
            m = d, a = i;
    }
    printf("%c %d\n", a, m);
    return 0;
}