每日一题----昂贵的婚礼

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
//本题酋长的允诺也算一个物品,最后一定要交给酋长,那么等级不能超过酋长的等级范围

const int N = 150 * 150,M = N;
typedef pair<int,int> pll;
int dist[N];//距离数组,这里代表到当前点的花费
int n,m;
int level[N];
//每次交易只能在等级限制范围内可以交易
bool st[N];
int e[M],h[N],idx,ne[M],w[M];
int price[N];//每个物品的价值,下标就是编号
void add(int a,int b,int c)
{
    e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}
int dijkstra(int l,int r)
{
    memset(dist,0x3f,sizeof dist);
    memset(st,0,sizeof st);
    dist[0] = 0;
    priority_queue<pll,vector<pll>,greater<pll>> heap;
    heap.push({0,0});//第一个是点,第二个是当前点的距离
    //dijkstra堆优化算法,优化在取路径最短那里
    while(heap.size())
    {
        auto t = heap.top().second;
        heap.pop();
        if(st[t]) continue;
        st[t] = true;
        for(int i = h[t];i != -1;i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[i] && level[j] >= l && level[j] <= r)
            {
               dist[j] = dist[t] +  w[i];
               heap.push({dist[j],j});
            }
        }
    }

    return dist[1];
}
int main()
{
    cin>>m>>n;
    //0是虚拟源点,比如到3要10000,不用其他物品换,直接买得到的价格
    //比如拿2去换1的物品,就用箭头指向1
    memset(h,-1,sizeof h);
    for(int i = 1;i <= n;i++)
    {
        int cnt;
        cin>>price[i]>>level[i]>>cnt;
        add(0,i,price[i]);
        for(int j = 0;j < cnt;j++)
        {
            int id,cost;
            cin>>id>>cost;
            add(id,i,cost);//id指向i代表id换i所需的花费
        }
    }
    int res = 0x3f3f3f3f;
    //枚举酋长允诺的等级区间之内
    for(int i = level[1] - m;i <= level[1];i++)
    {
         res = min(res,dijkstra(i,i + m));
    }
    cout<<res<<endl;
    return 0;
}

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/150001.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

高效使用 PyMongo 进行 MongoDB 查询和插入操作

插入到集合中&#xff1a; 要将记录&#xff08;在MongoDB中称为文档&#xff09;插入到集合中&#xff0c;使用insert_one()方法。insert_one()方法的第一个参数是一个包含文档中每个字段的名称和值的字典。 import pymongomyclient pymongo.MongoClient("mongodb://l…

使用pixy计算群体遗传学统计量

1 数据过滤 过滤参数&#xff1a;过滤掉次等位基因频率&#xff08;minor allele frequency&#xff0c;MAF&#xff09;低于0.05、哈达-温伯格平衡&#xff08;Hardy– Weinberg equilibrium&#xff0c;HWE&#xff09;对应的P值低于1e-10或杂合率&#xff08;heterozygosit…

两万字图文详解!InnoDB锁专题!

前言 本文将跟大家聊聊 InnoDB 的锁。本文比较长&#xff0c;包括一条 SQL 是如何加锁的&#xff0c;一些加锁规则、如何分析和解决死锁问题等内容&#xff0c;建议耐心读完&#xff0c;肯定对大家有帮助的。 为什么需要加锁呢&#xff1f; InnoDB 的七种锁介绍 一条 SQL 是…

2023.11.16-hive sql高阶函数lateral view,与行转列,列转行

目录 0.lateral view简介 1.行转列 需求1: 需求2: 2.列转行 解题思路: 0.lateral view简介 hive函数 lateral view 主要功能是将原本汇总在一条&#xff08;行&#xff09;的数据拆分成多条&#xff08;行&#xff09;成虚拟表&#xff0c;再与原表进行笛卡尔积&#xff0c…

那些让我苦笑不得的 Bug:编码之路的坎坷经历

文章目录 1. CSS 中的样式“消失”问题2. JavaScript 的变量命名引发的混乱3. 时间格式的困扰4. 数据库查询条件引发的错误结语 &#x1f389;欢迎来到Java学习路线专栏~那些让我苦笑不得的 Bug&#xff1a;编码之路的坎坷经历 ☆* o(≧▽≦)o *☆嗨~我是IT陈寒&#x1f379;✨…

了解一下知识付费系统的开发流程和关键技术点

知识付费系统的开发既涉及到前端用户体验&#xff0c;又需要强大的后端支持和复杂的付费逻辑。在这篇文章中&#xff0c;我们将深入探讨知识付费系统的开发流程和关键技术点&#xff0c;并提供一些相关的技术代码示例。 1. 需求分析和规划&#xff1a; 在着手开发知识付费系…

小学生加减乘除闯关运算练习流量主微信小程序开发

小学生加减乘除闯关运算练习流量主微信小程序开发 经过本次更新&#xff0c;我们增加了新的功能和特性&#xff0c;以提升用户体验和运算练习的趣味性&#xff1a; 能量石与激励视频&#xff1a;用户可以通过观看激励视频来获取能量石&#xff0c;这些能量石可以用于解锁收费…

ctfshow 文件上传 151-161

文件上传也好久没做了。。 手很生了 151 前端绕过 只能上传png文件 使用bp抓包&#xff0c;修改文件名后缀为php 上传成功&#xff0c;发现文件上传路径 使用蚁剑连接 找到flag 152 152 后端校验 跟上一关一样 表示后面即使执行错误&#xff0c;也不报错 抓包修改文件…

招投标系统软件源码,招投标全流程在线化管理

功能描述 1、门户管理&#xff1a;所有用户可在门户页面查看所有的公告信息及相关的通知信息。主要板块包含&#xff1a;招标公告、非招标公告、系统通知、政策法规。 2、立项管理&#xff1a;企业用户可对需要采购的项目进行立项申请&#xff0c;并提交审批&#xff0c;查看所…

TypeError: Cannot read properties of undefined (reading ‘0‘)

1、在使用<el-dropdown>会报这个错误 原因&#xff1a;使用v-if控制显隐&#xff0c;找不到该节点就会开始报错 解决&#xff1a;使用v-show就可以了

自定义控件封装

上边对两个控件整合时用函数指针是因为QSpinBox::valueChange有重载版本 自定义的接口放在类外 你设计的界面可以通过提升为调用这些接口 添加qt设计师界面类

winform窗体、控件的简单封装,重做标题栏

1标题栏封装中使用了以下技术&#xff1a; 知识点&#xff1a; 1.父类、子类的继承&#xff1b; 2.窗体之间的继承&#xff1b; 3.自定义控件的绘制&#xff1b; 4.多线程在窗体间的应用&#xff1b; 5.窗体和控件的封装&#xff1b; 6.回调函数&#xff08;委托&#xff09;&…

Redis快速入门(基础篇)

简介&#xff1a; 是一个高性能的 key-value数据库。 存在内存中 与其他 key-value 缓存产品有以下三个特点&#xff1a; Redis支持数据的持久化&#xff0c;可以将内存中的数据保持在磁盘中&#xff0c;重启的时候可以再次加载进行使用。 Redis不仅仅支持简单的key-value类…

自动备份pgsql数据库

bat文件中的内容&#xff1a; PATH D:\Program Files\PostgreSQL\13\bin;D:\Program Files\7-Zip set PGPASSWORD**** pg_dump -h 8.134.151.187 -p 5466 -U sky -d mip_db --schema-only -f D:\DB\backup\%TODAY%-schema-mip_db_ali.sql pg_dump -h 8.134.151.187 -p 5466…

BUUCTF 面具下的flag 1

BUUCTF:https://buuoj.cn/challenges 题目描述&#xff1a; 下载附件&#xff0c;得到一张.jpg图片。 密文&#xff1a; 解题思路&#xff1a; 1、将图片放到Kali中&#xff0c;使用binwalk检测出隐藏zip包。 使用foremost提取zip压缩包到output目录下 解压zip压缩包&…

python自动化第一篇—— 带图文的execl的自动化合并

简述 最近接到一个需求&#xff0c;需要为公司里的一个部门提供一个文件上传自动化合并的系统&#xff0c;以供用户稽核&#xff0c;谈到自动化&#xff0c;肯定是选择python&#xff0c;毕竟python的轮子多。比较了市面上几个用得多的python库&#xff0c;我最终选择了xlwings…

【自然语言处理(NLP)实战】LSTM网络实现中文文本情感分析(手把手与教学超详细)

目录 引言&#xff1a; 1.所有文件展示&#xff1a; 1.中文停用词数据&#xff08;hit_stopwords.txt)来源于&#xff1a; 2.其中data数据集为chinese_text_cnn-master.zip提取出的文件。点击链接进入github&#xff0c;点击Code、Download ZIP即可下载。 2.安装依赖库&am…

聊聊模糊测试,以及几种模糊测试工具的介绍!

以下为作者观点&#xff1a; 在当今的数字环境中&#xff0c;漏洞成为攻击者利用系统漏洞的通道&#xff0c;对网络安全构成重大威胁。这些漏洞可能存在于硬件、软件、协议实施或系统安全策略中&#xff0c;允许未经授权的访问并破坏系统的完整性。 根据 "常见漏洞与暴露…