Welcome To SDIBT ACM-ICPC Online Judge

VIRTUAL JUDGE Recent Contest F.A.Qs Forum Home ProblemSet Status Ranklist Contest LoginRegister Exam
Problem 1247. -- 银河贸易问题

银河贸易问题

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 37  Solved: 13
[Submit][Status][Forum]

Description

随着一种称为“¥”的超时空宇宙飞船的发明,一种叫做“¥¥”的地球与遥远的银河之间的商品进出口活动应运而生。¥¥希望从PluralZ星团中的一些银河进口商品,这些银河中的行星盛产昂贵的商品和原材料。初步的报告显示:   (1)每个银河都包含至少一个和最多26个行星,在一个银河的每个行星用A~Z中的一个字母给以唯一的标识。   (2)每个行星都专门生产和出口一种商品,在同一银河的不同行星出口不同的商品。   (3)一些行星之间有超时空货运航线连接。如果行星A和B相连,则它们可以自由贸易;如果行星C与B相连而不与A相连,则A和C之间仍可通过B进行贸易,不过B要扣留5%的货物作为通行费。一般来说,只要两个行星之间可以通过一组货运航线连接,他们就可以进行贸易,不过每个中转站都要扣留5%的货物作为通行费。   (4)在每个银河至少有一个行星开放一条通往地球的¥航线。对商业来说,¥航线和其他星际航线一样。   ¥¥已经对每个行星的主要出口商品定价(不超过10的正实数),数值越高,商品的价值越高。在本地市场,越值钱的商品获利也越高。问题是要确定如果要考虑通行费是,哪个行星的商品价值最高。

Input

输入包含若干银河的描述。每个银河的描述开始的第1行是一个整数n,表示银河的行星数。接下来的n行每行包括一个行星的描述,即:   (1)一行用以代表行星的字母;   (2)一个空格;   (3)以d.dd的形式给出该行星的出口商品的价值;   (4)一个空格;   (5)一个包含字母和(或)字符“*”的字符串;字母表示一条通往该行星的货运航线;“*”表示该行星向地球开放¥货运航线。

Output

对每个银河的描述,输出一个字母P表示在考虑通行费的前提下,行星P具有最高价值的出口商品。如果用有最高价值的出口商品的行星多于一个,只需输出字母序最小的那个行星。

Sample Input

5
E 0.01 *A
D 0.01 A*
C 0.01 *A
A 1.00 EDCB
B 0.01 A*

Sample Output

A

HINT

Source

[Submit][Status][Forum]

HOME Back

한국어 中文 English
All Copyright Reserved 2008-2010 SDIBT TEAM
GPL2.0 2003-2010 HUSTOJ Project TEAM
Anything about the Problems, Please Contact Admin:admin