最短路径问题，数据量很小(最多52个结点)，所以用floyd算法就可以了。
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("comehome.in");
ofstream fout("comehome.out");
#ifdef _DEBUG
#define out cout
#define in cin
#else
#define out fout
#define in fin
#endif
int graph[52][52];
int char2int(char c)
{
if(c>='a'&&c<='z')
return c-'a';
else if(c>='A'&&c<='Z')
return c-'A'+26;
}
void floyd()
{
for(int k=0;k<52;++k)
for(int i=0;i<52;++i)
for(int j=0;j<52;++j){
graph[i][j] = min(graph[i][j],graph[i][k]+graph[k][j]);
}
}
void solve()
{
int p;
char a,b;
int len;
for(int i=0;i<52;++i)
for(int j=0;j<52;++j)
graph[i][j] = INT_MAX/2;
in>>p;
while(p--){
in>>a>>b>>len;
int i = char2int(a);
int j = char2int(b);
graph[i][j] = graph[j][i] = min(graph[i][j],len);
}
floyd();
int res = INT_MAX;
int z = char2int('Z');
char resi;
for(int i=26;i<51;++i){
if(graph[z][i]<res){
resi = 'A'+i-26;
res = graph[z][i];
}
}
out<<resi<<" "<<res<<endl;
}
int main(int argc,char *argv[])
{
solve();
return 0;
}