二分+迪杰斯特拉
题目链接:传送门
题目比较复杂,经过城市要交钱,通过道路要扣血,开始时有b血量,问你从1到n交的钱的最大值的最小值是多少。
首先,第一个条件是能到n,第二个条件是交的钱的最大值的最小值是多少
刚开始我以为是bfs
,结果写了半天也写不出来。后来看了题解才想到二分。应该还是刷题太少了,根本拓展不开思维。
解题思路: 先二分出答案mid
,check
:使用dj
松弛操作的时候判断起点和终点的收费有没有超过mid
,有的话就不能进行松弛操作。
1 | /* |
那时候年轻,不知道命运赠送的礼物,早已在暗中标好价格。
题目链接:传送门
题目比较复杂,经过城市要交钱,通过道路要扣血,开始时有b血量,问你从1到n交的钱的最大值的最小值是多少。
首先,第一个条件是能到n,第二个条件是交的钱的最大值的最小值是多少
刚开始我以为是bfs
,结果写了半天也写不出来。后来看了题解才想到二分。应该还是刷题太少了,根本拓展不开思维。
解题思路: 先二分出答案mid
,check
:使用dj
松弛操作的时候判断起点和终点的收费有没有超过mid
,有的话就不能进行松弛操作。
1 | /* |
tag:
缺失模块。
1、请确保node版本大于6.2
2、在博客根目录(注意不是yilia根目录)执行以下命令:
npm i hexo-generator-json-content
--save
3、在根目录_config.yml里添加配置:
jsonContent: meta: false pages: false posts: title: true date: true path: true text: false raw: false content: false slug: false updated: false comments: false link: false permalink: false excerpt: false categories: true tags: true