第三代半导体 jsp 莱斯分布 Python爬虫实战 sockets recursion audio struct vcpkg ios4 bower vue路由 pmp视频 网校直播系统 多线程实现方式 mysql分页查询sql语句 centos查看python版本 小程序下拉刷新样式 java不定长数组 普通话网上报名 python图形界面开发 windows安装python环境 java数据 java对象和类 java基础课程 java数组最大值 java特性 java连接sql java语言入门 电子书之家 groupby 打马赛克的软件 通讯录管理系统 为什么英雄联盟无法连接服务器 文字转语音软件免费版 如何用ai设计字体 游戏linux正则表达式 文字转语音工具 ps高手教程 方正徐静蕾字体
当前位置: 首页 > 学习教程  > 编程语言

1106 Lowest Price in Supply Chain (25分)(树的遍历)

2020/11/4 14:52:25 文章标签:

这种题目是重点题型,跟前面刷到的DFS和BFS有很多相同的地方,树的先根遍历对应DFS,树的层序遍历对应BFS,这种题目也有很强的规律可循,刷的多了,就会越来越得心应手了。 题目描述如下: 题目大致…

这种题目是重点题型,跟前面刷到的DFS和BFS有很多相同的地方,树的先根遍历对应DFS,树的层序遍历对应BFS,这种题目也有很强的规律可循,刷的多了,就会越来越得心应手了。

题目描述如下:
在这里插入图片描述
在这里插入图片描述
题目大致意思:
这道题目和1079很像,1079那道题目是求总销售额,这道题目是求最低单价。
大致思路:
这道题目同样可以用BFS来做,具体的实现步骤如下面代码所示:
提交结果:
在这里插入图片描述
提交的代码如下:

#include<iostream>
#include<vector>
#include<queue>
#include<iomanip>
using namespace std;
struct Node
{
    vector<int> child;
    double danjia;
};
Node node[100000];
int n;
double p,r;
void BFS();
int main()
{
    cin>>n>>p>>r;
    for(int i=0;i<n;i++)
    {
        int k;
        cin>>k;
        if(k!=0)
        {
            for(int j=0;j<k;j++)
            {
                int temp;
                cin>>temp;
                node[i].child.push_back(temp);
            }
        }
    }
    BFS();
}
void BFS()
{
    queue<int> que;
    que.push(0);
    node[0].danjia=p;
    double min=10000000000;
    int number=0;
    while(!que.empty())
    {
        int top=que.front();
        que.pop();
        if(node[top].child.size()==0&&node[top].danjia<=min)
        {
            min=node[top].danjia;
            number++;
        }
        for(int i=0;i<node[top].child.size();i++)
        {
            que.push(node[top].child[i]);
            node[node[top].child[i]].danjia=node[top].danjia+node[top].danjia*r*0.01;
        }
    }
    cout<<setiosflags(ios::fixed)<<setprecision(4)<<min<<" "<<number<<endl;
}

本次提交后累计得分为1519。


本文链接: http://www.dtmao.cc/news_show_350250.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?