은하계 수입

시간 제한1초메모리 제한128 MB

요약

각 은하에서 지구까지의 연결과 행성 사이의 중간 정거장마다 5%의 수수료를 뺀 수출 가치가 가장 높은 행성을 찾고, 동점이면 알파벳 순으로 앞선 행성을 출력한다.

난이도: 보통10점 중 6점
유형: 그래프, 최단 경로, 구현, 수학
정답자: 아직 제출이 없습니다

문제

새로 개발된 ThrustoZoom 초차원 드라이브 덕분에, 뉴저지의 수출입 대기업 HyperCommodities는 우주에서 가장 먼 은하계와도 교역할 수 있게 되었습니다. HyperCommodities는 Plural Z 구역에 있는 몇몇 은하계에서 상품을 수입하려고 합니다. 이 은하계의 행성들은 진공 밀봉재, 투명 알루미늄, 다이그래파이트, 퀀텀 강철 같은 귀중한 제품과 원자재를 수출합니다. 예비 조사로 다음 사실이 밝혀졌습니다.

각 은하계에는 행성이 최소 1개, 최대 26개 있습니다. 은하계 안의 각 행성은 A부터 Z까지의 서로 다른 알파벳 한 글자로 식별됩니다.
각 행성은 한 가지 상품의 생산과 수출에 특화되어 있습니다. 같은 은하계 안의 서로 다른 행성은 서로 다른 상품을 수출합니다.
일부 행성 쌍은 초공간 운송 노선으로 연결되어 있습니다. 행성 A와 B가 연결되어 있으면 두 행성은 자유롭게 교역할 수 있습니다. 행성 C가 B와는 연결되어 있지만 A와는 연결되어 있지 않다면, A와 C는 여전히 B를 거쳐 교역할 수 있으나 이때 B가 운송료로 배송량의 5%를 가져갑니다. (따라서 A는 C가 보낸 양의 95%만 받고, C도 A가 보낸 양의 95%만 받습니다.) 일반적으로 두 행성은 운송 노선들로 연결되어 있기만 하면 교역할 수 있으며, 운송 경로 위의 각 중간 행성은 자신이 운송하는 양의 5%를 가져갑니다(이는 원래 배송량의 5%와 반드시 같지는 않습니다).
각 은하계의 적어도 한 행성은 지구로 향하는 ThrustoZoom 노선을 개설할 의향이 있습니다. ThrustoZoom 노선은 사업적으로 볼 때 은하계 안의 다른 운송 노선과 동일합니다. 예를 들어 행성 K가 지구로 ThrustoZoom 노선을 개설하면, 지구는 K와 자유롭게 교역할 수 있고, K와 연결된 임의의 행성과도 통상적인 운송료를 물며 교역할 수 있습니다.

HyperCommodities는 각 행성의 주력 수출품에 상대 가치(10보다 작은 양의 실수)를 부여했습니다. 값이 클수록 제품이 더 가치 있으며, 더 가치 있는 제품은 국내 시장에서 더 높은 마진으로 되팔 수 있습니다. 문제는 운송료를 고려했을 때 어느 행성의 수출품이 가장 가치 있는지 알아내는 것입니다.

입력

입력은 하나 이상의 은하계 설명으로 이루어집니다. 각 은하계 설명은 그 은하계의 행성 수를 나타내는 정수 $N$ 이 적힌 줄로 시작합니다. 이어지는 $N$ 개의 줄에는 각 행성의 설명이 들어 있으며, 각 줄은 다음으로 구성됩니다.

행성을 나타내는 알파벳.
공백.
d.dd 형식으로 표기된 그 행성 수출품의 상대 가치.
공백.
알파벳과 * 문자로 이루어진 문자열. 알파벳은 해당 행성으로의 운송 노선을 뜻하고, *는 지구로 ThrustoZoom 노선을 개설할 의향이 있음을 뜻합니다.

입력은 파일 끝(EOF)에서 종료됩니다.

출력

각 은하계 설명에 대해, 운송료를 고려했을 때 수출품이 가장 가치 있는 행성 $P$ 의 알파벳을 사용하여 Import from P라고 적힌 한 줄을 출력합니다. 가장 가치 있는 수출품 값을 가진 행성이 둘 이상이면 알파벳 순으로 가장 앞선 행성을 출력합니다.

예제8

예제 1

입력

1
F 0.81 *
5
E 0.01 *A
D 0.01 A*
C 0.01 *A
A 1.00 EDCB
B 0.01 A*
10
S 2.23 Q*
A 9.76 C
K 5.88 MI
E 7.54 GC
M 5.01 OK
G 7.43 IE
I 6.09 KG
C 8.42 EA
O 4.55 QM
Q 3.21 SO

예상 출력

Import from F
Import from A
Import from A

예제 2
입력
```
1
Z 5.00 *
```
예상 출력
```
Import from Z
```
예제 3
입력
```
2
B 3.00 *
A 3.00 *
```
예상 출력
```
Import from A
```
예제 4
입력
```
2
A 1.00 B*
B 1.02 A
```
예상 출력
```
Import from A
```
예제 5
입력
```
2
A 1.00 B*
B 1.10 A
```
예상 출력
```
Import from B
```

예제 6

입력

4
A 9.00 B*
B 1.00 AC
C 1.00 BD
D 1.00 C

예상 출력

Import from A

예제 7

입력

3
A 1.00 B*
B 1.00 AC
C 9.99 B

예상 출력

Import from C

예제 8

입력

4
D 4.00 *
C 4.20 *
B 3.90 *
A 4.10 *

예상 출력

Import from C