最短路徑問(wèn)題，數(shù)據(jù)量很小(最多52個(gè)結(jié)點(diǎn))，所以用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;
}