OI刷题笔记-洛谷-P1135-奇怪的电梯
SamShawCraft
2021年04月28日 22:00
收录于文集
共53篇

能用DFS或BFS做的题,本题解使用BFS。

题面

时间空间限制:1.0s 125.0MB

思路

因为要求的是按按钮的最少次数,所以可以使用优先队列。定义结构体opt(operation的简写),里面放有两个int,一个表示楼层,一个表示总按键次数,重载大于号小于号,只以总按键次数为关键字排序。在优先队列中,将按按钮次数最少的放在top()的位置上,所以应该使用小根堆(也即使用std::greater<>)。注意使用bitset或bool[]去重。

代码

变量声明

BFS函数

主函数