[CF1209F]Koala and Notebook_堆优化dij
2024-10-06 05:49:19
Koala and Notebook
题目链接:https://codeforces.com/contest/1209/problem/F
数据范围:略。
题解:
开始的时候看错题了....莫名其妙多了一道好题嘻嘻嘻
这个题非常诡异,就是把所有的边连在一起写下来。
所以我们把边权按照每一位建一个点然后拆开,保证每条边都是有向边而且边权是个位数。
然后我们按照图的样子,边权都设为$1$跑一遍堆优化$dij$,因为数的大小比较不是字符串,长串绝对比短串大。
然后我们取出所有的有向边,满足$dis_u = dis_v - 1$,因为只有这样的有向边才有用。
紧接着我们枚举每一个$dis$,并对上一层的节点排个序,即上一层的节点$i$的排名是$rk_i$。
然后每个节点再维护一个$fr_i$表示这个点的最短路(答案)上一个点是啥,也就是上一层的哪个节点编号。
先通过枚举上一个节点的$rk$,求出当前所有点的$fr$,最后转移一下即可。
代码:(我代码是抄的....略
最新文章
- Java 的静态代理 动态代理(JDK和cglib)
- c#学习<;一>; 基础知识
- iOS探索:对NSArray中自定义的对象进行排序
- 【linux】Cache和Buffer的区别
- javascript最新深度克隆对象方法
- myeclipse 10 优化
- 加载驱动模块时Device or resource busy的解决方法
- Kakfa揭秘 Day8 DirectKafkaStream代码解析
- 加密算法 - RSA算法一
- Mac下MySQL的安装与配置
- YII2 过滤器 filters
- asp.net core 六 Oracle ORM
- SSM(Spring4.x.x+SpringMVC4.x.x+Mybatis3.4.x)框架整合
- node_api学习之http
- MySQL联结查询和子查询
- Ansible入门笔记(1)之工作架构和使用原理
- 洛谷 P4112 [HEOI2015]最短不公共子串 解题报告
- Python Web学习笔记之递归和迭代的区别
- 编译libmad库
- 【LG3206】[HNOI2010]城市建设
热门文章
- vue + .net core 项目,源码在GitHub 希望对大家有所帮助
- docker安装postgresql
- 【CSP模拟赛】避难向导(倍增lca&;树的直径)
- 三大框架 之 SSH整合
- C字符贪吃蛇
- android x86 安装
- 文献阅读 - Genome-wide consequences of deleting any single gene
- Win10 设备管理器一个USB设备描述符请求失败解决方法
- Cent0S 6.7直接在/etc/resolv.conf文件下修改DNS地址重启不生效问题【转】
- 使用Git GUI,上传项目到github,并实现预览功能