Guest
Login
跳过导航链接

入口的选择
Time Limit:1000MS  Memory Limit:32768K

Description:

Zeism玩的赛车游戏中,有一种树形的赛道。树根表示赛道的终点,任何一个叶子结点表示一个赛道的入口,其余的结点都是中转站。如下图所示: 在这种赛道中,Zeism可以选择A,B,C三个入口中的任意一个。为了赢得比赛,Zeism需要选择一条总路程最短的路线。Zeism发现,每个入口都存在一条到终点的最短路,因此,他需要做出的选择就是:选择哪个入口?

Input:

输入数据是一条赛道。第一行N表示其后有N行数据。赛道的终点用字母T表示。赛道的入口和中转站用一个大写字母表示,且不会重名。输入数据的每一行由2个大写字母和一个正整数组成:U V D。表示站点U到站点V的路程为D公里。输入数据处理到文件结尾,并且保重数据的合法性。

Output:

输出数据包括入口和最短路程。如果存在多个最短路程相等的入口,请输出字母顺序最前的入口。

Sample Input:

2
T A 3
T B 2

Sample Output:

B 2
Status  Submit


Zhe Jiang University Of Technology Online Programming Space Beta1.3
Designed & Developped By Jin Qiwei
 All Copyright Reserved 2006
46