Galactic Import

With the introduction of the new ThrustoZoom gigadimensional drive, it has become possible for HyperCommodities, the import/export conglomerate from New Jersey, to begin trading with even the most remote galaxies in the universe. HyperCommodities wants to import goods from some of the galaxies in the Plural Z sector. Planets within these galaxies export valuable products and raw materials like vacuuseal, transparent aluminum, digraphite, and quantum steel. Preliminary reports have revealed the following facts:

• 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.

Input

The input consists of one or more galaxy descriptions. Each galaxy description begins with a line containing an integer N which specifies the number of planets in the galaxy. The next N lines contain descriptions of each planet, which consist of:

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.

Output

For each galaxy description, output a single line which reads ``Import from P'' where P is the letter of the planet with the most valuable export, once shipping fees have been taken into account. (If more than one planet have the same most valuable export value then output the plant which is alphabetically first).

Sample Input

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

Sample Output

Import from F
Import from A
Import from A

---

題目描述：

原題描述對於中國人來說太吃力了。

簡單說明一下，以 '*' 表示地球 'A'-'Z' 表示其他星球，而每個星球的產物要運送到地球，每轉運一次產物的價值相當於 *0.95, 也就是價值會下降，問哪個星球的產物具有最高價值。

題目解法：

相當於邊都是 1 的，計算每個星球到地球的最短距離，根據最短距離，
計算每個星球產物的價值，找一個最高的即可。

距離相當於折損(抽稅)的次數。

//這題看了好幾個小時，能叫的朋友都叫上了，也才一個人願意幫我看題目，哈哈


#include <stdio.h>
#include <queue>
#include <algorithm>
#include <math.h>
using namespace std;
vector<int> g[50];
#define eps 1e-8
int main() {
    int n, i, j, k;
    char x[50], y[50];
    double d[50], dd;
    while(scanf("%d", &n) == 1) {
        for(i = 0; i < 50; i++)
            g[i].clear();
        for(i = 0; i < n; i++) {
            scanf("%s %lf %s", x, &dd, y);
            d[x[0]-'A'+1] = dd;
            for(k = 0; y[k]; k++) {
                int tx = y[k] == '*' ? 0 : y[k]-'A'+1;
                g[tx].push_back(x[0]-'A'+1);
            }
        }
        queue<int> Q;
        int dist[105] = {};
        double ret = 0;
        int rch;
        dist[0] = 1;
        Q.push(0);
        while(!Q.empty()) {
            int tn = Q.front();
            Q.pop();
            for(i = 0; i < g[tn].size(); i++) {
                if(dist[g[tn][i]] == 0) {
                    dist[g[tn][i]] = dist[tn]+1;
                    Q.push(g[tn][i]);
                }
            }
            if(tn > 0) {
                double val = d[tn]*pow(0.95, dist[tn]-2);
                if(val > ret || (fabs(val-ret) < eps && tn < rch)) {
                    ret = val;
                    rch = tn-1;
                }
            }
        }
        printf("Import from %c\n", rch+'A');
    }
    return 0;
}