銀河貿易問題

http://acm.sdibt.edu.cn/JudgeOnline/problem.php?id=1247
銀河貿易問題
Time Limit：1 Sec  
メモリLimit:64 MB
Submit:15  
Solved:2
［
Submit][
Status][
ディスク]
Description
「￥」と呼ばれる超時空宇宙船の発明に伴い、地球とはるかな銀河の間の商品の輸出入活動が始まった。プラル星の中のいくつかの銀河から商品を輸入したいです。これらの銀河の中の惑星は高価な商品と原材料を豊富に生産しています。初歩的な報告によると、（1）各銀河には少なくとも一つと最大26個の惑星が含まれており、一つの銀河の各惑星にはA～Zのアルファベットで唯一の標識が与えられている。（2）各惑星は一つの商品を専門に生産し、輸出しています。同じ銀河の異なる惑星では違った商品を輸出しています。（3）一部の惑星の間には超時空貨物輸送ルートが接続されている。惑星AとBがつながっていれば、それらは自由貿易できます。惑星CとBがつながっていて、AとCの間はまだBを通じて貿易ができますが、Bは5%の貨物を通行料として拘束します。一般的には、二つの惑星の間が一つの貨物ルートを通じて連結されれば、彼らは貿易ができますが、どの中継所も5%の貨物を通行料として押収します。（4）銀河ごとに少なくとも一つの惑星が地球に行く￥航路を開放しています。ビジネスにとって￥航路は他の星間航路と同じです。各惑星の主な輸出商品について価格を設定しています。数値が高いほど商品の価値が高くなります。地元市場では、高価な商品ほど利益が上がる。問題は通行料を考えるなら、どの惑星の商品価値が一番高いかを確認することです。
Input
いくつかの銀河を含む説明を入力します。各銀河の記述の最初の行は整数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

分析：最も短絡的な変形は、乗算の最大値を求めます。
プログラム:

#include"string.h" 
#include"stdio.h" 
#include"queue" 
#include"map" 
#include"vector" 
#include"math.h" 
#define M 100 
#define inf 100000000 
#define eps 1e-10 
using namespace std; 
struct node 
{ 
    int v; 
    node(int vv) 
    { 
        v=vv; 
    } 
}; 
vector<node>edge[M]; 
struct Node 
{ 
    char name[3]; 
    double k; 
    char str[222]; 
    double ans; 
}p[M]; 
double dis[M]; 
int use[M]; 
void spfa(int s) 
{ 
    memset(dis,0,sizeof(dis)); 
    queue<int>q; 
    memset(use,0,sizeof(use)); 
    dis[s]=1; 
    use[s]=1; 
    q.push(s); 
    while(!q.empty()) 
    { 
        int u=q.front(); 
        q.pop(); 
        use[u]=0; 
        for(int i=0;i<(int)edge[u].size();i++) 
        { 
            int v=edge[u][i].v; 
            if(dis[v]<dis[u]*0.95) 
            { 
                dis[v]=dis[u]*0.95; 
                if(!use[v]) 
                { 
                    q.push(v); 
                    use[v]=1; 
                } 
            } 
        } 
    } 
} 
int main() 
{ 
    int n,i,j,r; 
    while(scanf("%d",&n)!=-1) 
    { 
        for(i=0;i<=n;i++) 
            edge[i].clear(); 
        map<int,int>mp; 
        for(i=1;i<=n;i++) 
        { 
            scanf("%s%lf%s",p[i].name,&p[i].k,p[i].str); 
            mp[p[i].name[0]-'A']=i; 
        } 
        for(i=1;i<=n;i++) 
        { 
            for(r=0;p[i].str[r]!='\0';r++) 
            { 
                if(p[i].str[r]=='*') 
                { 
                    edge[i].push_back(node(0)); 
                    edge[0].push_back(node(i)); 
                    continue; 
                } 
                j=mp[p[i].str[r]-'A']; 
                edge[i].push_back(node(j)); 
                edge[j].push_back(node(i)); 
            } 
        } 
        spfa(0); 
        //for(i=1;i<=n;i++) 
            //printf("%s %.3lf
",p[i].name,dis[i]); 
        double max=0; 
        int tep; 
        for(i=1;i<=n;i++) 
        { 
            p[i].ans=dis[i]/0.95*p[i].k; 
            if(max<p[i].ans) 
            { 
                max=p[i].ans; 
                tep=i; 
            } 
            else if(fabs(max-p[i].ans)<eps) 
            { 
                if(p[tep].name[0]>p[i].name[0]) 
                { 
                    tep=i; 
                } 
            } 
        } 
        printf("%c
",p[tep].name[0]); 
    } 
    return 0; 
}