1106 Lowest Price in Supply Chain (25 分)

1079 Total Sales of Supply Chain (25 分)几乎一模一样的题，没啥新意。

题意

给出一棵销售供应的树，树根唯一。在树根处货物的价格为P,然后从根结点开始每往子结点走一层， 该层的货物价格将会在父亲结点的价格上增加r%。求叶子结点处能获得的最低价格以及能提供最低价格的叶子结点的个数。

本题实际上就是求树的深度最小的叶子结点。

const int N=1e5+10;
vector<int> g[N];
int n;
double price,rate;
double ans;
int cnt;

void dfs(int root,double cost)
{
    if(g[root].size() == 0)
    {
        if(ans == 0 || cost < ans)
        {
            ans=cost;
            cnt=1;
        }
        else if(cost == ans)
            cnt++;
        return;
    }

    for(int i=0;i<g[root].size();i++)
    {
        int j=g[root][i];
        dfs(j,cost*(1+rate));
    }
}

int main()
{
    cin>>n>>price>>rate;
    rate/=100;

    for(int i=0;i<n;i++)
    {
        int k;
        cin>>k;
        for(int j=0;j<k;j++)
        {
            int x;
            cin>>x;
            g[i].pb(x);
        }
    }

    dfs(0,price);

    printf("%.4f %d\n",ans,cnt);

    //system("pause");
    return 0;
}

1106 Lowest Price in Supply Chain (25 分)

原文：https://www.cnblogs.com/fxh0707/p/14454484.html