Time Limit: Java: 2000 ms / Others: 2000 ms
Memory Limit: Java: 65536 KB / Others: 65536 KB
Each galaxy contains at least one and at most 26 planets. Each planet within
a galaxy is identified by a unique letter from A to Z.
Each planet specializes in the production and export of one good. Different planets within the same galaxy export different goods.
Some pairs of planets are connected by hyperspace shipping lines. If planets A and B are connected, they can trade goods freely. If planet C is connected to B but not to A, then A and C can still trade goods with each other through B, but B keeps 5% of the shipment as a shipping fee. (Thus A only receives 95% of what C shipped, and C receives only 95% of what A shipped.) In general, any two planets can trade goods as long as they are connected by some set of shipping lines, but each intermediate planet along the shipping route keeps 5% of what it shipped (which is not necessarily equal to 5% of the original shipment).
At least one planet in each galaxy is willing to open a ThrustoZoom shipping line to Earth. A ThrustoZoom line is the same as any other shipping line within the galaxy, as far as business is concerned. For example, if planet K opens a ThrustoZoom line to Earth, then the Earth can trade goods freely with K, or it can trade goods with any planet connected to K, subject to the usual shipping fees.
HyperCommodities has assigned a relative value (a positive real number less than 10) to each planet's chief export. The higher the number, the more valuable the product. More valuable products can be resold with a higher profit margin in domestic markets. The problem is to determine which planet has the most valuable export when shipping fees are taken into account.
1. The letter used to represent the planet.
2. A space.
3. The relative value of the planet's export, in the form d.dd.
4. A space.
5. A string containing letters and/or the character `*'; a letter indicates a shipping line to that planet, and a `*' indicates a willingness to open a ThrustoZoom shipping line to Earth.
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